Modeling combinatorial disjunctive constraints via junction trees

DOI10.1007/S10107-023-01955-3MaRDI QIDQ6120845zbMATH OpenFDO

Authors Bochuan Lyu, Illya V. Hicks, Joey Huchette

Publication date 21 February 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.06916

zbMATH Keywords

biclique coverscombinatorial disjunctive constraintsgeneralized special ordered setsjunction treesplanar obstacle avoidance

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Abstract: We introduce techniques to build small ideal mixed-integer programming (MIP) formulations of combinatorial disjunctive constraints (CDCs) via the independent branching scheme. We present a novel pairwise IB-representable class of CDCs, CDCs admitting junction trees, and provide a combinatorial procedure to build MIP formulations for those constraints. Generalized special ordered sets ($extSOSk$) can be modeled by CDCs admitting junction trees and we also obtain MIP formulations of $extSOSk$. Furthermore, we provide a novel ideal extended formulation of any combinatorial disjunctive constraints with fewer auxiliary binary variables with an application in planar obstacle avoidance.

Recommendations

• A combinatorial approach for small and strong formulations of disjunctive constraints
• Ideal, non-extended formulations for disjunctive constraints admitting a network representation
• Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
• Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
• A geometric way to build strong mixed-integer programming formulations

Cites work

• A combinatorial approach for small and strong formulations of disjunctive constraints
• A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
• Algorithm for cardinality-constrained quadratic optimization
• Base-2 expansions for linearizing products of functions of discrete variables
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Disjunctive Programming
• Disjunctive programming: Properties of the convex hull of feasible points
• Elementare Theorie der konvexen Polyeder
• Heuristics for cardinality constrained portfolio optimization
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)
• scientific article; zbMATH DE number 3545380 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Ideal representations of lexicographic orderings and base-2 expansions of integer variables
• Ideal, non-extended formulations for disjunctive constraints admitting a network representation
• Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm
• Mixed integer linear programming formulation techniques
• Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions
• Mixed-integer representations in control design. Mathematical foundations and applications
• Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
• Modelling with integer variables
• Nearly tight approximability results for minimum biclique cover and partition
• Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools
• On edge perfectness and classes of bipartite graphs
• The biclique covering number of grids
• Two comments on minimum spanning trees

This page was built for publication: Modeling combinatorial disjunctive constraints via junction trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120845)