Incorporating bounds from decision diagrams into integer programming
- PDF / 1,054,948 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 218 Views
Incorporating bounds from decision diagrams into integer programming Christian Tjandraatmadja1 · Willem-Jan van Hoeve1 Received: 5 December 2018 / Accepted: 2 June 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract Decision diagrams have been successfully used to help solve several classes of discrete optimization problems. We explore an approach to incorporate them into integer programming solvers, motivated by the wide adoption of integer programming technology in practice. The main challenge is to map generic integer programming models to a recursive structure that is suitable for decision diagram compilation. We propose a framework that opportunistically constructs decision diagrams for suitable substructures, if present. In particular, we explore the use of a prevalent substructure in integer programming solvers known as the conflict graph, which we show to be amenable to decision diagrams. We use Lagrangian relaxation and constraint propagation to consider constraints that are not represented directly by the substructure. We use the decision diagrams to generate dual and primal bounds to improve the pruning process of the branch-and-bound tree of the solver. Computational results on the independent set problem with side constraints indicate that our approach can provide substantial speedups when conflict graphs are present. Keywords Integer programming · Decision diagrams · Lagrangian relaxation · Conflict graph Mathematics Subject Classification 90C10 · 90C35
Christian Tjandraatmadja is currently at Google.
B
Christian Tjandraatmadja [email protected] Willem-Jan van Hoeve [email protected]
1
Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA
123
C. Tjandraatmadja, W.-J. van Hoeve
1 Introduction Decision diagrams were originally introduced to compactly represent Boolean functions, and have been widely applied to verification and configuration problem [4,21,30,38]. More recently, decision diagrams have been applied to model and solve combinatorial optimization problems, in particular via a stand-alone solver in which relaxed and restricted decision diagrams provide dual and primal bounds as well as a branch-and-bound search strategy [15,18,19]. A strength of decision diagrams lies in representing recursive structure embedded in certain discrete optimization problems. Typically, this structure is explicitly modeled by a user through a dynamic programming formulation [17], which is often not readily available when facing a new problem. Instead, it is common for discrete optimization problems to be modeled via integer programming (IP) formulations, due to the effectiveness of mixed-integer programming (MIP) solvers and the capability of IP models to express a variety of problems. In this paper, we propose a framework to improve the solution process of MIP solvers through the use of relaxed decision diagrams: decision diagrams that represent relaxations of a problem. To achieve this goal, we study two main r
Data Loading...
