Heuristics for entire programming with feasible and infeasible search paths

• Grant number: 07/01530-2
• Support Opportunities: Scholarships in Brazil - Master
• Start date: September 01, 2007
• End date: February 28, 2009
• Field of knowledge: Engineering - Electrical Engineering
• Principal Investigator: Vinicius Amaral Armentano
• Grantee: André Kazuo Takahata
• Host Institution: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This project deals with the development of generic search heuristics that interact with optimization commercial optimization solvers to solve combinatorial optimization problems which are formulated as mixed integer programming programs. This is a recent theme that makes use of the expressive advance in research and development in the solvers and the flexibility of heuristics to obtain high quality solutions in a short computational time. The heuristics are based on the rounding of solutions along the ray of a cone with vertex associated to the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such a relaxation. This approach is motivated by the geometric appeal and in the success of local search heuristics and meta-heuristics to solve combinatorial problems not formulated as integer programming problems. The development involves the project and implementation of the heuristics and computational experiments in test problems from the literature.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

TAKAHATA, André Kazuo. Heuristics for integer programming with feasible and infeasible search trajectories. 2009. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação Campinas, SP.