Full text
| |
| Author(s): |
André Kazuo Takahata
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação |
| Defense date: | 2009-08-05 |
| Examining board members: |
Vinícius Amaral Armentano;
Edson Luiz França Senne;
Cid Carvalho de Souza
|
| Advisor: | Vinícius Amaral Armentano |
| Abstract | |
In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. (AU) | |
| FAPESP's process: | 07/01530-2 - Heuristics for entire programming with feasible and infeasible search paths |
| Grantee: | André Kazuo Takahata |
| Support Opportunities: | Scholarships in Brazil - Master |