.png){kind=icon}
返回
Optimization algorithms for the disjunctively constrained knapsack problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s00500-016-2465-7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Knapsack problem
Disjunctive constraints
Polytope
Facet
Separation
Branch-and-cut
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.5
论文数:
1.0W
被引数:
2.1W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容