期刊
SOFT COMPUTING
卷 22, 期 6, 页码 2025-2043出版社
SPRINGER
DOI: 10.1007/s00500-016-2465-7
关键词
Knapsack problem; Disjunctive constraints; Polytope; Facet; Separation; Branch-and-cut
This paper deals with the Knapsack Problem with conflicts, also known as the Disjunctively Constrained Knapsack Problem. The conflicts are represented by a graph whose vertices are the items such that adjacent items cannot be packed in the knapsack simultaneously. We consider a classical formulation for the problem, study the polytope associated with this formulation and investigate the facial aspect of its basic constraints. We then present new families of valid inequalities and describe necessary and sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem. An extensive computational study is also presented.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据