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

Fingerprint

Integer programming
Polishing
Mixed integer programming
Recombination
Heuristics

Keywords

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

Cite this

@article{5867abcd0b194e7da8dcf082a318acff,
title = "A recombination-based matheuristic for mixed integer programming problems with binary variables",
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.",
keywords = "branch and bound, combinatorial optimization, integer programming, local search, metaheuristics",
author = "Maravilha, {Andr{\'e} L.} and Carrano, {Eduardo G.} and Felipe Campelo",
year = "2020",
month = "1",
day = "1",
doi = "10.1111/itor.12526",
language = "English",
volume = "27",
pages = "418--434",
journal = "International Transactions in Operational Research",
issn = "0969-6016",
publisher = "Blackwell",
number = "1",

}

A recombination-based matheuristic for mixed integer programming problems with binary variables. / Maravilha, André L.; Carrano, Eduardo G.; Campelo, Felipe.

In: International Transactions in Operational Research, Vol. 27, No. 1, 01.01.2020, p. 418-434.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Maravilha, André L.

AU - Carrano, Eduardo G.

AU - Campelo, Felipe

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - branch and bound

KW - combinatorial optimization

KW - integer programming

KW - local search

KW - metaheuristics

UR - https://onlinelibrary.wiley.com/doi/full/10.1111/itor.12526

UR - https://github.com/andremaravilha/polishing-heuristics

UR - http://www.scopus.com/inward/record.url?scp=85044340075&partnerID=8YFLogxK

U2 - 10.1111/itor.12526

DO - 10.1111/itor.12526

M3 - Article

VL - 27

SP - 418

EP - 434

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

SN - 0969-6016

IS - 1

ER -