Full text
| |
| Author(s): |
Rafael Francisco dos Santos
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2006-12-21 |
| Examining board members: |
Cid Carvalho de Souza;
Vinícius Amaral Armentano;
Orlando Lee
|
| Advisor: | Cid Carvalho de Souza |
| Abstract | |
In this dissertation we propose a broader usage of the Canonical Cuts (CC) introduced by Balas and Jeroslow ([2]) in the Local Branching method (LB) of Fischetti and Lodi ([6]). The LB is a general purpose heuristic for Mixed Integer Programming (MIP) that explores neighborhoods defined by the addition of linear inequalities to the original model. These inequalities determine subproblems that are computed more quickly by MIP solvers. An analysis of the execution of LB indicated that, in some situations, it adds local branching cuts that are too superficial (i.e., chopping off few solutions) and that these cuts happen very often. Since the local branching cuts of Fischetti and Lodi are special cases of CCs for 0?1 integer programming, we propose to incorporate deeper CCs (i.e, chopping of more solutions) to LB. We executed the resulting algorithm on 25 out of the 29 instances tested in [6] and we obtained better results than those attained by the original LB and by the XPRESS commercial MIP solver under default settings. Another research that we carried out was the inclusion of CC to the RINS heuristics for general mixed integer programs ([3]). This heuristic appeared during the development of this dissertation and showed a good performance. We carried out some tests with the same instances on which LB was tested and the results are promising. Finally, besides using the CCs in heuristics, we created a branching strategy that can be embedded to the branch-and-cut algorithms of the MIP solvers. We called it dive branching and implemented it in the XPRESS solver. In experiments with the same set of instances as before, we obtained results of better quality than those produced by XPRESS with default settings (AU) | |