@article {1426, title = {A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems}, journal = {Networks}, volume = {75}, year = {2020}, pages = {137-157}, abstract = {

Abstract We study a bipartite graph (BG) construction problem that arises in digital communication systems. In a digital communication system, information is sent from one place to another over a noisy communication channel using binary symbols (bits). The original information is encoded by adding redundant bits, which are then used to detect and correct errors that may have been introduced during transmission. Harmful structures, such as small cycles, severely deteriorate the error correction capability of a BG. We introduce an integer programming formulation to generate a BG for a given smallest cycle length. We propose a branch-and-cut algorithm for its solution and investigate the structural properties of the problem to derive valid inequalities and variable fixing rules. We also introduce heuristics to obtain feasible solutions for the problem. The computational experiments show that our algorithm can generate BGs without small cycles in an acceptable amount of time for practically relevant dimensions.

}, keywords = {bipartite graphs, branch-and-cut algorithm, integer programming, symmetry, telecommunications, valid inequalities}, doi = {https://doi.org/10.1002/net.21914}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21914}, author = {Banu Kabakulak and Z C Ta{\c s}k{\i}n and Pusane, Ali E.} } @article {1431, title = {A decomposition approach to solve the selective graph coloring problem in some perfect graph families}, journal = {Networks}, volume = {73}, year = {2019}, pages = {145-169}, abstract = {

Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two adjacent vertices receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the objective is to choose exactly one vertex per cluster so that, among all possible selections, the number of colors necessary to color the vertices in the selection is minimum. This study focuses on a decomposition based exact solution framework for selective coloring in some perfect graph families: in particular, permutation, generalized split, and chordal graphs where the selective coloring problem is known to be NP-hard. Our method combines integer programming techniques and combinatorial algorithms for the graph classes of interest. We test our method on graphs with different sizes and densities, present computational results and compare them with solving an integer programming formulation of the problem by CPLEX, and a state-of-the art algorithm from the literature. Our computational experiments indicate that our decomposition approach significantly improves solution performance in low-density graphs, and regardless of edge-density in the class of chordal graphs.

}, keywords = {chordal graphs, decomposition algorithm, generalized split graphs, integer programming, partition coloring, permutation graphs, selective graph coloring}, doi = {https://doi.org/10.1002/net.21850}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21850}, author = {{\c S}eker, Oylum and Ekim, Tinaz and Z C Ta{\c s}k{\i}n} } @article {1432, title = {The determination of optimal treatment plans for Volumetric Modulated Arc Therapy (VMAT)}, journal = {European Journal of Operational Research}, volume = {272}, year = {2019}, pages = {372-388}, abstract = {

The success of radiation therapy depends on the ability to deliver the proper amount of radiation to cancerous cells while protecting healthy tissues. As a natural consequence, any new treatment technology improves quality standards concerning primarily this issue. Similar to the widely used Intensity Modulated Radiation Therapy (IMRT), the radiation resource is outside of the patient{\textquoteright}s body and the beam is shaped by a multi-leaf collimator mounted on the linear accelerator{\textquoteright}s head during the state-of-the-art Volumetric Modulated Arc Therapy (VMAT) as well. However, unlike IMRT, the gantry of the accelerator may rotate along one or more arcs and deliver radiation continuously. This property makes VMAT powerful in obtaining high conformal plans in terms of dose distribution; but the apertures are interdependent and optimal treatment planning problem cannot be decomposed into simpler independent subproblems as a consequence. In this work, we consider optimal treatment planning problem for VMAT. First, we formulate a mixed-integer linear program minimizing total radiation dose intensity subject to clinical requirements embedded within the constraints. Then, we develop efficient solution procedures combining Benders decomposition with certain acceleration strategies. We investigate their performance on a large set of test instances obtained from an anonymous real prostate cancer data.

}, keywords = {algorithms, Benders decomposition, integer programming, Radiation therapy, VMAT}, issn = {0377-2217}, doi = {https://doi.org/10.1016/j.ejor.2018.06.023}, url = {https://www.sciencedirect.com/science/article/pii/S0377221718305514}, author = {P{\i}nar Dursun and Z C Ta{\c s}k{\i}n 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} } @article {1429, title = {Using branch-and-price to determine optimal treatment plans for volumetric modulated arc therapy (VMAT)}, journal = {Computers \& Operations Research}, volume = {110}, year = {2019}, pages = {1-17}, abstract = {

Volumetric Modulated Arc Therapy (VMAT) is the state-of-the-art technique for external radiation therapy treatment. In this method, radiation can be delivered continuously on one or more arcs during the rotation of the gantry of the linear accelerator. This property makes VMAT powerful in obtaining high conformal plans in terms of dose distribution within short treatment times. However, the apertures composed by the leaves of the multileaf collimator (MLC) system that shapes continuously the radiation are interdependent, which makes treatment planning hard. We propose a mixed integer linear programming model for VMAT planning problem and exact branch-and-price algorithms to solve it. The objective of the model is to minimize total radiation that is delivered to the patient, and pricing subproblem is decomposable by rows of the MLC and can be solved as a shortest path problem. We generate a large set of test instances from a real data set and evaluate the performance of the proposed branch-and-price algorithm. Computational results reveal that new algorithms are efficient and capable of finding optimal solutions for large problem instances.

}, keywords = {Branch-and-price, Column generation, integer programming, Radiation therapy, Shortest path problem, VMAT}, issn = {0305-0548}, doi = {https://doi.org/10.1016/j.cor.2019.05.018}, url = {https://www.sciencedirect.com/science/article/pii/S0305054819301315}, author = {P{\i}nar Dursun and Z C Ta{\c s}k{\i}n and I. Kuban Altinel} }