(Mixed) Integer Linear Programming

Optimizing the lead time of operational flexibility trading from distributed industrial energy systems in future energy and flexibility markets

  • Daniel Bull
    • Categories (Mixed) Integer Linear Programming, Control Applications, Energy Tags , , , ,

    To meet the challenges of increasing volatile and distributed renewable energy generation in the electric grid, local flexibility and energy markets are currently investigated. These markets aim to encourage prosumers to trade their available flexible power locally, to be used if a grid congestion is being predicted. The markets are emerging, but the characterizing parameter … Read more

    The Overflowing Bin Packing Problem: Theoretical Results and a New Flow Formulation

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We consider a recently proposed one-dimensional packing problem, called the overflowing bin packing problem (OBPP). In this scenario, we are given a set of items (of known sizes) and a set of bins (of known capacities). Roughly speaking, the task is to assign the items to the bins in such a way that the total … Read more

    A new framework to generate Lagrangian cuts in multistage stochastic mixed-integer programming

  • Christian Füllner
  • Xu Andy Sun
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    Based on recent advances in Benders decomposition and two-stage stochastic integer programming we present a new generalized framework to generate Lagrangian cuts in multistage stochastic mixed-integer linear programming (MS-MILP). This framework can be incorporated into decomposition methods for MS-MILPs, such as the stochastic dual dynamic integer programming (SDDiP) algorithm. We show how different normalization techniques … Read more

    On Lipschitz regularization and Lagrangian cuts in multistage stochastic mixed-integer linear programming

  • Christian Füllner
  • Xu Andy Sun
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    We provide new theoretical insight on the generation of linear and non-convex cuts for value functions of multistage stochastic mixed-integer programs based on Lagrangian duality. First, we analyze in detail the impact that the introduction of copy constraints, and especially, the choice of the accompanying constraint set for the copy variable have on the properties … Read more

    A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP

  • Suresh Bolusani
  • Gioni Mexi
  • Mathieu Besançon
  • Mark Turner
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and evaluation of MRENS in a full-fledged MILP solver, specifically coupled with the recently-introduced Lagromory separator for generating multiple reference solutions. Computational experiments on the MIPLIB 2017 benchmark set show that MRENS, … Read more

    BOBILib: Bilevel Optimization (Benchmark) Instance Library

  • Johannes Thürauf
  • Thomas Kleinert
  • Ivana Ljubić
  • Ted K. Ralphs
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Optimization Software Benchmark Tags , , , ,

    In this report, we present the BOBILib, a collection of more than 2500~instances of mixed integer linear bilevel optimization problems. The goal of this library is to make a large and well-curated set of test instances freely available for the research community so that new and existing algorithms in bilevel optimization can be tested and … Read more

    Exact Augmented Lagrangian Duality for Nonconvex Mixed-Integer Nonlinear Optimization

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , ,

    In the context of mixed-integer nonlinear problems (MINLPs), it is well-known that strong duality does not hold in general if the standard Lagrangian dual is used. Hence, we consider the augmented Lagrangian dual (ALD), which adds a nonlinear penalty function to the classic Lagrangian function. For this setup, we study conditions under which the ALD … Read more

    Inverse of the Gomory Corner Relaxation of Integer Programs

  • Fatemeh Nosrat
  • George Lyu
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Other Topics Tags , , ,

    We analyze the inverse of the Gomory corner relaxation (GCR) of a pure integer program (IP). We prove the inverse GCR is equivalent to the inverse of a shortest path problem, yielding a polyhedral representation of the GCR inverse-feasible region. We present a linear programming (LP) formulation for solving the inverse GCR under the \(L_{1}\) … Read more

    Exploiting Overlap Information in Chance-constrained Program with Random Right-hand Side

  • Wei Lv
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Xiao-Jiao Tong
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more