Workshop on Discrepancy Theory and Integer Programming

CWI, Amsterdam - Monday June 11 - Friday June 15, 2018

Purpose:

Discrepancy theory has developed a general theory of "rounding", which allows us to understand how much "error" one must incur to round continuous solutions to discrete ones. This theory was by and large non-constructive until recently, where in the last few years polynomial time algorithms have been developed that match almost all known existential guarantees. The need for good generic rounding methods has been clear for a long time in the context of Integer Programming. Heuristic techniques for rounding LP solutions within MIP solvers have been studied since at least the 1980's. The goal of this workshop is to bring together experts in discrepancy theory and integer programming to explore these exciting connections between both areas.

Resources and Open Problems:

A list of basic references in both discrepancy theory and rounding heuristics in IP has been compiled here.
An evolving list of open problems in both areas is available here.
Additional suggestions for both references and open problems are welcome!
Please send your recommendations to Daniel Dadush (dndadush@gmail.com).

Registration:

Registration is free, however space is limited. Registered participants are welcome to attend the morning talks Monday - Thursday. The work sessions on Monday - Thursday afternoons & Friday morning are mainly intended for invited participants. Those wishing to participate in the work sessions should express this in the registration email and commit to attending at least the first 3 days of the workshop. Please register by sending an email to Susanne van Dam (susanne@cwi.nl) before May 25th (if possible, with the exact dates you expect to attend) under the heading "Discrepancy and IP workshop registration", to help us with planning and catering.

Workshop Boat Trip and Dinner (invited participants):

Date: Tuesday, June 12. Time: 6pm - late.
Leave CWI by bus at 6pm.
Boat trip 6:30pm-7:30pm (Tropen Museum to Pllek).
Dinner at Pllek 7:30pm-late.

Workshop Schedule:

Monday, June 11

Time Location Description
9:30am - 10am Outside L016 Coffee Break
10:00am-11am L016 Nikhil Bansal (CWI & TU/e)
A Friendly Introduction to Discrepancy Minimization (show abstract)

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.
11am-12pm L016 Andrea Lodi (Polytechnique Montreal)
From Pivot and Complement to the Feasibility Pump (slides) (show abstract)

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.
12pm-1pm Outside L016 Catered Lunch
1pm-2pm L016 Thomas Rothvoss (University of Washington)
Discrepancy Algorithms and Applications to Bin Packing (slides) (show abstract)

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.
2pm - 2:30pm Outside L016 Coffee Break
2:30pm-3pm L016 Santanu Dey (Georgia Tech)
Improving the Randomization Step in Feasibility Pump using WalkSAT (slides) (show abstract)

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.
3pm-3:30pm L016 Sven Wiese (Mosek ApS)
The Feasibility Pump heuristic for Mixed Integer Conic Programming (slides) (show abstract)

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.
3:30pm-4pm L016 Open Problems Session
4pm-4:30pm L016 Coffee Break
4:30pm - 6pm L016, L202, L231, M290 Work Sessions

Tuesday, June 12

Time Location Description
9:30am - 10am Outside L016 Coffee Break
10:00am-11am L016 Andrea Tramontani (IBM CPLEX) & Pietro Belotti (FICO Xpress)
Heuristics in Commercial MIP Solvers (slides part 2) (show abstract)

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.
11am-12pm L016 Felipe Serrano (Zuse Institute Berlin)
Heuristic Algorithms in Exact MINLP Solving (slides) (show abstract)

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.
12pm-1pm Outside L016 Catered Lunch
1pm-2pm L016 Friedrich Eisenbrand (École Polytechnique Fédérale de Lausanne)
Faster Algorithms for Integer Programming using the Steinitz Lemma (show abstract)

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.
2pm - 2:30pm Outside L016 Coffee Break
2:30pm - 4:30pm L016, L202, L231, M290 Work Sessions
4pm-4:30pm L016 Coffee Break
4:30pm - 6pm L016, L202, L231, M290 Work Sessions
6pm - late Amsterdam Canals & Pllek Conference Boat Trip and Dinner

Wednesday, June 13

Time Location Description
9:30am - 10am Outside L016 Coffee Break
10am-11am L016 Mohit Singh (Georgia Tech)
Iterative Rounding and its applications in Combinatorial Optimization and Discrepancy (show abstract)

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.
11am-12am L016 Rasmus Kyng (Harvard)
Fast Numerical Linear Algebra in Theoretical Computer Science (show abstract)

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.
12pm-1pm Outside L016 Catered Lunch
1pm-2pm TBD TBD
2pm - 2:30pm Outside L016 Coffee Break
2:30pm - 4:30pm L016, L202, L231, M290 Work Sessions
4pm-4:30pm L016 Coffee Break
4:30pm - 6pm L016, L202, L231, M290 Work Sessions

Thursday, June 14

Time Location Description
9:30am - 10am Coffee Break Outside L016
10am-11am L016 Aleksandar Nikolov (University of Toronto)
Balancing Vectors in any Norm (slides) (show abstract)

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.
11am-11:30am L016 Alantha Newman (Université Grenoble Alpes)
Finding Permutations with Prefix Targets (slides) (show abstract)

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.
11:30am-12pm L016 Rebecca Hoberg (University of Washington)
A Fourier-Analytic approach for Random Set Systems (slides) (show abstract)

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.
12pm-1pm Catered Lunch Outside L016
1pm - 1:30pm L016 Ambros Gleixner (Zuse Institute Berlin)
Diving for Conflicts in Mixed-Integer Programming (slides) (show abstract)

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.
2pm - 2:30pm Outside L016 Coffee Break
2:30pm - 4pm L016, L202, L231, M290 Work Sessions
4pm - 4:30pm Outside L016 Coffee Break
4:30pm - 6pm L016, L202, L231, M290 Work Sessions

Friday, June 15

Time Location Description
9:30am - 10am Outside M290 Coffee Break
10:00am - 12pm L202, L231, M290 Work Sessions
12pm-1pm Outside M290 Catered Lunch
End of workshop

Location

CWI, Science Park 123, 1098 XG Amsterdam. Directions can be found here.

Invited Participants

  • Pietro Belotti (FICO Xpress)
  • Santanu Dey (Georgia Tech)
  • Fritz Eisenbrand (École Polytechnique Fédérale de Lausanne)
  • Ambros Gleixner (Zuse Institute Berlin)
  • Rebecca Hoberg (University of Washington)
  • Rasmus Kyng (Harvard)
  • Alantha Newman (Université Grenoble Alpes)
  • Aleksandar Nikolov (University of Toronto)
  • Thomas Rothvoss (University of Washington)
  • Felipe Serrano (Zuse Institute Berlin)
  • Mohit Singh (Georgia Tech)
  • Andrea Tramontani (IBM CPLEX)
  • Sven Wiese (Mosek ApS)

Organizers

Nikhil Bansal (CWI & TU/e), Daniel Dadush (CWI), Andrea Lodi (Polytechnique Montreal)

NWO Veni Project : New Frontiers in Lattice Algorithms and Design.
ERC Consolidator Grant: Algorithms for Coping with Uncertainty and Intractability.

Sponsors