@inproceedings{d54b50eebb594fbcb827b8bf56370b27,

title = "A few strong knapsack facets",

abstract = "We perform a shooting experiment for the knapsack facets and observe that 1/k-facets are strong for small k; in particular, k dividing 6 or 8.We also observe spikes of the size of 1/k-facets when k = n or when kC1 divides n+1.We discuss the strength of the 1/n-facets introduced by Ar{\'a}oz et al. (Math Program 96:377– 408, 2003) and the knapsack facets given by Gomory{\textquoteright}s homomorphic lifting. A general integer knapsack problem is a knapsack subproblem where a portion, often a significant majority, of the variables are missing from the master knapsack problem. The number of projections of 1/k-facets on a knapsack subproblem of l variables is O.(⌈k/2⌉), note that this is independent of the size of the master problem. Since 1/k-facets are strong for small k, we define the 1/k-inequalities which include the 1/d-facets with d dividing k and fix k to be a small constant such as k / 6 or k = 8. We develop an efficient way of enumerating violated valid 1/k-inequalities. For each violated 1/k-inequality, we determine its validity by solving a small integer programming problem, the size of which depends only on k.",

keywords = "Cutting planes, Facets, Knapsack problem, Master knapsack polytope, Shooting experiment",

author = "Sunil Chopra and Sangho Shim and Steffy, {Daniel E.}",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-23699-5_4",

language = "English (US)",

isbn = "9783319236988",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer New York LLC",

pages = "77--94",

editor = "Boris Defourny and Tamas Terlaky",

booktitle = "Modeling and Optimization",

note = "International Conference on Modeling and Optimization: Theory and Applications, MOPTA, 2014 ; Conference date: 13-08-2014 Through 15-08-2014",

}