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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Benjamin Hiller, Tom Walther
Document Type:ZIB-Report
Tag:approximate convex decomposition; branch-and-bound; convex hull reformulation; disjunctive set
CCS-Classification:J. Computer Applications
Date of first Publication:2018/03/01
Series (Serial Number):ZIB-Report (17-68)