Integer programming algorithms for identifying network matrices in linear systems

• Grant number: 06/00793-7
• Support type: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): June 01, 2006
• Effective date (End): May 31, 2007
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal researcher: Cid Carvalho de Souza
• Grantee: Rafael Forte Araújo Cavalcanti
• Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project we are interested in the obtention of large network matrices that occur as submatrices of the constraint matrix of the Integer Programming models of Combinatorial Optimization problems such as Partition, Covering and Packing of subsets. The goal is to find the largest network submatrix and to this end we will use models and tools from Integer Programming, including enumerative methods like branch-and-bound and Lagrangian relaxation techniques. Dual bounds and optimal solutions obtained in this work will be used to assess the quality of the heuristic solutions generated by algorithms developed in another research project that is being submitted simultaneously. (AU)