Duality for mixed-integer convex minimization
This paper studies duality in a combinatorial optimization problem with convex objective, convex constraints and the requirement that some of the variables are integer. In particular, this work extends the standard Karush-Kuhn-Tucker conditions so that it involves mixed integer-free polyhedra instead of separating hyperplanes. The authors begin with an overview of duality and previous attempts to extend the standard conditions followed by a presentation of mixed integer optimality certificates which are used for the proposed extension. The last sections of the article present the case of mixed integer convex dual programs and a technical appendix containing the details of some of the proofs of the presented theorems.
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Lagrangian relaxation view of linear and semidefinite hierarchies
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A strong dual for conic mixed-integer programs
- An Introduction to the Theory of Cutting-Planes
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Convexity in cristallographical lattices
- Cutting-plane theory: Algebraic methods
- Discrete Convex Analysis
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 3545380 (Why is no real title available?)
- scientific article; zbMATH DE number 3067835 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Minimal inequalities
- On the Group Problem and a Subadditive Approach to Integer Programming
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Transversal numbers over subsets of linear spaces
- Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
- Optimality certificates for convex minimization and Helly numbers
- An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities
- Constructing lattice-free gradient polyhedra in dimension two
- Lattice-free simplices with lattice width \(2d - o(d)\)
- Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem
- A strong dual for conic mixed-integer programs
- Optimality conditions in discrete-continuous nonlinear optimization
- Constructing lattice-free gradient polyhedra in dimension two
- On Subadditive Duality for Conic Mixed-integer Programs
- Duality for mixed-integer linear programs
- On the existence of duality gaps for mixed integer programming
- Evaluating mixed-integer programming models over multiple right-hand sides
- Towards a characterization of maximal quadratic-free sets
- A Unified Framework for Pricing in Nonconvex Resource Allocation Games
- Enumeration and unimodular equivalence of empty delta-modular simplices
- A characterization of maximal homogeneous-quadratic-free sets
This page was built for publication: Duality for mixed-integer convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304264)
