Polynomial size IP formulations of knapsack may require exponentially large coefficients.

Christopher Hojny

Published in: Oper. Res. Lett. (2020)

Keyphrases

polynomial size
exponential size
knapsack problem
dynamic programming
dnf formulas
upper bound
boolean functions
bounded treewidth
lower bound
np complete
knowledge compilation