Integer Programming

Stochastically Constrained Simulation Optimization On Integer-Ordered Spaces: The cgR-SPLINE Algorithm

  • Kalyani Nagaraj
  • Raghu Pasupathy
    • Categories Global Optimization, Integer Programming, Stochastic Programming Tags , ,

    We consider the problem of identifying the solution(s) to an optimization problem whose domain is a subset of the integer lattice, and whose objective and constraint functions can only be observed using a stochastic simulation. Such problems seem particularly prevalent (see www.simopt.org) within service systems having capacity or service-level constraints. We present cgR-SPLINE — a … Read more

    A new lift-and-project operator

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a … Read more

    Adaptive Elective Surgery Planning Under Duration and Length-Of-Stay Uncertainty: A Robust Optimization Approach

  • Bjorn Berg
  • Saba Neyshabouri
    • Categories Cutting Plane Approaches, Robust Optimization, Scheduling Tags , , ,

    Scheduling elective surgeries is a complicated task due to the coupled effect of multiple sources of uncertainty and the impact of the proposed schedule on the downstream units. In this paper, we propose an adaptive robust optimization model to address the existing uncertainty in surgery duration and length-of-stay in the surgical intensive care unit. The … Read more

    A Study of Three-Period Ramp-Up Polytope

  • Deepak Rajan
  • Liu Sheng
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags ,

    We study the polyhedron of the unit commitment problem, and consider a relaxation involving the ramping constraints. We study the three-period ramp-up polytope, and describe the convex-hull using a new class of inequalities. Citation[1] J. Ostrowski, M. F. Anjos, and A. Vannelli, \Tight mixed integer linear programming formulations for the unit commitment problem,” Power Systems, … Read more

    Tight second-stage formulations in two-stage stochastic mixed integer programs

  • Manish Bansal
  • Kuo-Ling Huang
  • Sanjay Mehrotra
    • Categories Cutting Plane Approaches, Production and Logistics, Stochastic Programming Tags , , , , , ,

    We study two-stage stochastic mixed integer programs (TSS-MIPs) with integer variables in the second stage. We show that under suitable conditions, the second stage MIPs can be convexified by adding parametric cuts a priori. As special cases, we extend the results of Miller and Wolsey (Math Program 98(1):73-88, 2003) to TSS-MIPs. Furthermore, we consider second … Read more

    Divisive heuristic for modularity density maximization

  • Alberto Costa
  • Leo Liberti
  • Sergey Kushnarev
  • Zeyu Sun
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , , , ,

    In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. … Read more

    A multiplicative weights update algorithm for MINLP

  • Leo Liberti
  • Luca Mencarelli
  • Youcef Sahraoui
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We discuss an application of the well-known Multiplicative Weights Update (MWU) algorithm to non-convex and mixed-integer nonlinear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of … Read more

    Solving MIPs via Scaling-based Augmentation

  • Pierre Le Bodic
  • Marc E. Pfetsch
  • Sebastian Pokutta
  • Jeffrey W. Pavelka
    • Categories (Mixed) Integer Linear Programming Tags , ,

    Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a current iterate is augmented to a better solution or proved optimal. It is well known that the performance of these methods, i.e., number of iterations needed, can theoretically be improved by scaling methods. We extend these results by an … Read more

    A new family of facet defining inequalities for the maximum edge-weighted clique problem

  • Franklin Djeumou Fomeni
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches Tags , , , , ,

    This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the … Read more

    Integer Programming Approaches for Appointment Scheduling with Random No-shows and Service Durations

  • Ruiwei Jiang
  • Siqian Shen
  • Yiling Zhang
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming

    We consider a single-server scheduling problem given a fixed sequence of appointment arrivals with random no-shows and service durations. The probability distribution of the uncertain parameters is assumed to be ambiguous and only the support and first moments are known. We formulate a class of distributionally robust (DR) optimization models that incorporate the worst-case expectation/conditional … Read more