The continuous knapsack set

Abstract

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 generalization of the single arc flow set studied by Magnanti et al. (Math Program 60:233–250, 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 (Discrete Optim 3:95–110, 2006). Finally we show (via an example) that when n=3, the non-zero coefficients of the continuous variables can take different values.