The continuous knapsack set

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Guenluek, Oktay; Wolsey, Laurence A.
• 署名单位: International Business Machines (IBM); IBM USA; Universite Catholique Louvain
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0859-4
• 发表日期: 2016
• 页码: 471-496
• 关键词: design arc-set; network; polyhedra

摘要

We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with non-negative integer and non-negative bounded continuous variables. When , 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 . Our next result is to show that when , this upper bound is actually 1. This implies that when , 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 . The convex hull of the sets with and is then shown to be given by facets of either two-variable pure-integer knapsack sets or continuous knapsack sets with and 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 , the non-zero coefficients of the continuous variables can take different values.