.png){kind=icon}
返回
Assignment problem with conflicts
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2019.07.001.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We focus on an extension of the assignment problem with additional conflict (pair) constraints in conjunction with the assignment constraints and binary restrictions. Given a bipartite graph with a cost associated with each edge and a conflict set of edge pairs, the assignment problem with conflict constraints corresponds to finding a minimum weight perfect matching without any conflicting edge pair. For example, some chemicals cannot be processed on close processors, food and toxic products cannot be stored neighboring locations at the same storage area, and machines cannot be sent to process jobs without satisfying some spatial constraints. Unlike the well-known assignment problem, this problem is NP-hard. We first introduce a realistic special class and demonstrate its polynomial solvability. Then, we propose a Branch-and-Bound algorithm and a Russian Doll Search algorithm using the assignment problem relaxations for lower bound computations, and introduce combinatorial branching rules based on the conflicting edges in an optimal solution of the relaxations. According to the extensive computational experiments we can say that the proposed algorithms are very efficient. (C) 2019 Elsevier Ltd. All rights reserved.
Keyword:
Assignment problem
Integer programming
Branch-and-bound
Conflicts
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
Hydrothermal preparation and low temperature magnetic properties of TbOOH, DyOOH, HoOOH, ErOOH, and YbOOHTbOOH，DyOOH，HoOOH，ErOOH和YbOOH的水热制备和低温磁性
PREAI
分享收藏The transportation problem with exclusionary side constraints and two branch-and-bound algorithms具有排除侧约束的运输问题和两个分支定界算法
PREAI
分享收藏A follow-up survey of berth allocation and quay crane scheduling problems in container terminals
PREAI
分享收藏A survey of berth allocation and quay crane scheduling problems in container terminals集装箱码头泊位分配和码头起重机调度问题的调查
PREAI
分享收藏
查看更多内容