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 - http://www.scopus.com/inward/record.url?scp=84930614705&partnerID=8YFLogxK
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 -