We describe the notion of discrepancy and explain its connection to rounding fractional solutions to integral ones. We then describe some discrepancy algorithms, and explain how they can viewed as combining the strengths of both iterated rounding and randomized rounding.

In this talk, I will concentrate on the problem of finding a first feasible solution for an integer programming problem within the branch-and-bound scheme. I will first review one of the oldest iterative rounding heuristics for 0-1 integer programming, Pivot and Complement by Balas & Martin (1980) and then, switch to the original version of the Feasibility Pump heuristic (Fischetti, Glover and Lodi, 2005). The latter has been followed by a number of improvements and extensions that I will highlight in short.

For bin packing, the input consists of \(n\) items with sizes \(s_1,...,s_n\) in \([0,1]\) which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from 1982 produces a solution with at most \({\rm OPT} + O(\log^2 {\rm OPT})\) bins. We show that methods from discrepancy theory can be used to find a solution of cost \({\rm OPT} + O(\log {\rm OPT})\) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation.

For the rounding algorithm itself one can use for example the random projection algorithm that can find partial colorings even in arbitrary symmetric convex sets.

This is joint work with Rebecca Hoberg.

Feasibility pump is a successful primal heuristic for mixed-integer linear programs. The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the Linear Programming relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have been proposed, they mainly focus on the rounding and projection steps. We start a more in-depth study of the randomization step in Feasibility Pump. For that, we propose a new randomization step based on the WalkSAT algorithm for solving instances of the Boolean Satisfiability Problem. First, we provide theoretical analyses for instances with disjoint equality constraints that show the potential of this randomization step; to the best of our knowledge, this is the first time any theoretical analysis of running-time of Feasibility Pump or its variants has been conducted, even for a special class of instances. Moreover, we propose a practical version of new randomization step, and incorporate it into a state-of-the-art Feasibility Pump code. Our experiments suggest that this simple-to-implement modification consistently dominates the standard randomization previously used.

This is joint work with Andres Iroume, Marco Molinaro, and Domenico Salvagnin.

In Mixed Integer Conic Programming, nonlinearities are described via convex cones. As a subclass of MINLP, it is inevitably in need of many ingredients that make up Mixed Integer Programming, such as primal heuristics. In this talk, we discuss some ideas on how to exploit conic structures in the Feasibility Pump heuristic and how they can be implemented in MOSEK, a software package for large-scale Conic and Mixed Integer Conic Programming.

State of the art MIP solvers offer a wide range of heuristics to provide good quality feasible MIP solutions as early as possible during the solution process. Whether they are used at the root node or within the branch-and-bound tree, they can speed up the solution significantly, and they work best when they are suited to the problem at hand or exploit its salient features.

In this joint presentation we provide a broad description of the types of heuristics available in two commercial MIP solvers, IBM-Cplex and FICO-Xpress, including several variants of local search and MIP-based heuristics, and discuss how and when they are used. We also provide computational results to evaluate the performance impact of the different types of heuristics previously discussed.

The constraint integer program framework SCIP solves convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality via spatial branch-and-bound over a linear relaxation. In this talk we give a brief introduction to the global optimization of MINLPs and to SCIP's solving algorithm with a special focus on primal heuristics applied during the search.

If the number of equations of an integer program \(\max \{c^Tx \colon Ax = b, \, x \geq 0, x \in \mathbb{Z}^n\}\) is fixed, then the problem lends itself to dynamic programming approaches. This was already observed in 1981 by Papadimitriou. In this talk, we discuss how to speed up this classical dynamic programming approach using the Steinitz Lemma which leads to the first significant improvement of the running time since more than 30 years. We will also discuss open problems in the area, in particular concerning integer programming with upper bounds on the variables.

Based on joint work with Robert Weismantel.

In this talk, I will survey the iterative rounding method and illustrate its applicability in combinatorial optimization with classical as well as new applications. I will also talk about the close relationship between discrepancy theory and iterative rounding.

I will survey some works on fast numerical linear algebra, in particular tools for approximating matrices by sampling. We will see a simple algorithm for sampling rows of a matrix A while approximately preserving ||Ax||_2^2 for all vectors x. While simple and efficient algorithms can approximate ||Ax||_2^2, more elaborate techniques can achieve the same approximation quality using fewer row samples, and we will discuss an algorithm that reduces the sample complexity by a factor log n.

In the vector balancing problem, we are given symmetric convex bodies \(C\) and \(K\) in \(n\)-dimensional space, and our goal is to determine the minimum number \(b\), known as the vector balancing constant from \(C\) to \(K\), such that for any sequence of vectors in \(C\) there always exists a signed combination of them lying inside \(bK\). This quantity goes back to a question of Dvoretzky from 1963. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Applied Mathematics, Vol 3 Issue 1, 1981), Spencer's "six standard deviations suffice" theorem (Transactions of the American Mathematical Society, Vol 289 Issue 2, 1985) and Banaszczyk's vector balancing theorem (Random Structures & Algorithms, Vol 12 Issue 4, 1998) correspond to bounds on vector balancing constants.

The above theorems have inspired much research in recent years within theoretical computer science, from the development of efficient polynomial time algorithms that match existential vector balancing guarantees, to their applications in the context of approximation algorithms. In this work, we show that all vector balancing constants admit "good" approximate characterizations, with approximation factors depending only polylogarithmically on the dimension \(n\). First, we show that a volumetric lower bound due to Banaszczyk is tight within a \(O(\log n)\) factor. Second, we present a novel convex program which encodes the "best possible way" to apply Banaszczyk's vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an \(O(\log^{2.5} n)\) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm. Our results yield the first guarantees which depend only polylogarithmically on the dimension of the norm ball \(K\).

Based on joint work with D. Dadush, K. Talwar, and N. Tomczak-Jaegermann.

Suppose we are given two sets of positive integers \(X\) and \(Y\), where \(X\) is ordered and interspersed with free slots. Our goal is to assign the elements in \(Y\) to these slots so as to minimize the maximum absolute value between the \(X\) and \(Y\) values over all prefixes. This problem is equivalent to the so-called "Gasoline Problem". We present an algorithm for this problem that rounds a natural LP relaxation to produce a permutation of \(Y\) whose objective value is at most twice optimal. We also discuss some connections to bin packing algorithms.

Based on joint work with Heiko Roeglin and Johanna Seif.

Suppose one has \(n\) elements and \(m\) sets containing each element independently with probability \(p\). We prove that in the regime of \(n \geq \Theta(m^2\log(m))\), the discrepancy is at most \(1\) with high probability. Previously, a result of Ezra and Lovett gave a bound of \(O(1)\) under much stricter assumptions.

We argue that a good coloring exists by analyzing the Fourier coefficients of the discrepancy of a random coloring. We hope that these techniques can be extended to a more general class of set systems.

Based on joint work with Thomas Rothvoss.

We are concerned with classical diving heuristics in mixed-integer programming solvers that iteratively fix integer variables and re-solve the linear programming relaxation. These heuristics share the property that they either succeed in producing a feasible primal solution or return a dual certificate of infeasibility subject to the variable fixings. Although aimed at success, the failure certificates can be analyzed to extract globally valid inequalities that help to reduce the size of the remaining search tree. We give a quick introduction to techniques from conflict analysis and discuss the design of a diving heuristic that aims at producing strong conflicts.