We consider the problem of minimizing a polynomial function f over a compact set K. Hierarchies of (lower and upper) bounds have been introduced in the recent years, based on sums of squares of polynomials. In this lecture we will in particular consider the measure-based upper bounds of Lasserre (2011), which are obtained by searching for a degree 2r sum-of-squares density function minimizing the expected value of f over K with respect to a given reference measure supported by K. For simple sets like the box, the unit ball, the simplex and the unit sphere (and natural reference measures including the Lebesgue measure), one can show that the convergence rate to the global minimum of f is in O(1/r^2) and that this bound is tight for some classes of polynomials. These results extend to smooth strictly convex bodies satisfying some boundary conditions. For general convex bodies one can show a slightly weaker convergence rate in O((log(r)/r)^2). The analysis relies, in particular, on an eigenvalue reformulation of the bounds and on links to extremal roots of orthogonal polynomials and to cubature rules. This is based on joint works with Etienne de Klerk and Lucas Slot.

Popular matchings are a well-known generalization of stable matchings. In this talk, we consider the following question: given a bipartite graph with weights on the edges, how can we find a popular matchings of maximum weight? Based on the papers Popular matchings and limits to tractability (with T. Kavitha, V. Powers, and X. Zhang, SODA 19) and Quasi-popular matchings, optimality, and extended formulations (with T. Kavitha, SODA 20)

Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that "approximately popular" branchings always exist. This is joint work with Telikepalli Kavitha, Tamás Király, Ildikó Schlotter, and Ulrike Schmidt-Kraepelin.

In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., y ~ x for all arcs a. Twenty years ago, in a landmark paper, Dinitz, Garg, and Goemans proved that there is an unsplittable flow y such that y(a) ist at most x(a)+dmax for all arcs a, where dmax denotes the maximum demand value. Unsplittable flows with arc-wise lower bounds have, to the best of the authors’ knowledge, not been considered yet. Based upon an entirely new approach, we prove the following result: There is an unsplittable flow y such that y(a) is at least x(a)-dmax for all arcs a. Our second contribution is a considerably simpler one-page proof for the above mentioned classical result of Dinitz, Garg, and Goemans, using a variant of our approach. Finally, building upon an iterative rounding technique previously introduced by Kolliopoulos and Stein and Skutella, we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case when demands are integer multiples of each other. For arbitrary demand values, we prove the slightly weaker simultaneous bounds with y(a) being lower bounded by x(a)/2 – dmax and upper bounded by 2x(a)+dmax for all arcs a. This is joint work with Martin Skutella.

We consider the task of proving integer infeasibility of a bounded convex K in R^n using a branching proof system. In a branching proof, one constructs a branching tree by adding an integer disjunction ax <= b or ax >= b+1, a in Z^n, b in Z, at each node, such that the leaves of the tree correspond to empty sets (i.e., K together with the inequalities picked up from the root to leaf is empty). Recently, Beame et al (ITCS 2018), asked whether the bit size of the coefficients in a branching proof, for the special case where K is a polytope in [0,1]^n, can be assumed to be polynomial in n. We resolve this question in the affirmative, by showing that any branching proof can be recompiled so that the normals of the disjunctions have length at most (n D)^{O(n^2)}, where D is diameter of K, while increasing the number of nodes in the branching tree by at most a factor n. Our recompilation techniques works by first replacing each disjunction using an iterated Diophantine approximation, first introduced by Frank and Tardos (Combinatorica 1986), and proceeds by patching up the leaves using judiciously added Chvatal-Gomory (CG) cuts guided by approximate Farkas certificates of infeasibility. The talk will be self-contained, and no prior knowledge of branching proof systems, Diophantine approximation or CG cuts will be assumed. Joint work with Samarth Tiwari (CWI).

Motivated by modern regression applications, in this paper, we study the convexification of quadratic optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on the convexification of sparse regression problems, we simultaneously consider the nonlinear objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic objective function, the perspective reformulation is ideal independent from the constraints of the problem. In contrast, while rank-one relaxations cannot be strengthened by exploiting information from k-sparsity constraint for k>1, they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity. Joint work with Andres Gomez and Linchuan Wei.

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower’s profits are uncertain. Adopting the robust optimization approach and assuming that the follower’s profits belong to a given uncertainty set, our aim is to compute a worst case optimal solution for the leader. We show that this problem can be solved in polynomial time for both discrete and interval uncertainty. Moreover, we show that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this shows that replacing uncertainty sets by their convex hulls may change the problem significantly, different from the classical single-level robust optimization setting.

We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n^6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n^2) bound for the special case of graphic (and cographic) matroids. However, the case of a general regular matroid was open, despite recent attempts (two papers claimed a polynomial bound in 2016, 2017, but each contained a fundamental flaw and was withdrawn). This is joint work with Samuel Fiorini.

Recently, there has been a surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, in order to obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P \neq NP. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set. This is joint work with Georg Anegg, Adam Kurpisz and Rico Zenklusen.

The Steiner tree problem (STP) is a classical NP-hard combinatorial optimization problem with applications in computational biology and network wiring. The objective of this problem is to find a minimum cost subgraph of a given undirected graph G with edge costs, that spans a subset of vertices called terminals. We present currently used linear programming formulations of the problem based on two different approaches—the bidirected cut relaxation (BCR) and the hypergraphic formulations (HYP), the former offering better computational performance, and the latter better bounds on the integrality gap. As our contribution, we propose a new hierarchy of path-based extended formulations for STP.We show that this hierarchy provides better integrality gaps on graph instances used to define the worst-case lower bounds on the integrality gap for both BCR and HYP. We prove that each consecutive level of our hierarchy is at least as strong as the previous one. Additionally, we also present numerical results showing that several difficult STP instances can be solved to integer optimality by using this hierarchy. Our approach can be adapted to variants of STP or applied to hypergraphic formulations for further potential improvement on the integrality gap bounds, in exchange for additional computational effort.

Rectilinear Steiner arborescences under linear delay constraints play an important role for buffering. We present exact algorithms for either minimizing the total length subject to delay constraints, or minimizing the total length plus the (weighted) absolute total negative slack. Our main theoretical contribution is the first minimum cost flow formulation for embedding Steiner arborescences at minimum length subject to delay constraints, resulting in the first strongly polynomial time algorithm for this subproblem. We use the minimum cost flow formulation to quickly compute lower bounds in a branch-&-bound algorithm for optimum Steiner arborescences.

Consider the family of graphs without $k$ node-disjoint odd cycles, where $k$ is a constant. Determining the complexity of the stable set problem for such graphs $ G $ is a long-standing problem. We give a polynomial-time algorithm for the case that $G$ can be further embedded in a (possibly non-orientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that $2$-sided odd cycles satisfy the Erd\H{o}s-P\'osa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erd\H{o}s-P\'osa property in graphs embedded in a fixed orientable surface (Kawarabayashi \& Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case. Joint work with Michele Conforti, Tony Huynh, Gwena\"el Joret and Stefan Weltge.

We consider problems of the form $\min\{cx+hy: Ax+By \geq b, x \in \Z^n_+,y \in Y \subseteq \R^p_+\}$ that are often treated using Benders' algorithm, but in which some of the $y$-variables are required to be integer. We present two algorithms that hopefully add to and clarify some of the algorithms proposed since the year 2000. Both are branch-and-cut algorithms solving linear programs by maintaining a strict separation between a Master problem in $(x,\eta)$-variables and a subproblem in the $y$-variables. The first involves nothing but the solution of linear programs, but involves branching in $(x,y)$-space. The second restricted to problems with $x \in \{0,1\}^n$ only requires branching in the $x$-space, but uses cutting planes in the subproblem based on the integrality of the $y$-variables that are converted/lifted into valid inequalities for the original problem in $(x,y)$-variables. For the latter algorithm we show how the lifting can be carried out trivially for several classes of cutting planes.

We study the design of water networks, which consists of selecting pipe connections and pumps to ensure a given water demand while minimizing investment and operating costs. The inclusion of the nonlinear dependencies of volume flow, pressure increase and power consumption for the operation of the variable-speed pumps leads to complex mixed-integer nonlinear programs. For tree-shaped networks the volume flow variables can only attain finitely many values. We present a branch and bound approach, which branches on the corresponding flow variables. For fixed flows we derive a convex pump model enabling the separation of perspective cuts involving the power, pressure and indicator variables of the pump. To strengthen these cuts, we heuristically lift them to also include the volume flow. Computational experiments show the method's advantages for the model of a decentralized high-rise water network. The work is joint work with Marc Pfetsch.

This talk reviews some recent results in bi-level optimization for applications in energy, privacy, and mobility.

This work presents a massively parallel implementation of the Network Simplex Algorithm, which runs on a Graphics Processing Unit (GPU). The parallel implementation of the Network Simplex is motivated by the computation of exact Wasserstein distance between a pair of discrete measures where the cost vector can be computed in closed form using a given cost function (e.g., the Euclidean distance). Currently, the available exact solvers for Wasserstein distances solve instances of moderate size because the fully dense cost matrix becomes too large to be stored in computer memory. To overcome this memory issue, we revise the Network Simplex in terms of Column Generation by decomposing the network flow problem into two subproblems: a master problem that maintains and updates the basic solution (i.e., a rooted spanning tree) and a pricing subproblem which looks for negative reduced cost variables by exploiting a closed-form expression of the cost function. The master problem is solved with a new implementation of the Network Simplex algorithm that supports re-optimization for variable additions and removals, and it is executed on the main CPU. The pricing subproblem is solved by exploiting the massive parallelism of GPUs. Numerical results on standard benchmarks for the computation of Wasserstein distances show that our exact solver is competitive with the current state-of-the-art exact algorithm in terms of running time, while it outperforms every other existing approach in terms of memory consumption.

** Slides available at: [GPU_NetworkSimplex.pdf]

The fact that "challenging problems motivate methodological advances", as obvious as it may seem, is nonetheless true. We were drawn to Unit Commitment problems because of a specific methodology, but studying it led us to interesting results for entirely different ones. This talk is only partly related to one of them (the Perspective Reformulation), and deals with a composition operation between MINLPs with the property that is one knows the convex hull of the two individual pieces, this immediately gives the convex hull of the whole problem. This result is not at all unexpected (in the linear case it boils down to the proof by Chvatal of composition of stable set polyhedra by clique-cutsets), but knowing it is indeed true may be useful to someone; indeed, a couple of wrong versions of it have circulated in the recent UC literature. If time permits we will also present some computationals about the strength and the usefulness of some extended formulations for UC which motivated the result.

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We focus on variables disjunctions and split disjunctions. It was known from previous work by Dash that for 0/1 polytopes, CP does at least as well as BB. We sharpen this by showing that there are instances of the stable set problem where CP does exponentially better than BB. We further show that if one moves away from 0/1 polytopes, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). Finally, we show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up). This gives some mathematical justification why the best guarantees in fixed dimensions exist for Lenstra-style algorithms that based on BB.

Although the cutting-plane approach is a widely used tool for the solution of integer and mixed integer linear programs, some theoretical questions on cutting planes are still unsolved even when there are only two variables. We answer two of these questions. Specifically, (i) we show that there is a polynomial-time cutting-plane algorithm based on split cuts that solves integer programming problems with two variables, and (ii) we prove that the split closure of a rational polyhedron in the plane has polynomial size. This is joint work with Amitabh Basu, Michele Conforti, and Hongyi Jiang.

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of the three algorithms for problem instances arising in the context of real-world gas transport networks.

The exact subgraph relaxation in combination with semidefinite optimization has recently turned out to be a very powerful tool for Max-Cut, Stable-Set and Coloring. It works with a basic SDP relaxation, typically in matrices of order $n$, and incrementally adds 'exact subgraph' constraints to the relaxation. In contrast, the Lasserre hierarchy moves to matrix relaxations, which are unpractical even in the first nontrivial step (typically matrices of order ${n \choose 2}$. In this talk we explore relations between the two seemingly quite different approaches. We show in particular how a slightly weakened version of the Lasserre relaxations can be dealt with in the space of matrices of order $n$. Preliminary computational results are given and look encouraging.

Augmented Lagrangian methods are among the most popular first-order approaches to handle large scale semidefinite programs (SDP). Alternating direction method of multipliers (ADMM) is a variant of the augmented Lagrangian scheme that performs consecutive updates on certain blocks of the dual variables. We present an ADMM where we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. A description on how to deal with the resulting unconstrained maximization of the augmented Lagrangian is given. In particular, we look at doubly nonnegative programs (DNN), i.e., semidefinite programs where the elements of the matrix variable are constrained to be nonnegative. In an ADMM, these constraints can be handled efficiently since this simply amounts in projections onto the non-negative orthant. Whenever the SDP or DNN is a relaxation of a combinatorial optimization problem, one is interested in using its solution within a branch-and-bound framework. ADMM typically does not yield solutions with a high precision. Having solutions of moderate precision only, the obtained optimum of the SDP or DNN might not be a valid bound for the underlying combinatorial optimization problem. We present methods to perform a post-processing to obtain valid bounds from the solution of the ADMM. This valid bound can be computed at low cost and the numerical results demonstrate that this procedure does not weaken the bound significantly. This is joint work with Martina Cerulli, Marianna De Santis, Elisabeth Gaar.

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. We present similar sufficient conditions under which the projected epigraph of the SDP gives the convex hull of the epigraph in the original QCQP. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs. This is joint work with Alex Wang.

In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constant-factor approximation algorithm for the asymmetric traveling salesman problem. In this work we revisit their algorithm: while following their overall framework, we improve on each part of it. Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22+epsilon for any epsilon>0. This also improves the upper bound on the integrality ratio from 319 to 22. This is joint work with Jens Vygen.

The new version 9.0 of Gurobi is able to solve non-convex MIQCPs to global optimality. The algorithm is pretty straight-forward: translate the non-convex parts of the quadratic constraints and objective into bilinear constraints and apply LP-based branch-and-cut using the McCormick relaxation to solve the resulting model. But of course, the devil is in the details. This talk will provide some insight into the details of our implementation and present some preliminary computational results.

An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y<= x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in any packing polyhedron is an integer packing set. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a question recently posed by Bodur et al. We prove that the k-aggregation closure of any packing polyhedron is again a packing polyhedron. The generality of our main result allows us to provide a generalization to non-polyhedral sets as well: The k-aggregation closure of any downset of $\R^n_+$ is a packing polyhedron.

Due to theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often handle a moderate presence of nonconvexities efficiently, which opens the door for the use of potentially tighter, nonconvex relaxations. In this work, we exploit this development by use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We study a generalization of these relaxations that allows for multiple aggregations and present the first algorithm that is capable of computing the best set of aggregations. We propose several computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.

Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger's celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.

We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of N items and a discrete time horizon of T days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time t can be satisfied by an order on any day prior to t, but a holding cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is O(log log min(N,T)); this improves exponentially on the previous best results.

Clustering is an important unsupervised learning method and approximation algorithms for objective functions like k-median and k-means have been intensively studied. Much less is known about a slightly different domain: hierarchical clustering. Here, instead of looking for one k-clustering, the goal is to find a hierarchy of clusterings. There are many popular hierarchical clustering algorithms that are used in practice but relatively little is known about their theoretical properties. We study Ward's method for the hierarchical k-means problem. This popular greedy heuristic is based on the complete linkage paradigm: Starting with all data points as singleton clusters, it successively merges two clusters to form a clustering with one cluster less. The pair of clusters is chosen to (locally) minimize the k-means cost of the clustering in the next step. We give upper and lower bounds on the algorithm's performance ratio. This is joint work with Anna Großwendt and Heiko Röglin.

Divisorial gonality is a graph parameter that has its origins in algebraic geometry. It is a combinatorial analogue and lower bound for gonality of algebraic curves. In terms of the classical chip-firing game of Björner-Lovász-Shor it relates to chip configurations that result in a finite game, even after adding a chip at an arbitrary position. In the talk, I will show that computing the gonality of a graph is NP-hard. In fact, it cannot be approximated to within an arbitrary factor in polynomial time (unless P=NP). I will also present a number of open problems.

In online min-cost matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an O(1)-competitive algorithm. The best known online algorithm by Raghvendra (2018) achieves a competitive factor of Theta(log n). This result matches a lower bound of Omega(log n) (Anntoniadis et al. 2018) that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an O(1)-competitive algorithm for online matching on the line that uses at most O(n log n) reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a (1+eps)-competitive algorithm that reassigns any request at most O(1/eps^2) times. This special case is interesting as the aforementioned quite general lower bound Omega(log n) uses such instances. Joint work with Lukas Noelke.

The Nemhauser-Trotter theorem states that the standard LP formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.

A famous 1986 result by Tardos on combinatorial linear programs showed that a linear program can be solved in poly(n,m,log Delta) arithmetic operations, where Delta is the maximum subdeterminant of the integer constraint matrix. Note that this bound is independent from the right hand side and the cost vector. This was significantly strengthened by Vavasis and Ye in 1996, who gave a 'layered least squares' (LLS) interior-point method, that terminates with an exact optimal solution in O(n^{3.5} log(\bar\chi_A+n)) iterations, where \bar\chi_A is a certain condition number associated with the (not necessarily integer) constraint matrix A.

Monteiro and Tsuchiya, noting that the central path is invariant under rescalings of the columns of A and c, asked whether there exists an LP algorithm depending instead on the measure \bar\chi^*_A, defined as the minimum \bar\chi_{AD} value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this question in the affirmative, by giving a new LLS interior-point method that terminates in O(n^{2.5} log(\bar\chi_A^*+n)) iterations.

The main insight is a new, combinatorial characterization of the condition number \bar\chi. We show that this can be well approximated with a certain 'circuit imbalance measure'. Using techniques of matroid theory, we give an efficient algorithm for finding a nearly optimal column rescaling. Further, we develop a scaling invariant LLS algorithm, together with a refined potential function based analysis for LLS algorithms in general.

In the talk, I will give a self-contained introduction of LLS interior-point methods from a combinatorial optimization perspective.

This is joint work with Daniel Dadush, Sophie Huiberts, and Bento Natura.

The paper is available at https://arxiv.org/abs/1912.06252, and the slides at https://platformconclude.github.io/talk_scaling/aussois.html

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The Connectivity Augmentation Problem (CAP) is arguably one of the most basic problems in this area: given a $k$(-edge)-connected graph $G$ and a set of extra edges (links), select a minimum cardinality subset $A$ of links such that adding $A$ to $G$ increases its edge connectivity to $k+1$. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is $2$, and this can be achieved with multiple approaches (the first such result is in [Frederickson and J{\'a}j{\'a}'81]). It is known [Dinitz et al.'76] that CAP can be reduced to the case $k=1$, a.k.a. the Tree Augmentation Problem (TAP), for odd $k$, and to the case $k=2$, a.k.a. the Cactus Augmentation Problem (CacAP), for even $k$. Several better than $2$ approximation algorithms are known for TAP, culminating with a recent $1.458$ approximation [Grandoni et al.'18]. However, for CacAP the best known approximation is $2$. In this paper we breach the $2$ approximation barrier for CacAP, hence for CAP, by presenting a polynomial-time $2\ln(4)-\frac{967}{1120}+\epsilon<1.91$ approximation. Previous approaches exploit properties of TAP that do not seem to generalize to CacAP. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al.'14]. This reduction is not approximation preserving, and using the current best approximation factor for Steiner tree [Byrka et al.'13] as a black-box would not be good enough to improve on $2$. To achieve the latter goal, we ``open the box'' and exploit the specific properties of the instances of Steiner tree arising from CacAP.

The parametric global minimum cut problem concerns a graph $G = (V, E)$ where the cost of each edge is an affine function of a parameter $\mu \in \mathbb{R}^d$ for some fixed dimension $d$. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.

We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. For a well-conditioned $m \times n$ constraint matrix with at most $d_c$ nonzero elements per column, at most $d$ nonzero elements per column or row of the basis, and optimality tolerance $\epsilon$, we show that pricing can be performed in time $\tilde{O}(\frac{1}{\epsilon}\sqrt{n}(d_c n + d^2 m))$, where the $\tilde{O}$ notation hides polylogarithmic factors. If the ratio $n/m$ is larger than a certain threshold, the running time of the quantum subroutine can be reduced to $\tilde{O}(\frac{1}{\epsilon}d \sqrt{d_c} n \sqrt{m})$. Classically, pricing would require $O(d_c^{0.7} m^{1.9} + m^{2 + o(1)} + d_c n)$ in the worst case using the fastest known algorithm for sparse matrix multiplication. We also show that the ratio test can be performed in time $\tilde{O}(\frac{t}{\delta} d^2 m^{1.5})$, where $t, \delta$ determine a feasibility tolerance; classically, this requires $O(m^2)$ in the worst case. For well-conditioned sparse problems the quantum subroutines scale better in $m$ and $n$, and may therefore have a worst-case asymptotic advantage. An important feature of our paper is that this asymptotic speedup does not depend on the data being available in some ``quantum form'': the input of our quantum subroutines is the natural classical description of the problem, and the output is the index of the variables that should leave or enter the basis.

The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined as a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed. To the best of our knowledge, this work is the first to provide maximal quadratic-free sets.

Exact methods for the Maxmium Cut problem heavily rely on the separation of the so-called odd-cycle inequalities. Since the groundbreaking work by Barahona and Mahjoub in 1986, it is known how to solve this subproblem efficiently. We show that it is computationally worthwhile to invest some more effort in order to make the algorithm return only facet-defining inequalities which is not the case in general. Moreover, we investigate how this enhanced separation procedure compares to an ideal setting, where one could even select facet-defining odd-cycle inequalities that are optimum to some commonly used measure, such as maximum violation, minimum support (maximum sparsity), or geometric criteria. This is joint work with Mike Jünger.

The Dijkstra Steiner Algorithm (Hougardy, Silvanus, Vygen 2017) is an dynamic program which solves the graphic Steiner tree problem exactly. The authors obtain very good practical run time useing special lower bounds on the cost of a Steiner trees connecting some vertex in the graph to some subsets of the terminals. We will focus on instances which have huge graph, but a nice geometric relaxation and few terminals or restricted topologies (they can e.g. appear in VLSI routing problems). We will discuss some techniques and challenges when trying to achieve a run time comparable to successive path searches in such instances, which are still used in industrial routers today due to run time requirements.

The academic literature is rich of works on minimizing makespan in scheduling batch processing machines, mainly motivated by burn-in tests in the semiconductor industry. The problem addressed in this talk consists in grouping jobs in batches and scheduling them on a machine. The jobs have a non-identical size and processing times, which means that each job requires an empty space to be allocated to the batch, and a minimum time to be processed on the machine. The machine has a capacity limitation, which must not be exceeded by the sum of the sizes of all jobs assigned in each batch. The processing time of each batch will be equal to the higher processing time of all the jobs assigned to it. Two new mathematical models are presented, in which the first deals with the symmetries found in the original problem, and the second is an arc-flow based formulation. Computational results show that the proposed models have a better performance than other models in the literature, using CPLEX to solve them. In the arc-flow formulation, the number of variables does not change when the number of jobs increases, which enabled us to find the optimum solution of instances with 100 million jobs in 3.25 seconds. These results define a new threshold for the size of the instances, because the maximum number of jobs previously treated by the works in the literature was 500, using heuristic approaches in instances with the same parameters.

Many cutting planes in MINLP heavily rely on the bounds of the variables. In this talk, we consider the possibility of generating a cutting plane from a reduced domain while still ensuring the validity of them. We formalize this idea using the reverse polar. Relying on the concept of visible points, we provide a simple description of the reduced domain of the variables when constructing cutting planes for a quadratic constraint. We also provide an extended formulation for the shrunken domain for polynomial constraints, based on nonnegative univariate polynomials.

In applied work, part of the data is sometimes missing or censored. "Missingness'' mechanisms may be adversarial: intentional withholding of information, censoring based on unobservables, etc. or modeling "missingness'' requires additional assumptions, which in turn may lead us to overstate the amount of information in the data. We develop a framework that is suitable for several statistical problems with missing data and, in particular, we consider in this talk the linear quantile regression with missing categorical variables. We propose a new mathematical model for it and we evaluate it computational on both synthetic and real data of econometrics models.