@article {1441, title = {Exact solution algorithms for the maximum flow problem with additional conflict constraints}, journal = {European Journal of Operational Research}, volume = {287}, year = {2020}, pages = {410-437}, abstract = {

We consider a variant of the maximum flow problem on a given directed graph where some arc pairs are incompatible or conflicting; in other words, they are not allowed to carry positive flow simultaneously. This problem, called the maximum flow problem with conflicts, is known to be strongly NP-hard. In this paper, we present mixed-integer linear programming formulations for the problem and develop exact solution methods based on Benders decomposition, branch-and-bound, and Russian Doll Search over the conflict graph which represents the conflict relations. The effectiveness of the proposed algorithms is tested on a large number of randomly generated instances. The results reveal that their performances are superior to solving the mixed-integer linear programming formulations with a commercial software.

}, keywords = {Benders decomposition, Branch-and-bound, Combinatorial optimization, Conflict, Maximum flow, Russian doll search}, issn = {0377-2217}, doi = {https://doi.org/10.1016/j.ejor.2020.04.001}, url = {https://www.sciencedirect.com/science/article/pii/S0377221720303192}, author = {Zeynep {\c S}uvak and I. Kuban Altinel and Necati Aras} } @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 {1434, title = {Minimum cost noncrossing flow problem on layered networks}, journal = {Discrete Applied Mathematics}, volume = {261}, year = {2019}, pages = {2-21}, abstract = {

In this work we focus on an extension of the minimum cost flow problem in layered networks. Feasible arc flows must satisfy a specific compatibility restriction in addition to flow balance and capacity restrictions. Namely, at most one of the crossing arcs is allowed to have positive flow on it. This variant of the minimum cost flow problem, which we call the minimum cost noncrossing flow problem, can frequently be encountered in real life. The determination of optimal temporal quay crane allocations to berthed vessels in container terminals, and optimal train schedules through the stations on the same railroad line are two examples. We first analyze the complexity of the problem and show that the noncrossing flow problem is in fact NP-complete in a layered network. Then, we introduce mixed-integer linear programming formulations and discuss a polynomially solvable special case. Next we show a sufficient condition for the existence of a crossing in an optimal solution, which can be used for preprocessing the arcs in order to reduce the problem size. Our computational experiments on a large test set show that our preprocessing algorithm can significantly reduce the number of arcs.

}, keywords = {integer programming, Layered networks, Network flows, Noncrossing flow}, issn = {0166-218X}, doi = {https://doi.org/10.1016/j.dam.2018.09.016}, url = {https://www.sciencedirect.com/science/article/pii/S0166218X18304815}, author = {I. Kuban Altinel and Necati Aras and Zeynep {\c S}uvak and Z C Ta{\c s}k{\i}n} } @mastersthesis {857, title = {Solving Integrated Berth Allocation And Crane Assignment Problem Using A Tabu Search Metaheuristic}, year = {2013}, author = {Zeynep {\c S}uvak} }