Forbidden vertices

DOI10.1287/MOOR.2014.0673MaRDI QIDQ5252224zbMATH OpenOpenAlexFDO

Authors Gustavo Angulo, S. Ahmed, Volker Kaibel, Santanu S. Dey

Publication date 29 May 2015

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-best solutionsall-different polytopesextended formulationforbidden verticesvertex enumeration

Mathematics Subject Classification ID

Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations when P has binary vertices only. Some applications and extensions to integral polytopes are discussed.

Recommendations

• scientific article; zbMATH DE number 3858830
• The Complexity of Vertex Enumeration Methods
• scientific article; zbMATH DE number 3918105
• Cardinality constrained combinatorial optimization: complexity and polyhedra
• scientific article; zbMATH DE number 5548206

Cites work

• A note on the extension complexity of the knapsack polytope
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• All-different polytopes
• Convex hulls of superincreasing knapsacks and lexicographic orderings
• Cropped cubes
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Generating all vertices of a polyhedron is hard
• How good are convex hull algorithms?
• Ideal representations of lexicographic orderings and base-2 expansions of integer variables
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Linear vs. semidefinite extended formulations
• On a binary-encoded ILP coloring formulation
• Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• The negative cycles polyhedron and hardness of checking some polyhedral properties

Cited in

(17)

• Lexicographical polytopes
• Subgraph polytopes and independence polytopes of count matroids
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• Special issue: Global solution of integer, stochastic and nonconvex optimization problems
• Ideal formulations for constrained convex optimization problems with indicator variables
• Forbidding intersection patterns between layers of the cube
• Matrices with lexicographically-ordered rows
• Mixed integer linear programming formulation techniques
• Improving the integer L-shaped method
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• scientific article; zbMATH DE number 3858830 (Why is no real title available?)
• scientific article; zbMATH DE number 5121864 (Why is no real title available?)
• Resistant sets in the unit hypercube
• A Strange Vertex Condition Coming from Nowhere
• A primal-dual lifting scheme for two-stage robust optimization
• An outer-approximation algorithm for maximum-entropy sampling
• Lagrangian dual for integer optimization with zero duality gap that admits decomposition

This page was built for publication: Forbidden vertices

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