On Solving the Assignment Problem with Conflicts
Preprint
Abstract
A variant of the well-known Assignment Problem is studied in this paper, where pairs of assignments are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which models real applications, looks for a complete assignment that minimizes the total cost, while no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature, indicates that the approach we propose achieves results comparable with, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity. The solver adopted is also able to provide heuristic solutions quicker and better than the heuristic methods previously discussed in the literature.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASPComputers & Operations Research, 2024
- Parallel drone scheduling vehicle routing problems with collective dronesComputers & Operations Research, 2023
- Shortest paths with exclusive-disjunction arc pairs conflictsComputers & Operations Research, 2023
- Set covering problem with conflict constraintsComputers & Operations Research, 2022
- A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairsNetworks, 2020
- A multiethnic genetic approach for the minimum conflict weighted spanning tree problemNetworks, 2019
- Minimum spanning tree with conflicting edge pairs: a branch-and-cut approachAnnals of Operations Research, 2018
- A branch and cut algorithm for minimum spanning trees under conflict constraintsOptimization Letters, 2014
- The minimum cost perfect matching problem with conflict pair constraintsComputers & Operations Research, 2013
- The Hungarian Method for the Assignment Problem2009