Disjunctive cuts in mixed-integer conic optimization
From MaRDI portal
Publication:6038657
DOI10.1007/S10107-022-01844-1zbMATH Open1518.90053arXiv1912.03166MaRDI QIDQ6038657FDOQ6038657
Authors: Andrea Lodi, Mathieu Tanneau, J. P. Vielma 
Publication date: 2 May 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: This paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating disjunctive cuts, and investigate the impact of the normalization condition on its resolution. In particular, we show that a careful selection of normalization guarantees its solvability and conic strong duality. Then, we highlight the shortcomings of separating conic-infeasible points in an outer-approximation context, and propose conic extensions to the classical lifting and monoidal strengthening procedures. Finally, we assess the computational behavior of various normalization conditions in terms of gap closed, computing time and cut sparsity. In the process, we show that our approach is competitive with the internal lift-and-project cuts of a state-of-the-art solver.
Full work available at URL: https://arxiv.org/abs/1912.03166
Recommendations
- On the separation of disjunctive cuts
- A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization
- Cuts for Conic Mixed-Integer Programming
- Conic mixed-integer rounding cuts
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)
Cites Work
- Disciplined convex programming
- CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Convex Analysis
- An algorithmic framework for convex mixed integer nonlinear programs
- Strengthening cuts for mixed integer programs
- A branch-and-cut method for 0-1 mixed convex programming
- Convex programming for disjunctive convex optimization
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Elements of Large-Scale Mathematical Programming Part I: Concepts
- Disjunctive Programming
- Lift-and-project for mixed 0-1 programming: recent progress
- Split cuts and extended formulations for mixed integer conic quadratic programming
- Disjunctive cuts for cross-sections of the second-order cone
- The split closure of a strictly convex body
- On optimizing over lift-and-project closures
- On minimal valid inequalities for mixed integer conic programs
- On sublinear inequalities for mixed integer conic programs
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- Intersection cuts for mixed integer conic quadratic sets
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Conic mixed-integer rounding cuts
- Two-term disjunctions on the second-order cone
- Cuts for mixed 0-1 conic programming
- A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
- On the separation of disjunctive cuts
- Title not available (Why is that?)
- Reflections on generating (disjunctive) cuts
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Lift-and-project cuts for mixed integer convex programs
- Lifting for conic mixed-integer programming
- Extended formulations in mixed-integer convex programming
- Outer approximation with conic certificates for mixed-integer convex problems
- Reformulating the disjunctive cut generating linear program
- A disjunctive cut strengthening technique for convex MINLP
- Polyhedral approximation in mixed-integer convex optimization
- Cutting plane algorithm for convex generalized disjunctive programs
- ``Facet separation with one linear program
- MathOptInterface: A Data Structure for Mathematical Optimization Problems
Cited In (15)
- Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints
- A convex-analysis perspective on disjunctive cuts
- On the separation of disjunctive cuts
- On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
- A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization
- Monoidal cut strengthening revisited
- Computing deep facet-defining disjunctive cuts for mixed-integer programming
- Disjunctive Cuts for Nonconvex MINLP
- Integer Programming and Combinatorial Optimization
- Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
- Intersection cuts from multiple rows: a disjunctive programming approach
- Disjunctive cuts for mixed integer nonlinear programming problems
- An in-out approach to disjunctive optimization
- On pathological disjunctions and redundant disjunctive conic cuts
- Disjunctive cuts for continuous linear bilevel programming
This page was built for publication: Disjunctive cuts in mixed-integer conic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038657)
