The Continuous Knapsack Set

We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n non-negative integer and m non-negative bounded continuous variables. When n = 1, this set is a slight generalization of the single arc flow set studied by Magnanti, Mirchandani, and Vachani (1993). We first show that in any facet-defining inequality, the number of distinct non-zero coefficients of the continuous variables is bounded by 2n - n. Our next result is to show that when n = 2, this upper bound is actually 1. This implies that when n = 2, the coefficients of the continuous variables in any facet-defining inequality are either 0 or 1 after scaling, and that all the facets can be obtained from facets of continuous knapsack sets with m = 1. The convex hull of the sets with n = 2 and m = 1 is then shown to be given by facets of either two-variable pure-integer knapsack sets or continuous knapsack sets with n = 2 and m = 1 in which the continuous variable is unbounded. The convex hull of these two sets has been completely described by Agra and Constantino (2006). Finally we show (via an example) that when n = 3, the non-zero coefficients of the continuous variables can take different values.

By: Sanjeeb Dash, Oktay Günlük, Laurence Wolsey

Published in: Mathematical Programming , volume 155, (no 1-2), pages 471-496; 10.1007/s10107-015-0859-4 in 2016

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .