@article {1439, title = {Assignment problem with conflicts}, journal = {Computers \& Operations Research}, volume = {111}, year = {2019}, pages = {214-229}, 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, Branch-and-bound, Conflicts, integer programming}, issn = {0305-0548}, doi = {https://doi.org/10.1016/j.cor.2019.07.001}, url = {https://www.sciencedirect.com/science/article/pii/S0305054819301777}, author = {Temel {\"O}ncan and Zeynep {\c S}uvak and M. Hakan Aky{\"u}z and I. Kuban Altinel} } @article {57723058, title = {{The multi-commodity capacitated multi-facility Weber problem: heuristics and confidence intervals}}, journal = {Iie Transactions}, volume = {42}, year = {2010}, pages = {825{\textendash}841}, doi = {10.1080/0740817X.2010.491504}, author = {M. Hakan Aky{\"u}z and Temel {\"O}ncan and I. Kuban Altinel} } @article {4756711, title = {{A comparative analysis of several asymmetric traveling salesman problem formulations}}, journal = {Computers \& Operations Research}, volume = {36}, year = {2009}, pages = {637{\textendash}654}, doi = {10.1016/j.cor.2007.11.008}, author = {Temel {\"O}ncan and I. Kuban Altinel and Gilbert Laporte} } @book {47738327, title = {{Efficient Lower and Upper Bounds for the Multi-commodity Capacitated Multi-facility Weber Problem with Rectilinear Distances}}, series = {Logistik Management}, year = {2009}, doi = {10.1007/978-3-7908-2362-2_11}, author = {M. Hakan Aky{\"u}z and Temel {\"O}ncan and I. Kuban Altinel} } @article {4777890, title = {{Exact solution procedures for the balanced unidirectional cyclic layout problem}}, journal = {European Journal of Operational Research}, volume = {189}, year = {2008}, pages = {609{\textendash}623}, doi = {10.1016/j.ejor.2006.09.094}, author = {Temel {\"O}ncan and I. Kuban Altinel} }