In this paper, we address an extension of the classical two-dimensional bin packing (2BPP) that considers the spread of customer orders (2BPP-OS). The 2BPP-OS addresses a set of rectangular items, required from different customer orders, to be cut from a set of rectangular bins. All the items of a customer order are dispatched together to … Read more
\(\) Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many … Read more
Mixed-Integer Rounding (MIR) cuts are effective at improving the dual bound in Mixed-Integer Linear Programming (MIP). However, in practice, MIR cuts are separated heuristically rather than using optimization as the latter is prohibitively expensive. We present a hybrid cut generation framework in which we train a Machine Learning (ML) model to inform cut generation for … Read more
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
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
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
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
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
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
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