Premium
A learn‐and‐construct framework for general mixed‐integer programming problems
Author(s) -
Adamo Tommaso,
Ghiani Gianpaolo,
Guerriero Emanuela,
Manni Emanuele
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12578
Subject(s) - solver , computer science , construct (python library) , integer programming , scalability , heuristic , relaxation (psychology) , exploit , mathematical optimization , integer (computer science) , linear programming , state (computer science) , theoretical computer science , algorithm , artificial intelligence , mathematics , programming language , psychology , social psychology , computer security , database
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 produce a 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 solved by 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.