  


The continuous knapsack set
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n nonnegative integer and m nonnegative 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 facetdefining inequality, the number of distinct nonzero coefficients of the continuous variables is bounded by 2^nn. 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 facetdefining 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 twovariable pureinteger 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 nonzero coefficients of the continuous variables can take different values. Keywords: integer programming, single arc flow set Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: IBM Research Report Download: [PDF] Entry Submitted: 02/03/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  