On the existence of compact ε-approximated formulations for knapsack in the original space

Yuri Faenza; Laura Sanità

doi:10.1016/j.orl.2015.04.004

On the existence of compact ε-approximated formulations for knapsack in the original space

Yuri Faenza
, Laura Sanità

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

Abstract

We show that there exists a family P of Knapsack polytopes such that for each P∈P and each ε>0, any ε-approximated formulation of P in the original space ^Rn requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an ε-approximated formulation in the original space can be obtained with inequalities using at most O(1εminlog(n/ε),n) different coefficients.

Original language	English
Pages (from-to)	339-342
Number of pages	4
Journal	Operations Research Letters
Volume	43
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2015.04.004
Publication status	Published - 30 May 2015
Externally published	Yes

Funding

We thank Carsten Moldenhauer for useful discussions. The author Yuri Faenza is supported by the Ambizione grant PZ00P2_154779 Tight formulations of 0-1 problems funded by the Swiss National Science Foundation.

Keywords

Approximated formulation
Integer programming
Knapsack

Access to Document

10.1016/j.orl.2015.04.004

Cite this

@article{3e037a8b00fd4ed29ed16c5fafe94d95,

title = "On the existence of compact ε-approximated formulations for knapsack in the original space",

abstract = "We show that there exists a family P of Knapsack polytopes such that for each P∈P and each ε>0, any ε-approximated formulation of P in the original space Rn requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an ε-approximated formulation in the original space can be obtained with inequalities using at most O(1εminlog(n/ε),n) different coefficients.",

keywords = "Approximated formulation, Integer programming, Knapsack",

author = "Yuri Faenza and Laura Sanit{\`a}",

year = "2015",

month = may,

day = "30",

doi = "10.1016/j.orl.2015.04.004",

language = "English",

volume = "43",

pages = "339--342",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - On the existence of compact ε-approximated formulations for knapsack in the original space

AU - Faenza, Yuri

AU - Sanità, Laura

PY - 2015/5/30

Y1 - 2015/5/30

N2 - We show that there exists a family P of Knapsack polytopes such that for each P∈P and each ε>0, any ε-approximated formulation of P in the original space Rn requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an ε-approximated formulation in the original space can be obtained with inequalities using at most O(1εminlog(n/ε),n) different coefficients.

AB - We show that there exists a family P of Knapsack polytopes such that for each P∈P and each ε>0, any ε-approximated formulation of P in the original space Rn requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an ε-approximated formulation in the original space can be obtained with inequalities using at most O(1εminlog(n/ε),n) different coefficients.

KW - Approximated formulation

KW - Integer programming

KW - Knapsack

UR - https://www.scopus.com/pages/publications/84930614705

U2 - 10.1016/j.orl.2015.04.004

DO - 10.1016/j.orl.2015.04.004

M3 - Article

AN - SCOPUS:84930614705

SN - 0167-6377

VL - 43

SP - 339

EP - 342

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

On the existence of compact ε-approximated formulations for knapsack in the original space

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this