Optimization Online


Polynomial Size IP Formulations of Knapsack May Require Exponentially Large Coefficients

Christopher Hojny(c.hojny***at***tue.nl)

Abstract: 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 model) every integer formulation of stable sets requires exponentially large coefficients if the number of non-trivialinequalities is bounded by a constant.

Keywords: integer programming formulation, knapsack polytope, size of coefficients

Category 1: Integer Programming

Category 2: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 11/14/2019
Entry Accepted: 11/14/2019
Entry Last Modified: 11/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society