Assignment problem with conflicts

Temel Öncan (Corresponding author), Zeynep Şuvak, Hakan Akyuz, I. Kuban Altinel

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)214-229
Number of pages16
JournalComputers & Operations Research
Volume111
DOIs
Publication statusPublished - Nov 2019

Fingerprint

Assignment Problem
Branching Rules
Computational complexity
Perfect Matching
Branch and Bound Algorithm
Polynomials
Computational Experiments
Bipartite Graph
Search Algorithm
Solvability
Assignment
NP-complete problem
Optimal Solution
Binary
Lower bound
Restriction
Polynomial
Conflict
Assignment problem
Costs

Keywords

  • Assignment Problem
  • Integer programming
  • Branch and bound
  • Conflicts
  • Branch-and-bound
  • Assignment problem

Cite this

Öncan, Temel ; Şuvak, Zeynep ; Akyuz, Hakan ; Kuban Altinel, I. / Assignment problem with conflicts. In: Computers & Operations Research. 2019 ; Vol. 111. pp. 214-229.
@article{78a2be4e17e1494c8093b607891d3d35,
title = "Assignment problem with conflicts",
abstract = "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.",
keywords = "Assignment Problem, Integer programming, Branch and bound, Conflicts, Branch-and-bound, Assignment problem",
author = "Temel {\"O}ncan and Zeynep Şuvak and Hakan Akyuz and {Kuban Altinel}, I.",
year = "2019",
month = "11",
doi = "10.1016/j.cor.2019.07.001",
language = "English",
volume = "111",
pages = "214--229",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Elsevier",

}

Assignment problem with conflicts. / Öncan, Temel (Corresponding author); Şuvak, Zeynep; Akyuz, Hakan; Kuban Altinel, I.

In: Computers & Operations Research, Vol. 111, 11.2019, p. 214-229.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Assignment problem with conflicts

AU - Öncan, Temel

AU - Şuvak, Zeynep

AU - Akyuz, Hakan

AU - Kuban Altinel, I.

PY - 2019/11

Y1 - 2019/11

N2 - 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.

AB - 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.

KW - Assignment Problem

KW - Integer programming

KW - Branch and bound

KW - Conflicts

KW - Branch-and-bound

KW - Assignment problem

UR - http://www.scopus.com/inward/record.url?scp=85068505969&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2019.07.001

DO - 10.1016/j.cor.2019.07.001

M3 - Article

VL - 111

SP - 214

EP - 229

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -