Integer Programming

Compact mixed-integer programming relaxations in quadratic optimization

  • Ben Beach
  • Robert Hildebrand
  • Joey Huchette
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization

    We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in … Read more

    On Generating Lagrangian Cuts for Two-stage Stochastic Integer Programs

  • Rui Chen
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We investigate new methods for generating Lagrangian cuts to solve two-stage stochastic integer programs. Lagrangian cuts can be added to a Benders reformulation, and are derived from solving single scenario integer programming subproblems identical to those used in the nonanticipative Lagrangian dual of a stochastic integer program. While Lagrangian cuts have the potential to significantly … Read more

    A study of the relation between the single-row and the double-row facility layout problem

  • Mirko Dahlbeck
  • Anja Fischer
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Facility Planning and Design Tags , ,

    The NP-hard Multi-Row Facility Layout Problem (MRFLP) consists of a set of one-dimensional departments and pairwise transport weights between them. It asks for a non-overlapping arrangement of the departments along a given number of rows such that the weighted sum of the horizontal center-to-center distances between the departments is minimized. We mainly focus on the … Read more

    Sparse Poisson regression via mixed-integer optimization

  • Kota Kudo
  • Yuichi Takano
  • Hiroki Saishu
    • Categories Integer Programming, Statistics Tags , , ,

    We present a mixed-integer optimization (MIO) approach to sparse Poisson regression. The MIO approach to sparse linear regression was first proposed in the 1970s, but has recently received renewed attention due to advances in optimization algorithms and computer hardware. In contrast to many sparse estimation algorithms, the MIO approach has the advantage of finding the … Read more

    Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets: Theory and Computation

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming

    We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more

    Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate … Read more

    Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems

  • Lena Hupp
  • Frauke Liers
  • Manu Kapolke
  • Alexander Martin
  • Robert Weismantel
    • Categories (Mixed) Integer Linear Programming, Airline Optimization, Combinatorial Optimization Tags , , ,

    The running time for solving a mixed-integer linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally … Read more

    Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories Cutting Plane Approaches, Game Theory, Polyhedra Tags , ,

    Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more

    On the Complexity of Inverse Mixed Integer Linear Optimization

  • A Bulut
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    Inverse optimization is the problem of determining the values of missing input parameters that are closest to given estimates and that will make a given solution optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILPs) to both the original problem and the separation problem associated with … Read more

    Stochastic Inventory Routing with Time-based Shipment Consolidation

  • Danja R Sonntag
  • Albert H. Schrotenboer
  • Gudrun P Kiesmuller
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    Inspired by the retail industry, we introduce a fundamentally new approach towards stochastic inventory routing by replenishing retailers from a central warehouse using a time-based shipment consolidation policy. Such a time-based dispatching policy, where retailers facing stochastic demand are repetitively replenished at fixed times, is essential in practice. It allows for easy incorporation with dependent … Read more