Forbidden Vertices

DOI10.1287/moor.2014.0673zbMath1316.90021arXiv1309.2545OpenAlexW3037601748MaRDI QIDQ5252224

Gustavo Angulo, Volker Kaibel, Shabbir Ahmed, 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

extended formulationvertex enumerationforbidden vertices\(k\)-best solutionsall-different polytopes

Mathematics Subject Classification ID

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

Related Items

On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank, Matrices with lexicographically-ordered rows, An outer-approximation algorithm for maximum-entropy sampling, Lexicographical polytopes, A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization, Subgraph polytopes and independence polytopes of count matroids, On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank, Mixed Integer Linear Programming Formulation Techniques, Improving the Integer L-Shaped Method, Resistant Sets in the Unit Hypercube, Special issue: Global solution of integer, stochastic and nonconvex optimization problems, Ideal formulations for constrained convex optimization problems with indicator variables

Cites Work

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