Intersection Disjunctions for Reverse Convex Sets
From MaRDI portal
Abstract: We present a framework to obtain valid inequalities for a reverse convex set: the set of points in a polyhedron that lie outside a given open convex set. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. An intersection cut is a well-known valid inequality for a reverse convex set that is generated from a basic solution that lies within the convex set. We introduce a framework for deriving valid inequalities for the reverse convex set from basic solutions that lie outside the convex set. We first propose an extension to intersection cuts that defines a two-term disjunction for a reverse convex set, which we refer to as an intersection disjunction. Next, we generalize this analysis to a multi-term disjunction by considering the convex set's recession directions. These disjunctions can be used in a cut-generating linear program to obtain valid inequalities for the reverse convex set.
Recommendations
- scientific article; zbMATH DE number 3883113
- scientific article; zbMATH DE number 1354889
- scientific article; zbMATH DE number 3931900
- scientific article; zbMATH DE number 1098930
- Intersection theorems for closed convex sets and applications
- Intersection patterns of convex sets
- Intersection patterns of finite sets and of convex sets
- On the intersection of two particular convex sets
- scientific article; zbMATH DE number 2037805
- Graph Drawing
Cites work
- \(NP\)-hardness of linear multiplicative programming and related problems
- A faster strongly polynomial time algorithm for submodular function minimization
- A finite cutting plane method for solving linear programs with an additional reverse convex constraint
- A level set algorithm for a class of reverse convex programs
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- An algorithm for optimizing network flow capacity under economies of scale
- Characterization of local solutions for a class of nonconvex programs
- Comments on a reverse convex programming algorithm
- Constrained infinite group relaxations of MIPs
- Convex programs with an additional reverse convex constraint
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
- Convex sets and minimal sublinear functions
- Cut-generating functions and S-free sets
- Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization
- Disjunctive Programming
- Disjunctive programming: Properties of the convex hull of feasible points
- Elementary closures for integer programs.
- Generalized intersection cuts and a new cut generating paradigm
- scientific article; zbMATH DE number 3930734 (Why is no real title available?)
- scientific article; zbMATH DE number 3961360 (Why is no real title available?)
- scientific article; zbMATH DE number 4011808 (Why is no real title available?)
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3422216 (Why is no real title available?)
- Integer Programming
- Integer programming and convex analysis: Intersection cuts from outer polars
- Intersection cuts for bilevel optimization
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Linear programs with an additional reverse convex constraint
- Minimal inequalities for an infinite relaxation of integer programs
- Mixing mixed-integer inequalities
- Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization
- On functions representable as a difference of convex functions
- On solving general reverse convex programming problems by a sequence of linear programs and line searches
- On the use of cuts in reverse convex programs
- Optimization Problems Subject to a Budget Constraint with Economies of Scale
- Outer-product-free sets for polynomial optimization and oracle-based cuts
- Polyhedral convexity cuts and negative edge extensions
- Reverse convex programming
- Strengthening lattice-free cuts using non-negativity
- The ellipsoid method and its consequences in combinatorial optimization
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Using separation algorithms to generate mixed integer model reformulations
Cited in
(2)
This page was built for publication: Intersection Disjunctions for Reverse Convex Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5076701)
