mixed-integer linear programming

Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

  • Björn Geißler
  • Antonio Morsi
  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more

    Bulk Ship Fleet Renewal and Deployment under Uncertainty: A Multi-Stage Stochastic Programming Approach

  • Ayse Nur Arslan
  • Dimitri J. Papageorgiou
    • Categories Stochastic Programming, Supply Chain Management, Transportation Tags , , , , ,

    We study a maritime fleet renewal and deployment problem under demand and charter cost uncertainty. A decision-maker for an industrial bulk shipping company must determine a suitable fleet size, mix, and deployment strategy to satisfy stochastic demand over a given planning horizon. She may acquire vessels in two ways: time chartering and voyage chartering. Time … Read more

    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