A recombination-based matheuristic for mixed integer programming problems with binary variables

André L. Maravilha, Eduardo G. Carrano, Felipe Campelo

Research output: Contribution to journalArticle

Abstract

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.
Original languageEnglish
Pages (from-to)418-434
Number of pages17
JournalInternational Transactions in Operational Research
Volume27
Issue number1
Early online date23 Mar 2018
DOIs
Publication statusPublished - 1 Jan 2020

Keywords

  • branch and bound
  • combinatorial optimization
  • integer programming
  • local search
  • metaheuristics

Fingerprint Dive into the research topics of 'A recombination-based matheuristic for mixed integer programming problems with binary variables'. Together they form a unique fingerprint.

  • Cite this