Registration

Opening remarks

Nadia Brauner – TBA

TBA

Break

Johannes Thürauf – Adjustable Robust Mixed-Integer Nonlinear Network Design

We study network design problems for nonlinear and nonconvex flow models without controllable elements under load scenario uncertainties, i.e., under uncertain injections and withdrawals. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, load scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all load scenario uncertainties, if and only if a finite number of worst-case load scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future load fluctuations.

Alexandra Lassota – Integer Programs meet Fixed-Parameter Tractability

Solving Integer Programs (IPs) is generally NP-hard. But this does not imply that all instances are inherently hard. In fact, a substantial body of research has focused on identifying tractable subclasses and developing efficient (fixed-parameter tractable) algorithms for those. This talk will give a little overview of some of the key results and techniques.

Lunch break

Elina Rönnberg – Accelerating branch-and-price by heuristic pricing for integrality

In branch-and-price algorithms, the generation of new columns is made as part of solving LP relaxations and not with the integer program explicitly in mind. Instead, the responsibility to find integer solutions is delegated to the branching and cut generation, with an implicit impact on the pricing. When designing heuristics to accelerate branch-and-price by finding high-quality integer solutions early in the solution process, columns for LP relaxations are not necessarily useful. An interesting question is therefore how to price for columns that are of immediate use in integer solutions, that is, to price for integrality. One important heuristic technique in the context of mixed-integer programming solvers is Large-eighbourhood search (LNS). These search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. In this talk, I will introduce an LNS heuristic, IPColGen, where the novelty is to heuristically price for integrality. The theoretical foundation for the pricing scheme is a set of optimality conditions for integer programs. IPColGen has been implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block-diagonal-structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement in solving performance of GCG for challenging instances having a large root node gap. We have also made a tailored implementation of IPColGen as part of a branch-price-and-cut algorithm for an Electric Vehicle Routing Problem with Time Windows and capacitated charging resources available only during specific time slots. Compared to only adding cuts in the root node, the impact of the heuristic is to close one third of the remaining root node gap.

Meike Neuwohner – TBA

TBA

Break

Veronica Piccialli – TBA

TBA

Frederic Didier – MIP aspects of Google OR-tools CP-SAT solver

While CP-SAT focus on pure integer-problems, a lot of its design is similar to the one of a "classic" MIP solver and they can be used to solve optimization problem in mostly the same way. After explaining the class of MIP problem that CP-SAT can deal with, I will dive on some of its implementation details. I will focus on the handling of linear constraints and how we use the LP relaxation of the problem, both being critical components like they are in MIP.

Poster session

Monique Laurent – Semidefinite approximations for bicliques and biindependent pairs

We investigate some graph parameters dealing with biindependent pairs in bipartite graphs, with close relationships to bicliques in general graphs. Deciding whether a bipartite graph has a maximum independent set that is balanced (i.e., with the same number of nodes on each side of the bipartition) is shown to be NP-complete. This implies, in particular, NP-hardness of computing the maximum ratio (sum of sizes over product of sizes) for biindependent pairs. These hardness results motivate introducing semidefinite programming bounds for these various graph parameters, which can be seen as natural variations of the Lovász ϑ-number. We also formulate closed-form eigenvalue bounds and show relationships among them as well as with earlier spectral parameters by Hoffman, Haemers (2001) and Vallentin (2020). Based on joint work with Sven Polak and Luis Felipe Vargas.

Break

Fabio Furini – Hidden Bilevel Structures in Graph Disconnection Problems: Stackelberg Game Models and Exact Algorithms

Many fundamental graph disconnection problems hide an underlying bilevel structure that can be exploited for stronger formulations and algorithms. In this talk, we reveal and formalize this hidden structure for two key problems: the capacitated vertex separator and the k-vertex cut. Both are modeled as two-phase Stackelberg games, where a leader strategically deletes vertices and a follower reacts by optimizing over the disconnected graph. We present new integer programming formulations naturally capturing this bilevel interaction, supported by families of strengthening valid inequalities and polynomial-time separation procedures. Our computational studies demonstrate that these approaches significantly improve the state-of-the-art, yielding better solutions and faster convergence on benchmark instances. Beyond these two problems, the bilevel perspective opens promising directions for a broader class of graph modification and partitioning problems.

Leona Gottwald – TBA

TBA

Lunch break

Martin Schmidt – An Exact Method for Nonlinear Network Flow Interdiction Problems

We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal of maximizing the load shed, and the follower aims at minimizing the load shed by solving a transport problem in the interdicted network. We develop an exact algorithm consisting of lower and upper bounding schemes that computes an optimal interdiction under the assumption that the interdicted network remains weakly connected. The main challenge consists of computing valid upper bounds for the maximal load shed, whereas lower bounds can directly be derived from the follower’s problem. To compute an upper bound, we propose solving a specific bilevel problem, which is derived from restricting the flexibility of the follower when adjusting the load flow. This bilevel problem still has a nonlinear and nonconvex follower’s problem, for which we then prove necessary and sufficient optimality conditions. Consequently, we obtain equivalent single-level reformulations of the specific bilevel model to compute upper bounds. Our numerical results show the applicability of this exact approach using the example of gas networks.

Yelena Yuditsky – Efficiently solving special instances of NP-hard problems: Integer programs with bounded subdeterminants

Many problems can be described using an integer program, e.g. scheduling, capital budgeting, or vehicle routing. In full generality, solving an integer program is known to be NP-hard. However, integer programs where the coefficient matrix is totally unimodular (each determinant of any square submatrix is one of the values in {-1,0,1}) can be solved in polynomial time. One of the central questions in combinatorial optimization is whether there is a polynomial-time algorithm for solving integer programs where the coefficient matrix is totally Δ-modular (each determinant of any square submatrix is one of the values in {-Δ,...,Δ}). The case of Δ=2 was positively resolved by Artmann, Weismantel, and Zenklusen only as recently as 2017 and the question for larger values of Δ still remains open and appears to be very difficult.

In this talk, I will present results for several different cases of the above conjecture. These results require tools from structural graph, as well as a new proximity result of integer optimal solutions and their corresponding linear relaxation solutions.

Break

Laurent Porrier – Engineering the simplex method

The simplex method is the fundamental building block for optimization algorithms like branch-and-bound, column generation, and cutting-plane methods. We explore the engineering trade-offs involved in building a fast and numerically-stable implementation of the simplex method. In particular, most practical optimization problems exhibit specific structure (with respect to sparsity and degeneracy among others), and we show how this impacts implementation choices, sometimes in counter-intuitive ways.

François Lamothe – Dantzig-Wolfe and Fenchel decompositions: hybridation and degeneracy

TBA

Gala dinner

Sophie Demassey – Scheduling nonlinear flow network reconfiguration

Optimizing the discrete control of a dynamic nonlinear system often relies on simulation-optimization, searching through the discrete decision space. Instead, we consider searching through the continuous space of the state variables by adapting a control/state variable splitting scheme alike ADMM. Fixing the state variables provides a strict decoupling into static discrete subproblems and, possibly, the further decomposition of the static subproblem itself, enabling its exact solution. We illustrate this on implementing load shifting in drinking water distribution systems to optimize their power consumption, which translates to dynamically reconfigure a nonlinear flow network with sequence-based boundary conditions. The convergence proof of our iterative scheme is lost on this discrete nonconvex problem, however it can be initialized properly, and the problem at each iteration becomes separable in time, in space, and in primal/flow and dual/potential parts.

Break

Stefan Kuhlmann – Sparse Integer Solutions and Approximations

Given an integer matrix A and vector b, does there exist a non-negative integer solution x to Ax = b with few nonzero entries, a so-called sparse solution? This question has received significant attention in recent years. This talk presents two novel results:

1. There always exists an optimal integral solution with at most m + f(A) non-zero entries, where m is the number of equations and f(A) depends only on the largest full rank subdeterminant of A.

2. When no sparse solution exists, a trade-off between feasibility and sparsity remains: it is still possible to find a sparse approximate solution whose feasibility error decreases exponentially as the number of non-zero entries increases.

Lucas Létocart – Decomposition methods for quadratic programming

The aim of this talk is to present some decomposition methods for quadratic problems. We first analyze a simplicial decomposition like algorithmic framework that handles convex quadratic programs in an eff ective way. In particular, we propose two suitable strategies for solving the master problem and describe some techniques for speeding up the solution of the pricing problem. We then propose a methodological analysis on a family of reformulations combining Dantzig-Wolfe decompositions and Quadratic Convex Reformulations for non-convex binary quadratic problems. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem. Finally, we propose a matrix generation method for non-convex quadratically constrained 0-1 quadratic problems based on a Dantzig-Wolfe reformulation that leads to a linear master and an unconstrained 0-1 pricing problem. The domain of this relaxation, the Boolean Quadric Polytope, is contained in the cone of Completely Positive matrices.

Lunch break

End of workshop