integer programming formulation

Computational Aspects of Relaxation Complexity: Possibilities and Limitation

  • Gennadiy Averkov
  • Christopher Hojny
  • Matthias Schymura
    • Categories (Mixed) Integer Linear Programming Tags ,

    The relaxation complexity $\mathrm{rc}(X)$ of the set of integer points $X$ contained in a polyhedron is the smallest number of facets of any polyhedron $P$ such that the integer points in $P$ coincide with $X$. It is a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive … Read more

    Polynomial Size IP Formulations of Knapsack May Require Exponentially Large Coefficients

  • Christopher Hojny
    • Categories 0-1 Programming, Integer Programming Tags , ,

    A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural … Read more