Exploiting user-supplied Decompositions inside Heuristics

Many mixed-integer models are sparse and can, therefore, usually be decomposed into weakly connected blocks. Such decompositions could be determined algorithmically or be specified by the user. We limit ourselves to the later, as the user usually has a very precise idea of which decomposition makes sense for structural reasons. In the present work, we … Read more

A Column Generation Approach for the Lexicographic Optimization of Intra-Hospital Transports

Over the last fewyears, the efficient design of processes in hospitals and medical facilities has received more and more attention, particularly when the improvement of the processes is aimed at relieving theworkload of medical staff. To this end,we have developed a method to determine optimal allocations of intra-hospital transports to hospital transport employees. When optimizing … Read more

A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

Lexicographic Branch-and-Bound Column Search

We present an exact generic method for solving the pricing problem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke … Read more

Benders-type Branch-and-Cut Algorithms for Capacitated Facility Location with Single-Sourcing

We consider the capacitated facility location problem with (partial) single-sourcing (CFLP-SS). A natural mixed integer formulation for the problem involves 0-1 variables x_j indicating whether faclility j is used or not and y_{ij} variables indicating the fraction of the demand of client i that is satisfied from facility j. When the x variables are fixed, … Read more

The SCIP Optimization Suite 8.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions

In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems … Read more

Presolving Linear Bilevel Optimization Problems

Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving … Read more

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems

In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis … Read more