Research Interests

Refereed Journal Publications:

  1. Kabakulak, B., Taşkın, Z.C. & Pusane, A.E. (2021), "A Branch-Price-and-Cut Algorithm for Optimal Decoding of LDPC Codes," Forthcoming in Journal of Global Optimization.
    [Abstract] [BibTeX] [PDF]
  2. Abstract: Channel coding aims to minimize the errors that occur during the transmission of digital information from one place to another. Low-density parity-check codes can detect and correct transmission errors if one encodes the original information by adding redundant bits. In practice, heuristic iterative decoding algorithms are used to decode the received vector. However, these algorithms may fail to decode if the received vector contains multiple errors. We consider decoding the received vector with minimum error as an integer programming (IP) problem and propose a branchand-price method for its solution. We improve the performance of our method by introducing heuristic feasible solutions and adding valid cuts to the mathematical formulation. Our computational experiments reveal that our branch-cut-and-price algorithm significantly improves solvability of the problem compared to a state-ofthe-art IP decoder in the literature and has superior error performance than the conventional sum-product algorithm.

    BibTeX:
    @article{,
      author = {Banu Kabakulak and Z. C. Ta\c{s}k{\i}n and Ali Emre Pusane},
      title = {A Branch-Price-and-Cut Algorithm for Optimal Decoding of LDPC Codes},
      journal = {Forthcoming in Journal of Global Optimization},
      year = {2021}
    }
    
  3. Kalay, S. & Taşkın, Z.C. (2021), "A branch-and-price algorithm for parallel machine campaign planning under sequence dependent family setups and co-production," Computers & Operations Research. Vol. 135
    [Abstract] [BibTeX] [DOI] [PDF]
  4. Abstract: We investigate a tactical level production planning problem in process industries under costly sequence dependent family setups, which drives the need for manufacturing of product families in campaigns. The motivation of our work is float glass manufacturing, which has some unique properties such as co-production and uninterruptible production. To solve the problem, we develop a branch-and-price algorithm based on a novel formulation of the problem. Our algorithm is capable of providing consistent performance in different problem sizes. We compare our proposed algorithm with previous work on the same problem by running computational experiments.

    BibTeX:
    @article{KalayTaskin2021b,
      author = {Serkan Kalay and Z. Caner Ta\c{s}k{\i}n},
      title = {A branch-and-price algorithm for parallel machine campaign planning under sequence dependent family setups and co-production},
      journal = {Computers & Operations Research},
      year = {2021},
      volume = {135},
      doi = {https://doi.org/10.1016/j.cor.2021.105430}
    }
    
  5. Seker, O., Ekim, T. & Taşkın, Z.C. (2021), "An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs," European Journal of Operational Research. Vol. 291(1), pp. 67-83 .
    [Abstract] [BibTeX] [DOI] [PDF]
  6. Abstract: We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy signicantly improves the solvability of the problem.

    BibTeX:
    @article{SekerEtAl2021,
      author = {Oylum Seker and T{\i}naz Ekim and Z. Caner Ta\c{s}k{\i}n},
      title = {An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs},
      journal = {European Journal of Operational Research},
      year = {2021},
      volume = {291(1)},
      pages = {67--83 },
      doi = {https://doi.org/10.1016/j.ejor.2020.09.017}
    }
    
  7. Kalay, S. & Taşkın, Z.C. (2021), "Single Machine Campaign Planning under Sequence Dependent Family Setups and Co-Production," Forthcoming in Journal of the Operational Research Society.
    [Abstract] [BibTeX] [DOI] [PDF]
  8. Abstract: We investigate tactical level production planning problem in process industries, with float glass manufacturing being the specific application domain. In the presence of high sequence dependent family setup costs, the need for planning production in batches, or campaigns as named in the float glass industry, arises. Moreover, the float glass manufacturing has some unique properties such as partially controllable co-production and uninterruptible production. The motivation of our work is a real life problem encountered at a major float glass manufacturing company in Turkey. We develop two mixed integer programming formulations and investigate some variants to solve the problem. Our formulations are capable of handling different resolutions in input data such as demand forecast expressed in discrete time and setup durations expressed in continuous time. We compare formulations both theoretically and by running computational experiments. Furthermore, we conduct additional experiments to gain insights about characteristics of the generated campaign plans from a business perspective.

    BibTeX:
    @article{KalayTaskin2021a,
      author = {Serkan Kalay and Z. Caner Ta\c{s}k{\i}n},
      title = {Single Machine Campaign Planning under Sequence Dependent Family Setups and Co-Production},
      journal = {Forthcoming in Journal of the Operational Research Society},
      year = {2021},
      doi = {https://doi.org/10.1080/01605682.2020.1772016}
    }
    
  9. Kucukasci, E.S., Baydogan, M.G. & Taşkın, Z.C. (2021), "A Linear Programming Approach to Multiple Instance Learning," Turkish Journal of Electrical Engineering & Computer Sciences. Vol. 29, pp. 2186-2201.
    [Abstract] [BibTeX] [DOI] [PDF]
  10. Abstract: Multiple instance learning (MIL) aims to classify objects with complex structures and covers a wide range of real-world data mining applications. In MIL, objects are represented by a bag of instances instead of a single instance and class labels are provided only for the bags. Some of the earlier MIL methods focus on solving MIL problem under the standard MIL assumption, which requires at least one positive instance in positive bags and all remaining instances are negative. This study proposes a linear programming framework to learn instance level contributions to bag label without emposing the standart assumption. Each instance of a bag is mapped to a pseudo-class membership estimate and these estimates are aggregated to obtain the bag-level class membership in an optimization framework. A simple linear mapping enables handling various MIL assumptions with adjusting instance contributions. Our experiments with instance-dissimilarity based data representations verify the effectiveness of the proposed MIL framework. Proposed mathematical models can be solved efficiently in polynomial time.

    BibTeX:
    @article{KucukasciEtAl2021,
      author = {Emel Seyma Kucukasci and Mustafa Gokce Baydogan and Z. Caner Ta\c{s}k{\i}n},
      title = {A Linear Programming Approach to Multiple Instance Learning},
      journal = {Turkish Journal of Electrical Engineering & Computer Sciences},
      year = {2021},
      volume = {29},
      pages = {2186--2201},
      doi = {https://doi.org/10.3906/elk-2009-144}
    }
    
  11. Unal, A.T., Ağralı, S. & Taşkın, Z.C. (2020), "A strong integer programming formulation for hybrid flowshop scheduling," Journal of the Operational Research Society. Vol. 71(12), pp. 2042-2052.
    [Abstract] [BibTeX] [DOI] [PDF]
  12. Abstract: We consider a hybrid flowshop scheduling problem that includes parallel unrelated discrete machines or batch processing machines in different stages of a production system. The problem is motivated by a bottleneck process within the production system of a transformer producer located in the Netherlands. We develop an integer programming model that minimises the total tardiness of jobs over a finite planning horizon. Our model is applicable to a wide range of production systems organised as hybrid flowshops. We strengthen our integer program by exploiting special properties of some constraints in our formulation. We develop a decision support system (DSS) based on our proposed optimisation model. We compare the results of our initial optimisation model with an improved formulation as well as with a heuristic that was in use at the company before the implementation of our DSS. Our results show that the improved optimisation model significantly outperforms the heuristic and the initial optimisation model in terms of both the solution time and the strength of its linear programming relaxation.

    BibTeX:
    @article{UnalEtAl2020,
      author = {A. Tamer Unal and Semra A\u{g}ral{\i} and Z. Caner Ta\c{s}k{\i}n},
      title = {A strong integer programming formulation for hybrid flowshop scheduling},
      journal = {Journal of the Operational Research Society},
      year = {2020},
      volume = {71},
      number = {12},
      pages = {2042--2052},
      doi = {https://doi.org/10.1080/01605682.2019.1654414}
    }
    
  13. Aydin, M.A. & Taşkın, Z.C. (2020), "Decentralized Decomposition Algorithms for Peer-to-Peer Linear Optimization," RAIRO-Operations Research. Vol. 54(6), pp. 1835-1861.
    [Abstract] [BibTeX] [DOI] [PDF]
  14. Abstract: We propose Decentralized Benders Decomposition and Decentralized Dantzig-Wolfe Decomposition algorithms for large-scale block angular linear programming problems. Our methods allow multiple peer decision makers to cooperate with the aim of solving the problem without the need of a central coordination mechanism. Instead we achieve cooperation by partial information sharing across a strongly connected communication network. Our main goal is to design decentralized solution approaches for decision makers who are unwilling to disclose their local data, but want to solve the global problem collaboratively for mutual benefit. We prove that our proposed methods reach global optimality in a finite number of iterations. We confirm our theoretical results with computational experiments.

    BibTeX:
    @article{AydinTaskin2020,
      author = {M. Asli Aydin and Z. Caner Ta\c{s}k{\i}n},
      title = {Decentralized Decomposition Algorithms for Peer-to-Peer Linear Optimization},
      journal = {RAIRO-Operations Research},
      year = {2020},
      volume = {54},
      number = {6},
      pages = {1835--1861},
      doi = {https://doi.org/10.1051/ro/2019097}
    }
    
  15. Kabakulak, B., Taşkın, Z.C. & Pusane, A.E. (2020), "A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems," Networks. Vol. 75(2), pp. 137-157.
    [Abstract] [BibTeX] [DOI] [PDF]
  16. 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 xing 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.

    BibTeX:
    @article{KabakulakEtAl2020,
      author = {Banu Kabakulak and Z. C. Ta\c{s}k{\i}n and Ali Emre Pusane},
      title = {A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems},
      journal = {Networks},
      year = {2020},
      volume = {75},
      number = {2},
      pages = {137--157},
      doi = {https://doi.org/10.1002/net.21914}
    }
    
  17. Sarıduman, A., Pusane, A.E. & Taşkın, Z.C. (2020), "On the Construction of Regular QC-LDPC Codes with Low Error Floor," IEEE Communications Letters. Vol. 24(1), pp. 25-28.
    [Abstract] [BibTeX] [DOI] [PDF]
  18. Abstract: Quasi-cyclic low-density (QC-LDPC) codes benefit from efficient encoding hardware and display excellent error correcting performance. Therefore, they have been accepted into the 5G standards in addition to being potential candidates for next generation mobile systems. However, dominant trapping sets in the Tanner graphs cause some failures for the iterative decoding algorithm. In this paper, we propose a simulated annealing based method to find regular QC-LDPC codes without dominant trapping sets and have good error floor performance. Simulation results show that our proposed method generates QC-LDPC codes that have the best trapping sets distribution among recent works and better frame rate performance than others.

    BibTeX:
    @article{SaridumanEtAl2020,
      author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z. Caner Ta\c{s}k{\i}n},
      title = {On the Construction of Regular QC-LDPC Codes with Low Error Floor},
      journal = {IEEE Communications Letters},
      year = {2020},
      volume = {24},
      number = {1},
      pages = {25--28},
      doi = {https://doi.org/10.1109/LCOMM.2019.2953058}
    }
    
  19. Dursun, P., Taşkın, Z.C., Altinel, I.K., Bilge, H., Kesen, N.D., Okutan, M. & Oral, E.N. (2019), "A column generation heuristic for VMAT treatment planning with adaptive CVaR constraints," Physics in Medicine and Biology. Vol. 64(20), pp. 205024.
    [Abstract] [BibTeX] [DOI] [PDF]
  20. Abstract: In this study we develop an ecient computational procedure that generates medically acceptable treatment plans for volumetric modulated arc therapy with constant gantry speed. Our proposed method is a column generation heuristic based on a mixed integer linear programming model, where the objective function contains minimization of total monitor unit of the treatment plan and dose-volume requirements are included as conditional value-at-risk constraints. Our heuristic generates a full treatment arc for the restricted master problem and calibrates the right hand side parameters of the conditional value-at-risk constraints in the first phase. In the second phase, this initial solution is improved by performing column generation. This is a fully automated procedure and produces treatment plans in a single call without any human intervention. We evaluate its performance on real prostate cancer data by comparing the quality of the generated plans with those obtained by a widely used commercial treatment planning system. Our analysis shows that the results are promising, and the generated plans satisfy the prescription restrictions and require 22% fewer monitor units on average compared to the ones obtained using Eclipse.

    BibTeX:
    @article{DursunEtAl2019c,
      author = {Pinar Dursun and Z. Caner Ta\c{s}k{\i}n and I. Kuban Altinel and Hatice Bilge and Nazmiye Donmez Kesen and Murat Okutan and Ethem Nezih Oral},
      title = {A column generation heuristic for VMAT treatment planning with adaptive CVaR constraints},
      journal = {Physics in Medicine and Biology},
      year = {2019},
      volume = {64},
      number = {20},
      pages = {205024},
      doi = {https://doi.org/10.1088/1361-6560/ab416e}
    }
    
  21. Kabakulak, B., Taşkın, Z.C. & Pusane, A.E. (2019), "Optimization-Based Decoding Algorithms for LDPC Convolutional Codes in Communication Systems," IISE Transactions. Vol. 51(10), pp. 1061-1074.
    [Abstract] [BibTeX] [DOI] [PDF]
  22. Abstract: In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Lowdensity paritycheck (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programmingbased exact and heuristic decoding algorithms for its solution. In particular, we consider relax-and-fix heuristics that decode information in small windows. Computational results indicate that our approaches identify nearoptimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.

    BibTeX:
    @article{KabakulakEtAl2019,
      author = {Banu Kabakulak and Z. C. Ta\c{s}k{\i}n and Ali Emre Pusane},
      title = {Optimization-Based Decoding Algorithms for LDPC Convolutional Codes in Communication Systems},
      journal = {IISE Transactions},
      year = {2019},
      volume = {51},
      number = {10},
      pages = {1061--1074},
      doi = {https://doi.org/10.1080/24725854.2018.1550692}
    }
    
  23. Dursun, P., Taşkın, Z.C. & Altinel, I.K. (2019), "Using Branch-and-Price to Determine Optimal Treatment Plans for Volumetric Modulated Arc Therapy (VMAT)," Computers & Operations Research. Vol. 110, pp. 1-17.
    [Abstract] [BibTeX] [DOI] [PDF]
  24. 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.

    BibTeX:
    @article{DursunEtAl2019b,
      author = {Pinar Dursun and Z. Caner Ta\c{s}k{\i}n and I. Kuban Altinel},
      title = {Using Branch-and-Price to Determine Optimal Treatment Plans for Volumetric Modulated Arc Therapy (VMAT)},
      journal = {Computers & Operations Research},
      year = {2019},
      volume = {110},
      pages = {1--17},
      doi = {https://doi.org/10.1016/j.cor.2019.05.018}
    }
    
  25. Altınel, İ.K., Aras, N., Suvak, Z. & Taşkın, Z.C. (2019), "Minimum Cost Noncrossing Flow Problem on Layered Networks," Discrete Applied Mathematics. Vol. 261, pp. 2-21.
    [Abstract] [BibTeX] [DOI] [PDF]
  26. 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.

    BibTeX:
    @article{AltinelEtAl2019,
      author = {\.{I}. K. Alt{\i}nel and N. Aras and Z. Suvak and Z. C. Ta\c{s}k{\i}n},
      title = {Minimum Cost Noncrossing Flow Problem on Layered Networks},
      journal = {Discrete Applied Mathematics},
      year = {2019},
      volume = {261},
      pages = {2--21},
      doi = {https://doi.org/10.1016/j.dam.2018.09.016}
    }
    
  27. Seker, O., Ekim, T. & Taşkın, Z.C. (2019), "A Decomposition Approach to Solve the Selective Graph Coloring Problem in Some Perfect Graph Families," Networks. Vol. 73(2), pp. 145-169.
    [Abstract] [BibTeX] [DOI] [PDF]
  28. 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.

    BibTeX:
    @article{SekerEtAl2019,
      author = {Oylum Seker and T{\i}naz Ekim and Z. Caner Ta\c{s}k{\i}n},
      title = {A Decomposition Approach to Solve the Selective Graph Coloring Problem in Some Perfect Graph Families},
      journal = {Networks},
      year = {2019},
      volume = {73},
      number = {2},
      pages = {145--169},
      doi = {https://doi.org/10.1002/net.21850}
    }
    
  29. Dursun, P., Taşkın, Z.C. & Altinel, I.K. (2019), "The Determination of Optimal Treatment Plans for Volumetric Modulated Arc Therapy (VMAT)," European Journal of Operational Research. Vol. 272(1), pp. 372-388.
    [Abstract] [BibTeX] [DOI] [PDF]
  30. 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's body and the beam is shaped by a multi-leaf collimator mounted on the linear accelerator'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.

    BibTeX:
    @article{DursunEtAl2019,
      author = {Pinar Dursun and Z. Caner Ta\c{s}k{\i}n and I. Kuban Altinel},
      title = {The Determination of Optimal Treatment Plans for Volumetric Modulated Arc Therapy (VMAT)},
      journal = {European Journal of Operational Research},
      year = {2019},
      volume = {272},
      number = {1},
      pages = {372--388},
      doi = {https://doi.org/10.1016/j.ejor.2018.06.023}
    }
    
  31. Gungor, M., Unal, A.T. & Taşkın, Z.C. (2018), "A parallel machine lot-sizing and scheduling problem with a secondary resource and cumulative demand," International Journal of Production Research. Vol. 56(9), pp. 3344-3357.
    [Abstract] [BibTeX] [DOI] [PDF]
  32. Abstract: We investigate a parallel machine multi-item lot-sizing and scheduling problem with a secondary resource, in which demands are given for the entire planning horizon rather than for every single period. All-or-nothing assumption of the discrete lot-sizing and scheduling problem is valid so that a machine is either idle or works at full capacity in a period. The objective is to minimise the number of setups and teardowns. We prove that the problem is NP-hard, and present two equivalent formulations. We show some properties of the optimal objective value, give optimality conditions, and suggest a heuristic algorithm. We discuss and formulate two possible extensions related to real-life applications. Finally, we carry out computational experiments to compare the two formulations, to determine the effect of our proposed modeling improvements on solution performance, and to test the quality of our heuristic.

    BibTeX:
    @article{GungorEtAl2018,
      author = {Murat Gungor and A. Tamer Unal and Z. Caner Ta\c{s}k{\i}n},
      title = {A parallel machine lot-sizing and scheduling problem with a secondary resource and cumulative demand},
      journal = {International Journal of Production Research},
      year = {2018},
      volume = {56},
      number = {9},
      pages = {3344--3357},
      doi = {https://doi.org/10.1080/00207543.2017.1406675}
    }
    
  33. Ahat, B., Ekim, T. & Taşkın, Z.C. (2018), "Integer Programming Formulations and Benders Decomposition for Maximum Induced Matching Problem," INFORMS Journal on Computing. Vol. 30(1), pp. 43-56.
    [Abstract] [BibTeX] [DOI] [PDF]
  34. Abstract: We investigate the Maximum Induced Matching problem (MIM), which is the problem of finding an induced matching having the largest cardinality on an undirected graph. The problem is known to be NP-hard for general graphs. We first propose a vertex-based integer programming formulation for MIM, which is more compact compared to an edge-based formulation found in the literature. We also introduce the Maximum Weight Induced Matching problem (MWIM), which generalizes MIM so that vertices and edges have weights. We adapt the edge-based formulation to MWIM, and propose a quadratic programming formulation of MWIM based on our vertex-based formulation. We then linearize our quadratic programming formulation, and devise a Benders decomposition algorithm that exploits a special structure of the linearized formulation. We also propose valid inequalities and formulation tightening procedures to improve the efficiency of our approach. Our computational tests on a large suite of randomly generated graphs show that our vertex-based formulation and decomposition approach significantly improve the solvability of MIM and MWIM, especially on dense graphs.

    BibTeX:
    @article{AhatEtAl2018,
      author = {Betul Ahat and Tinaz Ekim and Z. Caner Ta\c{s}k{\i}n},
      title = {Integer Programming Formulations and Benders Decomposition for Maximum Induced Matching Problem},
      journal = {INFORMS Journal on Computing},
      year = {2018},
      volume = {30},
      number = {1},
      pages = {43--56},
      doi = {https://doi.org/10.1287/ijoc.2017.0764}
    }
    
  35. Taşkın, Z.C. & Smith, J.C. (2017), "Branch-cut-price algorithms for solving a class of search problems on general graphs," Networks. Vol. 70(1), pp. 4-18.
    [Abstract] [BibTeX] [DOI] [PDF]
  36. Abstract: We consider graph search problems involving an intruder and mobile searchers. The graph consists of nodes on which the intruder and searchers may be located, and edges on which these entities travel. Associated with each node is a set of nodes that are visible from that node. The goal is to find the minimum number of searchers needed to detect the intruder within a given time limit. We investigate three variants of the graph search problem: (i) a hide-and-seek problem, in which a stationary intruder 'hides' at an unknown node, (ii) a pursuit-evasion problem, in which the intruder moves among the nodes to avoid being detected, and (iii) a patrol problem, which is similar to the pursuit-evasion problem except that searchers patrol the graph in repeated circuits to seek intruders. Our contribution provides exponential-size set-covering formulations for these problems, along with a class of branch-cut-price algorithms tailored for solving them. These algorithms leverage results from the orienteering literature to solve pricing problems related to searcher routes.

    BibTeX:
    @article{TaskinSmith2017,
      author = {Z. Caner Ta\c{s}k{\i}n and J. Cole Smith},
      title = {Branch-cut-price algorithms for solving a class of search problems on general graphs},
      journal = {Networks},
      year = {2017},
      volume = {70},
      number = {1},
      pages = {4-18},
      doi = {https://doi.org/10.1002/net.21740}
    }
    
  37. Ağralı, S., Taşkın, Z.C. & Unal, A.T. (2017), "Employee Scheduling in Service Industries with Flexible Employee Availability and Demand," Omega. Vol. 66, pp. 159-169.
    [Abstract] [BibTeX] [DOI] [PDF]
  38. Abstract: We consider an employee scheduling problem arising in service industries with flexible employee availability and flexible demand. In the system to be planned, there is a given set of service requirements and a set of employees at any time. Each employee belongs to one of various skill levels, each service requirement specifies the requested employee skill level and the timing of the service delivery, and each requirement has a weight that indicates the importance of that requirement. Employees have individual flexible contracts with the organization, which are characterized by weekly/monthly contracted work hours, days the employee is available for work and availability of overtime. Furthermore, there are regulations on maximum work hours and minimum rest requirements of employees enforced by the government and the labor union. The problem that we investigate is to generate an assignment of employees to service requirements which (i) ensures that the maximum weighted number of service requirements is met, (ii) satisfies government and labor union regulations, (iii) honors individual employee contracts with minimum deviation from the contracted work hours, and (iv) ensures a fair balance between employee schedules in terms of work assignments on holidays. We model the problem as a mixed-integer programming problem and discuss a reformulation strategy, which allows us to solve practical problems in a reasonable amount of time. We also report our experience in a large health-care organization in Belgium.

    BibTeX:
    @article{AgraliEtAl2017,
      author = {Semra A\u{g}ral{\i} and Z. Caner Ta\c{s}k{\i}n and A. Tamer Unal},
      title = {Employee Scheduling in Service Industries with Flexible Employee Availability and Demand},
      journal = {Omega},
      year = {2017},
      volume = {66},
      pages = {159--169},
      doi = {https://doi.org/10.1016/j.omega.2016.03.001}
    }
    
  39. Türkoğulları, Y.B., Taşkın, Z.C., Aras, N. & Altınel, İ.K. (2016), "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals," European Journal of Operational Research. Vol. 254(3), pp. 985-1001.
    [Abstract] [BibTeX] [DOI] [PDF]
  40. Abstract: There has been a dramatic increase in world's container traffic during the last thirty years. As a consequence, the efficient management of container terminals has become a crucial issue. In this work we concentrate on the integrated seaside operations, namely the integration of berth allocation, quay crane assignment and quay crane scheduling problems. First, we formulate a mixed-integer linear program whose exact solution gives optimal berthing positions and berthing times of the vessels, along with their crane schedules during their stay at the quay. Then, we propose an efficient cutting plane algorithm based on a decomposition scheme. Our approach deals with berthing positions of the vessels and their assigned number of cranes in each time period in a master problem, and seeks the corresponding optimal crane schedule by solving a subproblem. We prove that the crane scheduling subproblem is NP-complete under general cost settings, but can be solved in polynomial time for certain special cases. Our computational study shows that our new formulation and proposed solution method yield optimal solutions for realistic-sized instances.

    BibTeX:
    @article{TurkogullariEtAl2016,
      author = {Y. B. T\"{u}rko\u{g}ullar{\i} and Z. C. Ta\c{s}k{\i}n and N. Aras and \.{I}. K. Alt{\i}nel},
      title = {Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals},
      journal = {European Journal of Operational Research},
      year = {2016},
      volume = {254},
      number = {3},
      pages = {985--1001},
      doi = {https://doi.org/10.1016/j.ejor.2016.04.022}
    }
    
  41. Taşkın, Z.C., Ağralı, S., Unal, A.T., Belada, V. & Gokten-Yilmaz, F. (2015), "Mathematical Programming-Based Sales and Operations Planning at Vestel Electronics," INFORMS Journal on Applied Analytics. Vol. 45(4), pp. 325-340.
    [Abstract] [BibTeX] [DOI] [PDF]
  42. Abstract: We investigate the sales and operations planning (S&OP) problem at Vestel Electronics, a major television manufacturer located in Turkey. The company's product portfolio is very wide due to a large number of configuration options, and changes rapidly due to technological advances. Demand volatility is high and materials procurement requires long lead times. Hence, the S&OP process is critical for efficient management of company resources and its supply chain as well as customer satisfaction. We devise a mathematical programming formulation for Vestel's S&OP problem and describe our experience in implementation of a decision support system (DSS) based on our optimization model. We have fully implemented and deployed our DSS at Vestel, and Vestel has been using it on a daily basis since 2011.

    BibTeX:
    @article{TaskinEtAl2015,
      author = {Z. Caner Ta\c{s}k{\i}n and Semra A\u{g}ral{\i} and A. Tamer Unal and Vahdet Belada and Filiz Gokten-Yilmaz},
      title = {Mathematical Programming-Based Sales and Operations Planning at Vestel Electronics},
      journal = {INFORMS Journal on Applied Analytics},
      year = {2015},
      volume = {45},
      number = {4},
      pages = {325--340},
      doi = {https://doi.org/10.1287/inte.2015.0793}
    }
    
  43. Goren, M. & Taşkın, Z.C. (2015), "A column generation approach for evaluating delivery efficiencies of collimator technologies in IMRT treatment planning," Physics in Medicine and Biology. Vol. 60(5), pp. 1989-2004.
    [Abstract] [BibTeX] [DOI] [PDF]
  44. Abstract: Collimator systems used in Intensity Modulated Radiation Therapy (IMRT) can form different geometric aperture shapes depending on their physical capabilities. We compare the efficiency of using regular, rotating and dual multileaf collimator (MLC) systems under different combinations of consecutiveness, interdigitation and rectangular constraints. We also create a virtual freeform collimator, which can form any possible segment shape by opening or closing each bixel independently, to provide a basis for comparison. We formulate the problem of minimizing beam-on time as a large-scale linear programming problem. To deal with its dimensionality, we propose a column generation approach. We demonstrate the efficacy of our approach on a set of clinical problem instances. Our results indicate that the dual MLC under consecutiveness constraint yields very similar beam-on time to a virtual freeform collimator. Our approach also provides a ranking between other collimator technologies in terms of their delivery efficiencies.

    BibTeX:
    @article{GorenTaskin2015,
      author = {Merve Goren and Z. Caner Ta\c{s}k{\i}n},
      title = {A column generation approach for evaluating delivery efficiencies of collimator technologies in IMRT treatment planning},
      journal = {Physics in Medicine and Biology},
      year = {2015},
      volume = {60},
      number = {5},
      pages = {1989--2004},
      doi = {https://doi.org/10.1088/0031-9155/60/5/1989}
    }
    
  45. Sarıduman, A., Pusane, A.E. & Taşkın, Z.C. (2014), "An Integer Programming-Based Search Technique for Error-Prone Substructures of LDPC Codes," AEU - International Journal of Electronics and Communications. Vol. 68(11), pp. 1097-1105.
    [Abstract] [BibTeX] [DOI] [PDF]
  46. Abstract: In this paper, an efficient, general framework is presented for finding common, devastating error-prone structures (EPS) of any finite-length low-density parity-check (LDPC) code. The smallest stopping set for the binary erasure channel (BEC), the smallest fully absorbing set, the smallest absorbing set, and the smallest elementary trapping set for the binary symmetric channel (BSC) are found and the dominant EPS are enumerated. The method involves integer programming optimization techniques, which guarantees that the results are provably optimal.

    BibTeX:
    @article{SaridumanEtAl2014,
      author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z. Caner Ta\c{s}k{\i}n},
      title = {An Integer Programming-Based Search Technique for Error-Prone Substructures of LDPC Codes},
      journal = {AEU - International Journal of Electronics and Communications},
      year = {2014},
      volume = {68},
      number = {11},
      pages = {1097--1105},
      doi = {https://doi.org/10.1016/j.aeue.2014.05.012}
    }
    
  47. Türkoğulları, Y.B., Taşkın, Z.C., Aras, N. & Altınel, İ.K. (2014), "Optimal berth allocation and time-invariant quay crane assignment in container terminals," European Journal of Operational Research. Vol. 235(1), pp. 88-101.
    [Abstract] [BibTeX] [DOI] [PDF]
  48. Abstract: Due to the dramatic increase in the world's container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.

    BibTeX:
    @article{TurkogullariEtAl2014,
      author = {Y. B. T\"{u}rko\u{g}ullar{\i} and Z. C. Ta\c{s}k{\i}n and N. Aras and \.{I}. K. Alt{\i}nel},
      title = {Optimal berth allocation and time-invariant quay crane assignment in container terminals},
      journal = {European Journal of Operational Research},
      year = {2014},
      volume = {235},
      number = {1},
      pages = {88--101},
      doi = {https://doi.org/10.1016/j.ejor.2013.10.015}
    }
    
  49. Bodur, M., Ekim, T. & Taşkın, Z.C. (2013), "Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem," Networks. Vol. 62(4), pp. 273-287.
    [Abstract] [BibTeX] [DOI] [PDF]
  50. Abstract: We investigate the problem of finding a maximal matching that has minimum total weight on a given edge-weighted graph. Although the minimum weight maximal matching problem is NP-hard in general, polynomial time exact or approximation algorithms on several restricted graph classes are given in the literature. In this paper, we propose an exact algorithm for solving several variants of the problem on general graphs. In particular, we develop integer programming formulations for the problem and devise a decomposition algorithm, which is based on a combination of integer programming techniques and combinatorial matching algorithms. Our computational tests on a large suite of randomly generated graphs show that our decomposition approach significantly improves the solvability of the problem compared to the underlying integer programming formulation.

    BibTeX:
    @article{BodurEtAl2013,
      author = {Merve Bodur and T{\i}naz Ekim and Z. Caner Ta\c{s}k{\i}n},
      title = {Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem},
      journal = {Networks},
      year = {2013},
      volume = {62},
      number = {4},
      pages = {273--287},
      doi = {https://doi.org/10.1002/net.21516}
    }
    
  51. Taşkın, Z.C. & Cevik, M. (2013), "Combinatorial Benders Cuts for Decomposing IMRT Fluence Maps Using Rectangular Apertures," Computers & Operations Research. Vol. 40(9), pp. 2178-2186.
    [Abstract] [BibTeX] [DOI] [PDF]
  52. Abstract: We consider the problem of decomposing Intensity Modulated Radiation Therapy (IMRT) fluence maps using rectangular apertures. A fluence map can be represented as an integer matrix, which denotes the intensity profile to be delivered to a patient through a given beam angle. We consider IMRT treatment machinery that can form rectangular apertures using conventional jaws, and hence, do not need sophisticated multi-leaf collimator (MLC) devices. The number of apertures used to deliver the fluence map needs to be minimized in order to treat the patient efficiently. From a mathematical point of view, the problem is equivalent to a minimum cardinality matrix decomposition problem. We propose a combinatorial Benders decomposition approach to solve this problem to optimality. We demonstrate the efficacy of our approach on a set of test instances derived from actual clinical data. We also compare our results with the literature and solutions obtained by solving a mixed-integer programming formulation of the problem.

    BibTeX:
    @article{TaskinCevik2013,
      author = {Z. Caner Ta{\c{s}}k{\i}n and Mucahit Cevik},
      title = {Combinatorial Benders Cuts for Decomposing IMRT Fluence Maps Using Rectangular Apertures},
      journal = {Computers & Operations Research},
      year = {2013},
      volume = {40(9)},
      pages = {2178--2186},
      doi = {https://doi.org/10.1016/j.cor.2011.07.005}
    }
    
  53. Ağralı, S., Geunes, J. & Taşkın, Z.C. (2012), "A Facility Location Model with Safety Stock Costs: Analysis of the Cost of Single-Sourcing Requirements," Journal of Global Optimization. Vol. 54(3), pp. 551-581.
    [Abstract] [BibTeX] [DOI] [PDF]
  54. Abstract: We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer's demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer's demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.

    BibTeX:
    @article{AgraliEtAl2012,
      author = {Semra A\u{g}ral{\i} and Joseph Geunes and Z. Caner Ta\c{s}k{\i}n},
      title = {A Facility Location Model with Safety Stock Costs: Analysis of the Cost of Single-Sourcing Requirements},
      journal = {Journal of Global Optimization},
      year = {2012},
      volume = {54(3)},
      pages = {551--581},
      doi = {https://doi.org/10.1007/s10898-011-9777-z}
    }
    
  55. Taşkın, Z.C. & Ekim, T. (2012), "Integer Programming Formulations for the Minimum Weighted Maximal Matching Problem," Optimization Letters. Vol. 6(6), pp. 1161-1171.
    [Abstract] [BibTeX] [DOI] [PDF]
  56. Abstract: Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.

    BibTeX:
    @article{TaskinEkim2012,
      author = {Z. Caner Ta\c{s}k{\i}n and T{\i}naz Ekim},
      title = {Integer Programming Formulations for the Minimum Weighted Maximal Matching Problem},
      journal = {Optimization Letters},
      year = {2012},
      volume = {6(6)},
      pages = {1161--1171},
      doi = {https://doi.org/10.1007/s11590-011-0351-x}
    }
    
  57. Taşkın, Z.C., Smith, J.C. & Romeijn, H.E. (2012), "Mixed-Integer Programming Techniques for Decomposing IMRT Fluence Maps Using Rectangular Apertures," Annals of Operations Research. Vol. 196(1), pp. 799-818.
    [Abstract] [BibTeX] [DOI] [PDF]
  58. Abstract: We consider a matrix decomposition problem arising in Intensity Modulated Radiation Therapy (IMRT). The problem input is a matrix of intensity values that are to be delivered to a patient via IMRT from some given angle, under the condition that the IMRT device can only deliver radiation in rectangular shapes. This paper studies the problem of minimizing the number of rectangles (and their associated intensities) necessary to decompose such a matrix. We propose an integer programming-based methodology for providing lower and upper bounds on the optimal solution, and demonstrate the efficacy of our approach on actual clinical data.

    BibTeX:
    @article{TaskinEtAl2012,
      author = {Z. Caner Ta\c{s}k{\i}n and J. Cole Smith and H. Edwin Romeijn},
      title = {Mixed-Integer Programming Techniques for Decomposing IMRT Fluence Maps Using Rectangular Apertures},
      journal = {Annals of Operations Research},
      year = {2012},
      volume = {196(1)},
      pages = {799--818},
      doi = {https://doi.org/10.1007/s10479-010-0767-1}
    }
    
  59. Taşkın, Z.C., Smith, J.C., Romeijn, H.E. & Dempsey, J.F. (2010), "Optimal Multileaf Collimator Leaf Sequencing in IMRT Treatment Planning," Operations Research. Vol. 58(3), pp. 674-690.
    [Abstract] [BibTeX] [DOI] [PDF]
  60. Abstract: We consider a problem dealing with the efficient delivery of Intensity Modulated Radiation Therapy (IMRT) to individual patients. IMRT treatment planning is usually performed in three phases. The first phase determines a set of beam angles through which radiation is delivered, followed by a second phase that determines an optimal radiation intensity profile (or fluence map). This intensity profile is selected to ensure that certain targets receive a required amount of dose while functional organs are spared. In order to deliver these intensity profiles to the patient, a third phase must decompose them into a collection of apertures and corresponding intensities. In this paper, we investigate this last problem. Formally, an intensity profile is represented as a nonnegative integer matrix; an aperture is represented as a binary matrix whose ones appear consecutively in each row. A feasible decomposition is one in which the original desired intensity profile is equal to the sum of a number of feasible binary matrices multiplied by corresponding intensity values. In order to most efficiently treat a patient, we wish to minimize a measure of total treatment time, which is given as a weighted sum of the number of apertures and the sum of the aperture intensities used in the decomposition. We develop the first exact algorithm capable of solving real-world problem instances to optimality within practicable computational limits, using a combination of integer programming decomposition and combinatorial search techniques. We demonstrate the efficacy of our approach on a set of 25 test instances derived from actual clinical data and on 100 randomly generated instances.

    BibTeX:
    @article{TaskinEtAl2010a,
      author = {Z. Caner Ta\c{s}k{\i}n and J. Cole Smith and H. Edwin Romeijn and James F. Dempsey},
      title = {Optimal Multileaf Collimator Leaf Sequencing in IMRT Treatment Planning},
      journal = {Operations Research},
      year = {2010},
      volume = {58},
      number = {3},
      pages = {674--690},
      doi = {https://doi.org/10.1287/opre.1090.0759}
    }
    
  61. Taşkın, Z.C., Smith, J.C., Ahmed, S. & Schaefer, A.J. (2009), "Cutting Plane Algorithms for Solving a Stochastic Edge-Partition Problem," Discrete Optimization. Vol. 6(4), pp. 420-435.
    [Abstract] [BibTeX] [DOI] [PDF]
  62. Abstract: We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.

    BibTeX:
    @article{TaskinEtAl2009a,
      author = {Z. Caner Ta\c{s}k{\i}n and J. Cole Smith and Shabbir Ahmed and Andrew J. Schaefer},
      title = {Cutting Plane Algorithms for Solving a Stochastic Edge-Partition Problem},
      journal = {Discrete Optimization},
      year = {2009},
      volume = {6},
      number = {4},
      pages = {420--435},
      doi = {https://doi.org/10.1016/j.disopt.2009.05.004}
    }
    
  63. Taşkın, Z.C. & Unal, A.T. (2009), "Tactical Level Planning in Float Glass Manufacturing with Co-Production, Random Yields and Substitutable Products," European Journal of Operational Research. Vol. 199(1), pp. 252-261.
    [Abstract] [BibTeX] [DOI] [PDF]
  64. Abstract: We investigate tactical level planning problems in float glass manufacturing. Float glass manufacturing is a process that has some unique properties such as uninterruptible production, random yields, partially controllable co-production compositions, complex relationships in sequencing of products, and substitutable products. Furthermore, changeover times and costs are very high, and production speed depends significantly on the product mix. These characteristics render measurement and management of the production capacity difficult. The motivation for this study is a real life problem faced at Trakya Cam in Turkey. Trakya Cam has multiple geographically separated production facilities. Since transportation of glass is expensive, logistics costs are high. In this paper, we consider multi-site aggregate planning, and color campaign duration and product mix planning. We develop a decision support system based on several mixed-integer linear programming models in which production and transportation decisions are made simultaneously. The system has been fully implemented, and has been in use at Trakya Cam since 2005.

    BibTeX:
    @article{TaskinUnal2009,
      author = {Z. Caner Ta\c{s}k{\i}n and A. Tamer Unal},
      title = {Tactical Level Planning in Float Glass Manufacturing with Co-Production, Random Yields and Substitutable Products},
      journal = {European Journal of Operational Research},
      year = {2009},
      volume = {199},
      number = {1},
      pages = {252--261},
      doi = {https://doi.org/10.1016/j.ejor.2008.11.024}
    }
    
  65. Men, C., Romeijn, H.E., Taşkın, Z.C. & Dempsey, J.F. (2007), "An Exact Approach to Direct Aperture Optimization in IMRT Treatment Planning," Physics in Medicine and Biology. Vol. 52(24), pp. 7333-7352.
    [Abstract] [BibTeX] [DOI] [PDF]
  66. Abstract: We consider the problem of intensity-modulated radiation therapy (IMRT) treatment planning using direct aperture optimization. While this problem has been relatively well studied in recent years, most approaches employ a heuristic approach to the generation of apertures. In contrast, we use an exact approach that explicitly formulates the fluence map optimization (FMO) problem as a convex optimization problem in terms of all multileaf collimator (MLC) deliverable apertures and their associated intensities. However, the number of deliverable apertures, and therefore the number of decision variables and constraints in the new problem formulation, is typically enormous. To overcome this, we use an iterative approach that employs a subproblem whose optimal solution either provides a suitable aperture to add to a given pool of allowable apertures or concludes that the current solution is optimal. We are able to handle standard consecutiveness, interdigitation and connectedness constraints that may be imposed by the particular MLC system used, as well as jaws-only delivery. Our approach has the additional advantage that it can explicitly account for transmission of dose through the part of an aperture that is blocked by the MLC system, yielding a more precise assessment of the treatment plan than what is possible using a traditional beamlet-based FMO problem. Finally, we develop and test two stopping rules that can be used to identify treatment plans of high clinical quality that are deliverable very efficiently. Tests on clinical head-and-neck cancer cases showed the efficacy of our approach, yielding treatment plans comparable in quality to plans obtained by the traditional method with a reduction of more than 75% in the number of apertures and a reduction of more than 50% in beam-on time, with only a modest increase in computational effort. The results also show that delivery efficiency is very insensitive to the addition of traditional MLC constraints; however, jaws-only treatment requires about a doubling in beam-on time and number of apertures used. Finally, we showed the importance of accounting for transmission effects when assessing or, preferably, optimizing treatment plan quality.

    BibTeX:
    @article{MenEtAl2007,
      author = {Chunhua Men and H. Edwin Romeijn and Z. Caner Ta\c{s}k{\i}n and James F. Dempsey},
      title = {An Exact Approach to Direct Aperture Optimization in IMRT Treatment Planning},
      journal = {Physics in Medicine and Biology},
      year = {2007},
      volume = {52},
      number = {24},
      pages = {7333--7352},
      doi = {https://doi.org/10.1088/0031-9155/52/24/009}
    }
    

Data:

Book Chapters:

  1. Seker, O., Heggernes, P., Ekim, T. & Taşkın, Z.C. (2017), "Linear-time generation of random chordal graphs," In Lecture Notes in Computer Science. Springer.
    [Abstract] [BibTeX] [DOI] [PDF]
  2. Abstract: Chordal graphs form one of the most well studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is based on the ``intersection of subtrees of a tree" characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. The complexity of our algorithm is linear in the size of the produced graph. We give test results to show the variety of chordal graphs that are produced, and we compare these results to existing results.

    BibTeX:
    @incollection{SekerEtAl2017,
      author = {Oylum Seker and Pinar Heggernes and Tinaz Ekim and Z. Caner Ta\c{s}k{\i}n},
      title = {Linear-time generation of random chordal graphs},
      booktitle = {Lecture Notes in Computer Science},
      publisher = {Springer},
      year = {2017},
      doi = {http://doi.org/10.1007/978-3-319-57586-5_37}
    }
    
  3. Teksan, Z.M., Unal, A.T. & Taşkın, Z.C. (2012), "Integrated Production Planning, Shift Planning, and Detailed Scheduling in a Tissue Paper Manufacturer," In Models, Algorithms, and Technologies for Network Analysis. Springer.
    [BibTeX] [DOI] [PDF]
  4. BibTeX:
    @incollection{TeksanUnalTaskin2012,
      author = {Zehra Melis Teksan and A. Tamer Unal and Z. Caner Ta\c{s}k{\i}n},
      title = {Integrated Production Planning, Shift Planning, and Detailed Scheduling in a Tissue Paper Manufacturer},
      booktitle = {Models, Algorithms, and Technologies for Network Analysis},
      publisher = {Springer},
      year = {2012},
      doi = {http://doi.org/10.1007/978-1-4614-5574-5_9}
    }
    
  5. Taşkın, Z.C. (2010), "Benders Decomposition," In J. J. Cochran (Editor), Encyclopedia of Operations Research and Management Science. Wiley.
    [Abstract] [BibTeX] [DOI] [PDF]
  6. Abstract: Benders decomposition is a solution method for solving certain large-scale
    optimization problems. Instead of considering all decision variables
    and constraints of a large-scale problem simultaneously, Benders
    decomposition partitions the problem into multiple smaller problems.
    Since computational difficulty of optimization problems increases
    significantly with the number of variables and constraints, solving
    these smaller problems iteratively can be more efficient than solving
    a single large problem. In this chapter, we first formally describe
    Benders decomposition. We then briefly describe some extensions and
    generalizations of Benders decomposition. We conclude our chapter
    by illustrating how the decomposition decomposition works on a problem
    encountered in Intensity Modulated Radiation Therapy (IMRT) treatment
    planning and giving a numerical example.

    BibTeX:
    @incollection{Taskin2010,
      author = {Z. Caner Ta\c{s}k{\i}n},
      title = {Benders Decomposition},
      booktitle = {Encyclopedia of Operations Research and Management Science},
      editor = {J. J. Cochran},
      publisher = {Wiley},
      year = {2010},
      doi = {http://doi.org/10.1002/9780470400531.eorms0104}
    }
    
  7. Smith, J.C. & Taşkın, Z.C. (2008), "A Tutorial Guide to Mixed-Integer Programming Models and Solution Techniques," In G. J. Lim and E. K. Lee (Editor), Optimization in Medicine and Biology. January 2008. Taylor and Francis, Auerbach Publications.
    [Abstract] [BibTeX] [PDF]
  8. Abstract: Mixed-integer programming theory provides a mechanism for optimizing
    decisions that take place in complex systems, including those encountered
    in biology and medicine. This chapter is intended for researchers
    and practitioners wanting an introduction to the field of mixed-integer
    programming. We begin by discussing basic mixed-integer programming
    formulation principles and tricks, especially with regards to the
    use of binary variables to form logical statements. We then discuss
    two core techniques, branch-and-bound and cutting-plane algorithms,
    used to solve mixed-integer programs. We illustrate the use of mixed-integer
    programming in the context of several medical applications, and close
    with a featured study on Intensity Modulated Radiation Therapy planning.

    BibTeX:
    @incollection{SmithTaskin2007,
      author = {J. Cole Smith and Z. Caner Ta\c{s}k{\i}n},
      title = {A Tutorial Guide to Mixed-Integer Programming Models and Solution Techniques},
      booktitle = {Optimization in Medicine and Biology},
      editor = {G. J. Lim and E. K. Lee},
      publisher = {Taylor and Francis, Auerbach Publications},
      school = {Department of Industrial and Systems Engineering, University of Florida},
      year = {2008}
    }
    

Conference Proceedings:

  1. Dursun, P., Taşkın, Z.C. & Altinel, I.K. (2016), "Mathematical Models for Optimal Volumetric Modulated Arc Therapy (VMAT) Treatment Planning," In Procedia Computer Science. Volume 100, pp. 644 - 651.
    [Abstract] [BibTeX] [DOI] [PDF]
  2. Abstract: Volumetric Modulated Arc Therapy (VMAT) is an external radiation treatment method, during which the gantry of the linear accelerator (linac) may rotate on one or more arc and send radiation continuously. A multileaf collimator (MLC) is mounted in the linac head in order to shape the radiation beam. These properties make VMAT powerful in obtaining high conformal plans in terms of dose distribution. However, there is interdependency between apertures that are composed by the MLC, and this makes the VMAT planning hard. In this study, we present two mixed integer linear programming models and compare them with respect to their total solution times and quality.

    BibTeX:
    @incollection{Dursun2016,
      author = {Pinar Dursun and Z. Caner Ta\c{s}k{\i}n and I. Kuban Altinel},
      title = {Mathematical Models for Optimal Volumetric Modulated Arc Therapy (VMAT) Treatment Planning},
      booktitle = {Procedia Computer Science},
      journal = {Procedia Computer Science},
      year = {2016},
      volume = {100},
      pages = {644 -- 651},
      doi = {http://doi.org/10.1016/j.procs.2016.09.206}
    }
    
  3. Sarıduman, A., Pusane, A.E. & Taşkın, Z.C. (2016), "A heuristic method for adaptive linear programming decoding," In Proceedings of Signal Processing and Communications Applications (SIU 2016).
    [BibTeX] [PDF]
  4. BibTeX:
    @incollection{SaridumanEtAl2016,
      author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z. Caner Ta\c{s}k{\i}n},
      title = {A heuristic method for adaptive linear programming decoding},
      booktitle = {Proceedings of Signal Processing and Communications Applications (SIU 2016)},
      year = {2016}
    }
    
  5. Altinel, I.K., Turkogullari, Y.B., Taşkın, Z.C. & Aras, N. (2015), "Optimal Berth Allocation, Time-variant Quay Crane Assignment and Scheduling with Crane Setups in Container Terminals," In Proceedings of The 2015 International Conference on Logistics and Maritime Systems (LOGMS 2015).
    [BibTeX] [PDF]
  6. BibTeX:
    @incollection{AltinelEtAl2015,
      author = {I. Kuban Altinel and Yavuz B. Turkogullari and Z. Caner Ta\c{s}k{\i}n and Necati Aras},
      title = {Optimal Berth Allocation, Time-variant Quay Crane Assignment and Scheduling with Crane Setups in Container Terminals},
      booktitle = {Proceedings of The 2015 International Conference on Logistics and Maritime Systems (LOGMS 2015)},
      year = {2015}
    }
    
  7. Sarıduman, A., Pusane, A.E. & Taşkın, Z.C. (2014), "Adaptive Linear Programming for Decoding LDPC Codes," In Proceedings of Signal Processing and Communications Applications (SIU 2014).
    [BibTeX] [PDF]
  8. BibTeX:
    @incollection{SaridumanEtAl2014a,
      author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z. Caner Ta\c{s}k{\i}n},
      title = {Adaptive Linear Programming for Decoding LDPC Codes},
      booktitle = {Proceedings of Signal Processing and Communications Applications (SIU 2014)},
      year = {2014}
    }
    
  9. Aras, N., Turkogullari, Y., Taşkın, Z.C. & Altinel, K. (2012), "Simultaneous Optimization of Berth Allocation, Quay Crane Assignment and Quay Crane Scheduling Problems in Container Terminals," In Proceedings of International Annual Conference of the German Operations Research Society (OR 2012).
    [Abstract] [BibTeX] [PDF]
  10. Abstract: In this work, we focus on the integrated planning of the following problems faced within the context of seaside operations at container terminals: berth allocation, quay crane assignment, and quay crane scheduling. First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment problems called BACAP. Then we extend it by incorporating the crane scheduling problem as well, which is named BACASP. Although the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality, only small instances for BACASP can be solved optimally. To be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a postprocessing algorithm. We also develop a cutting plane algorithm
    for the case where this condition is not satisfied. This algorithm solves BACAP repeatedly by adding cuts generated from the optimal solutions at each trial until the aforementioned condition holds.

    BibTeX:
    @incollection{ArasEtAl2012,
      author = {Necati Aras and Yavuz Turkogullari and Z. Caner Ta\c{s}k{\i}n and Kuban Altinel},
      title = {Simultaneous Optimization of Berth Allocation, Quay Crane Assignment and Quay Crane Scheduling Problems in Container Terminals},
      booktitle = {Proceedings of International Annual Conference of the German Operations Research Society (OR 2012)},
      year = {2012}
    }
    
  11. Teksan, Z.M., Unal, A.T. & Taşkın, Z.C. (2012), "A Mixed Integer Programming Based Solution Methodology for a Scheduling Problem in Tissue Paper Manufacturing," In Proceedings of 13th International Conference on Project Management and Scheduling (PMS 2012). Springer.
    [BibTeX] [PDF]
  12. BibTeX:
    @incollection{TeksanEtAl2012,
      author = {Zehra Melis Teksan and A. Tamer Unal and Z. Caner Ta\c{s}k{\i}n},
      title = {A Mixed Integer Programming Based Solution Methodology for a Scheduling Problem in Tissue Paper Manufacturing},
      booktitle = {Proceedings of 13th International Conference on Project Management and Scheduling (PMS 2012)},
      publisher = {Springer},
      year = {2012}
    }
    
  13. Sarıduman, A., Pusane, A.E. & Taşkın, Z.C. (2012), "An integer programming based trapping set search technique," In Proceedings of Signal Processing and Communications Applications (SIU 2012).
    [Abstract] [BibTeX] [PDF]
  14. Abstract: Near codewords of low-density parity-check (LDPC) codes are known to be one of the main reasons of errors that occur in decoding. For high signal-to-noise ratios, these codewords cause error floors in decoding and they are called trapping sets. Especially, trapping sets with small size devastate the performance of communication systems that use LDPC codes. Unfortunately, trapping sets are difficult to find since they satisfy almost all of the parity check equations. In this paper, we develop an integer programming based optimization approach to find the smallest trapping set. Moreover, we develop an algorithm to determine the smallest bit set that belongs to the smallest trapping set and causes an oscillation in the decoder.

    BibTeX:
    @incollection{SaridumanEtAl2012,
      author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z. Caner Ta\c{s}k{\i}n},
      title = {An integer programming based trapping set search technique},
      booktitle = {Proceedings of Signal Processing and Communications Applications (SIU 2012)},
      year = {2012}
    }