Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On … Read more
In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and … Read more
We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, … Read more
Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more
Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein, A general branch-and-bound framework for continuous global multiobjective optimization, Journal of Global Optimization, 80 (2021) 195-227, we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the … Read more
A \emph{general branch-and-bound tree} is a branch-and-bound tree which is allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0 \,\vee\, \pi^{\top}x \geq \pi_0 + 1$, where $\pi$ is an integer vector and $\pi_0$ is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a … Read more
Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and … Read more
For a binary integer program (IP) $\max c^\T x, Ax \leq b, x \in \{0,1\}^n$, where $A \in \R^{m \times n}$ and $c \in \R^n$ have independent Gaussian entries and the right-hand side $b \in \R^m$ satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we prove that the gap between the value … Read more
Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more
One of the standard approaches for solving time-dependent discrete optimization problems, such as the traveling salesman problem with time-windows or the shortest path problem with time-windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a … Read more