Conference proceeding
Enumerative Branching with Less Repetition
INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2020, Vol.12296, pp.399-416
Lecture Notes in Computer Science
01/01/2020
DOI: 10.1007/978-3-030-58942-4_26
Abstract
We can compactly represent large sets of solutions for problems with discrete decision variables by using decision diagrams. With them, we can efficiently identify optimal solutions for different objective functions. In fact, a decision diagram naturally arises from the branch-and-bound tree that we could use to enumerate these solutions if we merge nodes from which the same solutions are obtained on the remaining variables. However, we would like to avoid the repetitive work of finding the same solutions from branching on different nodes at the same level of that tree. Instead, we would like to explore just one of these equivalent nodes and then infer that the same solutions would have been found if we explored other nodes. In this work, we show how to identify such equivalences-and thus directly construct a reduced decision diagram-in integer programs where the left-hand sides of all constraints consist of additively separable functions. First, we extend an existing result regarding problems with a single linear constraint and integer coefficients. Second, we show necessary conditions with which we can isolate a single explored node as the only candidate to be equivalent to each unexplored node in problems with multiple constraints. Third, we present a sufficient condition that confirms if such a pair of nodes is indeed equivalent, and we demonstrate how to induce that condition through preprocessing. Finally, we report computational results on integer linear programming problems from the MIPLIB benchmark. Our approach often constructs smaller decision diagrams faster and with less branching.
Details
- Title: Subtitle
- Enumerative Branching with Less Repetition
- Creators
- Thiago Serra - Bucknell University
- Contributors
- E Hebrard (Editor)N Musliu (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2020, Vol.12296, pp.399-416
- Publisher
- Springer Nature
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-030-58942-4_26
- ISSN
- 0302-9743
- eISSN
- 1611-3349
- Number of pages
- 18
- Language
- English
- Date published
- 01/01/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984696753002771
Metrics
1 Record Views