Mathematical optimization for the inverse problem of intensity modulated radiation therapy

  • Yair Censor
    • Categories Biomedical Applications, Global Optimization Applications Tags , , , , ,

    In this tutorial we discuss modeling issues in intensity modulated radiation therapy, contrasting the continuous model with the fully-discretized one and considering feasibility formulations versus optimization setups. We review briefly some mathematical optimization techniques for IMRT. These include global optimization, multi-objective optimization, linear and mixed integer programming and projection methods. Citationin: J.R. Palta and T.R. … Read more

    Sharpening the Karush-John optimality conditions

  • Arnold Neumaier
  • Hermann Schichl
    • Categories Constrained Nonlinear Optimization Tags , ,

    A refined version of the Karush-John first order optimality conditions is presented which reduces the number of constraints for which a constraint qualification is needed. This version is a generalization both of the Karush-John conditions and of the first order optimality conditions for concave constraints. ArticleDownload View PDF

    Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more

    Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , ,

    We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear costs on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory capacities explicitly and give exact separation algorithms. We also give a … Read more

    The global optimization of Morse clusters by potential energy transformations

  • Jon P. K. Doye
  • Marco Locatelli
  • Robert H. Leary
  • Fabio Schoen
    • Categories Basic Sciences Applications, Biomedical Applications, Stochastic Approaches

    The Morse potential is a simple model pair potential that has a single parameter $\rho$ which determines the width of the potential well and allows a wide variety of materials to be modelled. Morse clusters provide a particularly tough test system for global optimization algorithms, and one that is highly relevant to methods that are … Read more

    Cover and pack inequalities for (mixed) integer programming

  • Alper Atamturk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among … Read more

    Lift-and-project ranks and antiblocker duality

  • Laszlo Liptak
  • Levent Tunçel
    • Categories Combinatorial Optimization Tags , , , , ,

    Recently, Aguilera et al.\ exposed a beautiful relationship between antiblocker duality and the lift-and-project operator proposed by Balas et al. We present a very short proof of their result that the \BCC-rank of the clique polytope is invariant under complementation. The proof of Aguilera et al. relies on their main technical result, which describes a … Read more

    Computational study of a cutting plane algorithm for University Course Timetabling

  • Pasquale Avella
  • Igor Vasil'ev
    • Categories Branch and Cut Algorithms, Scheduling Tags ,

    In this paper we describe a successful case-study where a Branch-and-Cut algorithm yields the \lq\lq optimal” solution of a real-world timetabling problem of University courses \emph{(University Course Timetabling problem)}. The problem is formulated as a \emph{Set Packing problem} with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing … Read more

    Asymptotic behavior of the central path for a special class of degenerate SDP problems

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \|X_{\cT}(\nu)\|, \|S_{\cT}(\nu)\| \} … Read more

    Approximating the Two-Level Facility Location Problem Via a Quasi-Greedy Approach

  • Jiawei Zhang
    • Categories Approximation Algorithms Tags , ,

    We propose a {\em quasi-greedy} algorithm for approximating the classical uncapacitated $2$-level facility location problem ($2$-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization $2$-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of … Read more