Integer Programming

A Distributionally Robust Optimization Approach for Stochastic Elective Surgery Scheduling with Limited Intensive Care Unit Capacity

  • Rema Padman
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    In this paper, we study the decision process of assigning elective surgery patients to available surgical blocks in multiple operating rooms (OR) under random surgery durations, random postoperative length-of-stay in the intensive care unit (ICU), and limited capacity of ICU. The probability distributions of random parameters are assumed to be ambiguous, and only the mean … Read more

    Mining for diamonds – matrix generation algorithms for binary quadratically constrained quadratic problems

  • Enrico Bettiol
  • Immanuel M. Bomze
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more

    Combinatorial Acyclicity Models for Potential-based Flows

  • Oliver Habeck
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization Tags , , ,

    Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more

    An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs

  • Mark Karwan
  • Marco E. Lübbecke
  • Chase Murray
  • Zachary Steever
  • Junsong Yuan
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are employed … Read more

    An algorithm for assortment optimization under parametric discrete choice models

  • Andrea Lodi
  • Tien Mai
    • Categories 0-1 Programming, Applications - OR and Management Sciences Tags , , ,

    This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a parametric choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The … Read more

    Mixed-Integer Nonlinear Optimization for District Heating Network Expansion

  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , ,

    We present a mixed-integer nonlinear optimization model for computing the optimal expansion of an existing tree-shaped district heating network given a number of potential new consumers. To this end, we state a stationary and nonlinear model of all hydraulic and thermal effects in the pipeline network as well as nonlinear models for consumers and the … Read more

    A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

  • Suresh Bolusani
  • Stefano Coniglio
  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , , , ,

    We introduce a unified framework for the study of multilevel mixed integer linear optimization problems and multistage stochastic mixed integer linear optimization problems with recourse. The framework highlights the common mathematical structure of the two problems and allows for the development of a common algorithmic framework. Focusing on the two-stage case, we investigate, in particular, … Read more

    A Framework for Generalized Benders’ Decomposition and Its Application to Multilevel Optimization

  • Suresh Bolusani
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , ,

    We describe an algorithmic framework generalizing the well-known framework originally introduced by Benders. We apply this framework to several classes of optimization problems that fall under the broad umbrella of multilevel/multistage mixed integer linear optimization problems. The development of the abstract framework and its application to this broad class of problems provides new insights and … Read more

    High Dimensional Three-Periods Locally Ideal MIP Formulations for the UC Problem

  • Beihua Fang
  • Wei Li
  • Yan Xu
  • Linfeng Yang
  • Cuo Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Energy, Scheduling Tags , , , ,

    The thermal unit commitment (UC) problem often can be formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale instances. The tighter characteristic re-duces the search space, therefore, as a natural conse-quence, significantly reduces the computational burden. In the literature, many tightened formulations for single units with parts … Read more

    2×2-convexifications for convex quadratic optimization with indicator variables

  • Shaoning Han
  • Andrés Gómez
  • Alper Atamturk
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive … Read more