mixed-integer linear programming

Robust optimization of dose-volume metrics for prostate HDR-brachytherapy incorporating target- and OAR volume delineation uncertainties

  • Marleen Balvert
  • Dick den Hertog
  • Aswin Hoffmann
    • Categories Biomedical Applications, Robust Optimization Tags , , , ,

    In radiation therapy planning, uncertainties in target volume definition yield a risk of underdosing the tumor. The classical way to prevent this in the context of external beam radiotherapy (EBRT) has been to expand the clinical target volume (CTV) with an isotropic margin to obtain the planning target volume (PTV). However, the EBRT-based PTV concept … Read more

    The Power Edge Set problem

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Sonia Toubaline
    • Categories Applications - OR and Management Sciences Tags , , ,

    The automated real time control of an electrical network is achieved through the estimation of its state using Phasor Measurement Units (PMUs). Given an undirected graph representing the network, we study the problem of finding the minimum number of PMUs to place on the edges such that the graph is fully observed. This problem is … Read more

    Mixed Integer Second-Order Cone Programming for the Horizontal and Vertical Free-flight Planning Problem

  • Liana Amaya Moreno
  • Armin Fügenschuh
  • Anton Kaier
  • Amina Mollaysa
  • Swen Schlobach
  • Zhi Yuan
    • Categories Airline Optimization, Second-Order Cone Programming Tags , ,

    In the past, travel routes for civil passenger and cargo air traffic were aligned to the air traffic network (ATN). To resolve the network congestion problem, the free-flight system has recently been introduced in more and more regions around the globe, allowing flight operations to make full use of the four space-and-time dimensions. For the … Read more

    Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part II: Tight Upper Bounds

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Approximation Algorithms Tags , , ,

    We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds $1$ and $s$. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the … Read more

    Solving Vertex Coloring Problems as Maximum Weight Stable Set Problems

  • Denis Cornaz
  • Fabio Furini
  • Enrico Malaguti
    • Categories Graphs and Matroids, Integer Programming Tags , , ,

    In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set … Read more

    An MILP approach to Multi-location, Multi-Period Equipment Selection for Surface Mining with Case Studies

  • Christina Burt
  • Louis Caccetta
  • Leon Fouche
  • Palitha Welgama
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Production and Logistics Tags , ,

    In the surface mining industry, the Equipment Selection Problem involves choosing an appropriate fleet of trucks and loaders such that the long-term mine plan can be satisfied. An important characteristic for multi-location (multi-location and multi-dumpsite) mines is that the underlying problem is a multi-commodity flow problem. The problem is therefore at least as difficult as … Read more

    Tight and Compact MIP Formulation of Configuration-Based Combined-Cycle Units

  • Carlos M. Correa-Posada
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    Private investors, flexibility, efficiency and environmental requirements from deregulated markets have led the existence and building of a significant number of combined-cycle gas turbines (CCGTs) in many power systems. These plants represent a complicated optimization problem for the short-term planning unit commitment (UC) carried out by independent system operators due to their multiple operating configurations. … Read more

    How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic

  • Samuel Burer
  • Fatma Kılınç-Karzan
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , , , , ,

    A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l – x_j)(x_j – u) \le 0$ with $l < u$, equals the intersection ... Read more

    A Note on Linear On/Off Constraints

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags ,

    This note studies compact representations of linear on/off constraints in mixed-integer linear optimization. A characterization of the convex hull of linear disjunctions is given in the space of original variables. This result can improve formulations of mixed-integer linear programs featuring on/off constraints by reducing the integrality gap in a Branch and Bound approach. Citation @article{, … Read more

    Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations – a computational case study –

  • Andreas Bärmann
  • Andreas Heidt
  • Sebastian Pokutta
  • Alexander Martin
  • Christoph Thurner
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Second-Order Cone Programming Tags , , ,

    Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the … Read more