Invited Session Fri.3.H 2033

Friday, 15:15 - 16:45 h, Room: H 2033

Cluster 11: Integer & mixed-integer programming [...]

Decomposition methods and applications


Chair: Joe Naoum-Sawaya



Friday, 15:15 - 15:40 h, Room: H 2033, Talk 1

Joe Naoum-Sawaya
A Benders decomposition approach for the critical node selection problem

Coauthor: Christoph Buchheim


In this presentation, we discuss the critical node selection problem where given an undirected graph the objective is to remove a given number of nodes in order to minimize the pairwise connections. The critical node selection problem has several important applications arising in supply chain, telecommunication, and in healthcare. To solve large scale instances, we consider the integer programming formualtion and propose a Benders decomposition algorithm for its solution. The Benders decomposition approach is implemented in a branch-and-cut algorithm. We also discuss alternative quadratic reformulations and derive valid inequalities.



Friday, 15:45 - 16:10 h, Room: H 2033, Talk 2

Emre Celebi
An approximation algorithm for Benders decomposition of variational inequality problems


In this talk, we examine an approximate solution of the master problem in Benders decomposition method for large-scale equilibrium models formulated as VI problems. We have used exact or approximate analytic center cutting plane method (ACCPM) within the Benders decomposition of VI problems in order to reduce the computational effort. ACCPM allows for adding another cut to the Benders master problem along with the cut obtained from the dual information of the subproblem. This cut can be calculated (or approximated) from the analytic center of the feasible region of the master problem at each iteration of Benders decomposition. This approach may lead to improvements in the speed of the algorithm compared to the original Benders or Dantzig-Wolfe decomposition of VI problems. A realistic electricity market price simulation model is used to test the algorithm and preliminary results are presented.



Friday, 16:15 - 16:40 h, Room: H 2033, Talk 3

Kerem Akartunali
Radiation treatment planning for volumetric modulated arc therapy (VMAT): Optimization and heuristics

Coauthor: Vicky Mak-Hau


Volumetric-modulated arc therapy (VMAT) is a recent technological development in the area of cancer radiation treatment, where the aim is the generation of a treatment plan involving decisions of appropriate radiation dosages, angles and collimator shapes. The problem is computationally very challenging, in particular considering additional problem features such as time limitations. In this talk, we will discuss an integer programming formulation for this problem, and improvements on this formulation using some linearization techniques and valid inequalities. We will present some polyhedral results, and also discuss a branching and column generation framework specifically designed for this problem. We will discuss some computational results, as well as possible future extensions.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Buy Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.