Integer Programming

A unified mixed-integer programming model for simultaneous fluence weight and aperture optimization in VMAT, Tomotherapy, and Cyberknife

  • Kerem Akartunali
  • Vicky Mak-Hau
  • Thu Tran
    • Categories Biomedical Applications, Integer Programming

    In this paper, we propose and study a unified mixed-integer programming model that simultaneously optimizes fluence weights and multi-leaf collimator (MLC) apertures in the treatment planning optimization of VMAT, Tomotherapy, and CyberKnife. The contribution of our model is threefold: i. Our model optimizes the fluence and MLC apertures simultaneously for a given set of control … Read more

    A family of polytopes in the 0/1-cube with Gomory-Chvátal rank at least ((1+1/6)n – 4)

  • Can Kizilkale
    • Categories Combinatorial Optimization, Integer Programming Tags ,

    We provide a family of polytopes P in [0, 1]^n whose Gomory-Chvátal rank is at least ((1 + 1/6)n – 4). Citation Rutcor 640 Bartholomew Road Piscataway, NJ 08854-8003 , July,2012 Article Download View A family of polytopes in the 0/1-cube with Gomory-Chvátal rank at least ((1+1/6)n – 4)

    Mixed Integer Linear Programming Formulation Techniques

  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming

    A wide range of problems can be modeled as Mixed Integer Linear Programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result … Read more

    Polyhedral Aspects of Self-Avoiding Walks

  • Agnes Dittel
  • Armin Fügenschuh
  • Alexander Martin
    • Categories Cutting Plane Approaches, Polyhedra

    In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this … Read more

    Graver basis and proximity techniques for block-structured separable convex integer minimization problems

  • Raymond Hemmecke
  • Matthias Köppe
  • Robert Weismantel
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

    We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more

    A new warmstarting strategy for the primal-dual column generation method

  • Jacek Gondzio
  • Pablo Gonzalez-Brevis
    • Categories Cutting Plane Approaches, Linear Programming Tags , , , ,

    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson’s infinite group problem, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically, for deciding extremality in this important class of minimal valid functions. Article … Read more

    Aircraft deconfliction with speed regulation: new models from mixed-integer optimization

  • Sonia Cafieri
  • Nicolas Durand
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , , ,

    Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact … Read more

    A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more

    An Exact Algorithm for Quadratic Integer Minimization using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
  • Mauro Piacentini
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags ,

    We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima … Read more