Facet separation for disjunctive constraints with network flow representation

Péter Dobrovoczki () and Tamás Kis ()
Additional contact information
Péter Dobrovoczki: HUN-REN Institute for Computer Science and Control
Tamás Kis: HUN-REN Institute for Computer Science and Control

Annals of Operations Research, 2024, vol. 341, issue 2, No 4, 825-857

Abstract: Abstract We present a novel algorithm for separating facet-inducing inequalities for the convex-hull of the union of polytopes representing a disjunctive constraint of special structure. It is required that the union of polytopes admit a certain network flow representation. The algorithm is based on a new, graph theoretic characterization of the facets of the convex-hull. Moreover, we characterize the family of polytopes that are representable by the networks under consideration. We demonstrate the effectiveness of our approach by computational results on a set of benchmark problems.

Keywords: Disjunctive programming; Embedding formulations; Branch-and-cut (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06264-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:341:y:2024:i:2:d:10.1007_s10479-024-06264-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06264-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().