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

• Author: Felipe Campelo,Eduardo G. Carrano,André L. Maravilha
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12526
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 418–434

DOI: 10.1111/itor.12526

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A recombination-based matheuristic for mixed integer

programming problems with binary variables

Andr´

e L. Maravilhaa,c , Eduardo G. Carranob,c and Felipe Campelob,c

aGraduate Program in Electrical Engineering, UniversidadeFederal de Minas Gerais, Belo Horizonte, 31270-010 MG,

Brazil

bDepartment of Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, 31270-010 MG, Brazil

cOperations Research and ComplexSystems Laboratory (ORCS Lab), Belo Horizonte, 31270-010 MG, Brazil

E-mail: andrelms@ufmg.br [Maravilha];egcarrano@ufmg.br [Carrano]; fcampelo@ufmg.br [Campelo]

Received 13 October 2016; receivedin revised form 14 February 2018; accepted 15 February 2018

Abstract

This work introduces a heuristic formixed 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 thatof 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 comparableto 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:combinatorial optimization; integer programming; metaheuristics; branch and bound; local search

1. Introduction

Many real problems in applications ranging from computer science and engineering to biology

can be formulated as mixed integer programming (MIP) problems (Du and Pardalos, 1999). The

selection of the subset of elements from a set of available choices, the assignment of resources, and

the sequencing of tasks such that a given cost function is minimized are examples of situations

usually formulated as MIP problems (Wolsey, 1998). An MIP problem can be stated as

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

A. L. Maravilha et al. / Intl. Trans.in Op. Res. 27 (2020) 418–434 419

Minimize cTx+fTy+hTz

Subject to: Ax +Gy +Hz ≥b

x∈Rn

+(1)

y∈Zm

+

z∈{0,1}p,

in which x,y,andzare column vectors of decision variables; c∈Rn,f∈Rm,andh∈Rpare column

vectors representing the coefficients in the objective function; A∈Rq×n,G∈Rq×m,andH∈Rq×p

are coefficient matrices of constraints; and b∈Rqis a column vector of constant terms in the

constraints.

MIP problems are one of the most active topics in operations research and optimization, mainly

due to their theoretical and practical importance.Most of the practical problems formulated as MIP

belong to the class of NP-hard problems, which means they cannot be solved to proven optimality

in polynomial time on a deterministic machine (Garey and Johnson, 1979; Wolsey, 1998). However,

the ability to find good solutions, even if not provably optimal, is essential when dealing with large-

scale and complex problems. In this context, heuristics play a very important role (Gendreau and

Potvin, 2010).

Exact and heuristic approaches have advanced with little interaction for a long time (Raidl and

Puchinger, 2008; Raidl et al., 2010). Bridging this gap, hybrid techniques that combine exact and

heuristic approaches, commonly referred to as matheuristics (Raidl and Puchinger, 2008), have

been shown to be quite effective in providing solutions to complex MIP problems (Maniezzo

et al., 2010), and generally present a more mathematically sound approach to the development of

heuristics. Among the methods classified as matheuristics, MIP heuristic is a term used to refer

to a heuristic method designed for MIP problems in general. These MIP heuristics usually solve

sub-MIP problems (or MIP subproblems—MIP problems of reduced size) built from the original

MIP problem.

Some MIP heuristics have provided a significant step forward in the capability of solving large-

scale and complex MIP problems. Examples include local branching (Fischetti and Lodi, 2003),

which defines sub-MIPs by adding new constraints to the problem; relaxation-induced neighbor-

hood search (RINS; Danna et al., 2005), which defines sub-MIPs by the difference between the

incumbent solution and a solution obtained to the linear relaxation; distance-induced neighbor-

hood search (DINS; Ghosh, 2007), which combines aspects from both local branching and RINS;

preprocessing aware RINS (p-RINS; Gomes et al., 2013), which explicitly employs preprocessing

techniques in the sub-MIP construction; and Solution Polishing (Rothberg, 2007), which defines

sub-MIPs by the difference among feasible solutions in a pool. These heuristics explore a neigh-

borhood from a known feasible solution through the solution of a sub-MIP problem. As their goal

is to find solutions of better quality, these methods are generally referred to as improvement MIP

heuristics. Distinct methods differ on how the neighborhood is built. MIP heuristics are not limited

to neighborhood searches. Methods such as dive and fix (Wolsey, 1998), feasibility pump (Fischetti

et al., 2005), and relaxation-enforced neighborhood search (RENS; Berthold 2014) aim at finding

a feasible solution by solving sub-MIP problems. They are referred to as feasibility MIP heuristics.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies