Integer Programming

Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service System Staffing and Scheduling with Arrival Rate Uncertainty

  • Merve Bodur
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    We study server scheduling in multiclass service systems under stochastic uncertainty in the customer arrival volumes. Common practice in such systems is to first identify staffing levels, and then determine schedules for the servers that cover these targets. We propose a new stochastic integer programming model that integrates these two decisions, which can yield lower … Read more

    PEBBL: An Object-Oriented Framework for Scalable Parallel Branch and Bound

  • Jonathan Eckstein
  • William E. Hart
  • Cynthia A. Phillips
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    PEBBL is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms in a message-passing parallel computing environment. Deriving application-speci c classes from PEBBL, one may create parallel branch-and-bound applications through a process focused on the unique aspects of the application, while relying on PEBBL for generic aspects of … Read more

    Exact Algorithms for Arc and Node Routing Problems

  • Rafael Martinelli
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Dynamic Programming

    Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has … Read more

    Mathematical Programming: Turing completeness and applications to software analysis

  • Leo Liberti
  • Fabrizio Marinelli
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Global Optimization Applications Tags , , ,

    Mathematical Programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of Mathematical Programming to … Read more

    Optimization Methods for Disease Prevention and Epidemic Control

  • Yan Deng
  • Siqian Shen
  • Yevgeniy Vorobeychik
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    This paper investigates problems of disease prevention and epidemic control (DPEC), in which we optimize two sets of decisions: (i) vaccinating individuals and (ii) closing locations, given respective budgets with the goal of minimizing the expected number of infected individuals after intervention. The spread of diseases is inherently stochastic due to the uncertainty about disease … Read more

    A pseudo-polynomial size formulation for 2-stage two-dimensional knapsack problems

  • Fabio Furini
  • Enrico Malaguti
    • Categories (Mixed) Integer Linear Programming Tags , ,

    Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum … Read more

    Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization

  • Dimitris Bertsimas
  • Angelos Georghiou
    • Categories Applications - OR and Management Sciences, Integer Programming, Robust Optimization Tags , ,

    In recent years, decision rules have been established as the preferred solution method for addressing computationally demanding, multistage adaptive optimization problems. Despite their success, existing decision rules (a) are typically constrained by their a priori design and (b) do not incorporate in their modeling adaptive binary decisions. To address these problems, we first derive the … Read more

    A novel passenger recovery approach for the integrated airline recovery problem

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Airline Optimization Tags , , ,

    Schedule disruptions require airlines to intervene through the process of recovery; this involves modifications to the planned schedule, aircraft routings, crew pairings and passenger itineraries. Passenger recovery is generally considered as the final stage in this process, and hence passengers experience unnecessarily large impacts resulting from flight delays and cancellations. Most recovery approaches considering passengers … Read more

    Exact and Heuristic Approaches for Directional Sensor Control

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Control Applications Tags , , ,

    Directional sensors are gaining importance due to applications, in- cluding surveillance, detection, and tracking. Such sensors have a limited fi eld-of-view and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with … Read more