Forbidden Vertices

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.

• Publication year

  2013

• Venue

  Mathematics of Operations Research

• Publication date

  2013-09-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/moor.2014.0673arXiv 1309.2545
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A note on the extension complexity of the knapsack polytope

  2013cited by this paper
• The matching polytope has exponential extension complexity

  2013cited by this paper
• Ideal representations of lexicographic orderings and base-2 expansions of integer variables

  2013cited by this paper
• The negative cycles polyhedron and hardness of checking some polyhedral properties

  2011cited by this paper
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization

  2011cited by this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cited by this paper
• Extended Formulations in Combinatorial Optimization

  2011cited by this paper
• Disjunctive Programming

  2009cited by this paper
• On a Binary-Encoded ILP Coloring Formulation

  2007cited by this paper
• Generating All Vertices of a Polyhedron Is Hard

  2006cited by this paper
• Separating Type-I Odd-Cycle Inequalities for a Binary-Encoded Edge-Coloring Formulation

  2005cited by this paper
• Cropped Cubes

  2003cited by this paper
• All-Different Polytopes

  2002cited by this paper
• The integer L-shaped method for stochastic integer programs with complete recourse

  1993cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991cited by this paper
• Annals of Discrete Mathematics

  1986cited by this paper
• Theory of linear and integer programming

  1986cited by this paper
• A PROCEDURE FOR COMPUTING THE K BEST SOLUTIONS TO DISCRETE OPTIMIZATION PROBLEMS AND ITS APPLICATION TO THE SHORTEST PATH PROBLEM

  1972cited by this paper
• Letter to the Editor - An Algorithm for Ranking all the Assignments in Order of Increasing Cost

  1968cited by this paper

• A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

  2024cites this paper
• Nonlinear Decision Rules Made Scalable by Nonparametric Liftings

  2024cites this paper
• An outer-approximation algorithm for maximum-entropy sampling

  2024cites this paper
• Lagrangian dual with zero duality gap that admits decomposition

  2024cites this paper
• A Knowledge Compilation Take on Binary Polynomial Optimization

  2023cites this paper
• A Privacy-Aware Distributed Approach for Loosely Coupled Mixed Integer Linear Programming Problems

  2022cites this paper
• Special Issue: Global Solution of Integer, Stochastic and Nonconvex Optimization Problems

  2022cites this paper
• SIAG/OPT Views and News

  2021cites this paper
• Strong IP formulations need large coefficients

  2021cites this paper
• Ideal formulations for constrained convex optimization problems with indicator variables

  2020cites this paper
• On a class of stochastic programs with exponentially many scenarios

  2020cites this paper
• A Primal-Dual Lifting Scheme for Two-Stage Robust Optimization

  2020cites this paper
• Lancet: Better Network Resilience by Designing for Pruned Failure Sets

  2019cites this paper
• Resistant Sets in the Unit Hypercube

  2019cites this paper
• An MINLP formulation for the optimization of multicomponent distillation configurations

  2019cites this paper
• Matrices with lexicographically-ordered rows

  2018cites this paper
• Matrices with lexicographically-ordered rows

  2018cites this paper
• Lexicographical polytopes

  2018cites this paper
• On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank

  2018cites this paper
• Exact MAP Inference by Avoiding Fractional Vertices

  2017influential citation
• Decomposition Algorithms and Parallel Computing for Chance-constrained and Stochastic Integer Programs with Applications.

  2016cites this paper
• Global Optimization Methods for Optimal Power Flow and Transmission Switching Problems in Electric Power Systems

  2016cites this paper
• Strong mixed-integer formulations for the floor layout problem

  2016cites this paper
• Improving the Integer L-Shaped Method

  2016influential citation
• On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank

  2016cites this paper
• On lexicographic approximations of integer programs

  2016cites this paper
• Facet Guessing for Finding the M-Best Integral Solutions of a Linear Program

  2016influential citation
• Subgraph polytopes and independence polytopes of count matroids

  2015cites this paper
• Large-Scale Unit Commitment: Decentralized Mixed Integer Programming Approaches

  2015cites this paper
• Embedding Formulations and Complexity for Unions of Polyhedra

  2015cites this paper
• Mixed Integer Linear Programming Formulation Techniques

  2015cites this paper
• New Formulation and Strong MISOCP Relaxations for AC Optimal Transmission Switching Problem

  2015cites this paper