A learn‐and‐construct framework for general mixed‐integer programming problems

• DOI: http://doi.org/10.1111/itor.12578
• Date: 01 January 2020
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 9–25

DOI: 10.1111/itor.12578

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A learn-and-construct framework for general mixed-integer

programming problems

Tommaso Adamo , Gianpaolo Ghiani , Emanuela Guerriero and

Emanuele Manni

Dipartimento di Ingegneria dell’Innovazione, Universit`

a del Salento, via per Monteroni, Lecce 73100, Italy

E-mail: tommaso.adamo@unisalento.it [Adamo]; gianpaolo.ghiani@unisalento.it [Ghiani];

emanuela.guerriero@unisalento.it [Guerriero]; emanuele.manni@unisalento.it [Manni]

Received 27 July2016; received in revised form 2 November 2017; accepted 3 July 2018

Abstract

In this paper, we propose a new framework for finding an initial feasible solution from a mixed-integer

programming (MIP) model. We call it learn-and-construct since it first exploits the structure of the model and

its linear relaxation solution and then uses this knowledge to try to producea feasible solution. In the learning

phase, we use an unsupervised learning algorithm to cluster entities originating the MIP model. Such clusters

are then used to decompose the original MIP in a number of easier sub-MIPs that are solvedby using a black

box solver.Computational results on three well-known problems show that our procedure is characterized by

a success rate larger than both the feasibility pump heuristic and a state-of-the-art MIP solver. Furthermore,

our approach is more scalable and uses less computing time on average.

Keywords:mixed-integer programming; heuristics; feasible solution; unsupervised learning; optimization

1. Introduction

Finding a feasible solution of a mixed-integer programming (MIP) model is a well-known NP-hard

problem. Over the last decade, research in this field has produced many heuristics tackling this

problem. Among these, the so-called feasibility pump (FP) proposed in Fischetti et al. (2005) for

0–1 binary problems has proven to be very successful. The FP framework has been subsequently

slightly modified and improved in several ways (Achterberg and Berthold, 2007; Bertacco et al.,

2007; Fischetti and Salvagnin, 2009; Boland et al., 2012, 2014). The basic idea of the FP is that of

considering pairs of points (x∗,˜

x), with x∗feasible for the linear programming (LP) relaxation of

the original MIP (but not necessarily integer), and ˜

xinteger, but not necessarily feasible. At each

iteration, FP updates x∗and ˜

xwith the aim of reducing as much as possible the “distance” (x∗,˜

x)

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.

10 T. Adamo et al. / Intl. Trans. in Op. Res. 27 (2020) 9–25

between them, in order to find an integer feasible solution. Given ˜

x, the process of finding the LP

feasible solution closest to ˜

xis known as projection problem.Finding the closest integer point to x∗

is known as rounding step. If the L1norm is used as a measure of distance (as is the case for most

implementations of FP), then the projection problem can be solved as an LP, and the rounding

step is performed by simply rounding x∗. Given its generality and ease of implementation, the FP

heuristic is now implemented in most MIP solvers, both commercial and open-source, such as IBM

ILOG CPLEX and GLPK.

There are other MIP-based heuristics that—although aiming to improve a given feasible solu-

tion rather than to obtain a first one—are worth mentioning. In particular, the Local Branching

algorithm by Fischetti and Lodi (2003) is based on the construction of spherical neighborhoods

obtained by defining appropriate nonvalid inequalities. For purely binary MIPs, a neighborhood

relies on the concept of Hamming distance from the current solution. The neighborhoods are then

explored by using a generic black boxMIP solver. Another remarkable contributionis due to Danna

et al. (2005), who defined the relaxation-induced neighborhood search heuristic. This method de-

fines Relaxation-Induced Neighborhoods of a givenincumbent solution as follows. First, it fixes the

variables having the same values in the incumbent and in the continuous relaxation. Then, it sets a

cutoff based on the objective value of the current incumbent and, finally, it solves a sub-MIP on the

remaining variables. In an attempt to improve solutions to MIP models, Rothberg (2007) presented

an evolutionary algorithm. In particular, in the context of a large neighborhood search framework,

the author proposed coarse-grained approaches to mutating and combining MIP solutions and

integrated them within an MIP branch-and-bound framework.

In this paper, we propose a new framework for obtaining an initial feasible solution for general

MIPs, based on the approach recently presented in Ghiani et al. (2015), who start from an MIP

feasible solution and improve it through a two-phase procedure. The intuition lies in looking at a

generic MIP model as made up of sets of entities (e.g., a set of plants, a set of warehouses, a set

of customers, etc.). In this way, in such a model each variable, as well as each constraint, is tagged

by one or more entities. In the first phase (learning), the approach exploits the structure of both

the problem and a given feasible solution to group the entities originating the MIP model into a

number of homogeneous clusters by using an unsupervised learning method. Then, in the second

phase (fixing), the procedure explores a neighborhood of the current solution, by considering one

cluster at a time and solving a sub-MIP for each of them, where all the variables unrelated to the

entities of that cluster are fixed to their values in the reference solution.

Our approach, which we call learn-and-construct, differs from that in Ghiani et al. (2015) mainly

(but not only) for the learning phase, in that we use the information provided by an infeasible

solution (in addition to the information provided by the model itself) to determine the clusters. The

ultimate goal is to obtain, at the end of the second phase, a feasible MIP solution. This goal is

achieved by solving a sequence of sub-MIPs,as in Ghiani et al. (2015). However, the structure of the

sub-MIPs is slightly different, due to the infeasibility of the reference solution, as will be clarified in

Section 2.1. In addition, to extract from both the model and the solution the information needed to

obtain the clusters, we also takeadvantage of some concepts presented in Adamo et al. (2016, 2017a,

2017b). Another difference of our approach lies in the clustering technique. Indeed, we make use of

a method based on the k-medoids algorithm, suitably modified to identify more clusters balanced

in terms of number and nature of the entities. Finally, differently from Ghiani et al. (2015), here the

parameter tuning effort is demanded to an automatic algorithm configuration (AAC) procedure

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies