Improving branching for disjunctive polyhedral models using approximate convex decompositions
Please always quote using this URN: urn:nbn:de:0297-zib-67462
- Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.
Author: | Benjamin HillerORCiD, Tom Walther |
---|---|
Document Type: | ZIB-Report |
Tag: | approximate convex decomposition; branch-and-bound; convex hull reformulation; disjunctive set |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Classification: | J. Computer Applications |
Date of first Publication: | 2018/03/01 |
Series (Serial Number): | ZIB-Report (17-68) |
ISSN: | 1438-0064 |