Some snippets from days 2 and 3 at the BIRS-CMO Workshop on Discrete Optimization in Oaxaca.

Thomas
Rothvoss presented his work
on constructive
discrepancy minimization for convex sets
(slides
are available). The basic problem is that of assigning one of two
colors \(\chi(i)\) to each \(i \in [n]:=\{1,\dots,n\}\) of \(n\)
items represented by \(\{-1,+1\}\) such that for a system of sets
\(\cal{S} = \{S_1,\dots,S_m\}\) with \(S_i \in [n]\) we minimize
the maximum "mismatch", defined as the *discrepancy*:

I found the techniques developed fairly deep, and would find use in lots of applications (i.e., for proving results on other optimization problems; Thomas talked about an application to bin packing). We had previously looked at the somewhat related problem of number partitioning. There, we assign a set of integers \(\{a_1, \dots, a_n\}\) to two sets such that the sums of the numbers over the two sets are as close to each other as possible (the difference between these two sums is the

*discrepancy*here). At the same time, the corresponding alternative definition of discrepancy given as

would make the problem sort of "easy" here. With that objective, one could prove that a random assignment of \(\pm 1\) would perhaps do as well as we can. Nonetheless, an appropriately defined notion of "weighted" discrepancy, where each element now has, say, nonnegative weights, would be interesting to consider. It appears a generalization to more than two colors would be interesting, but perhaps tricky to establish the building blocks of results.

Tamon Stephen
talked about a variant of
the Hirsch
conjecture
using circuit
diameter of polyhedra, instead of the
default graph
diameter. See
the preprint for an
illustration of circuit distance between vertices of a polyhedron
- unlike the graph diameter, it's not symmetric. The idea is that
one is allowed to take "shortcuts" along the interior of the
polyhedron along with the walks along the edges. In that sense,
it's mixing the ideas of the default simplex method and the
interior point method for solving linear programs (LPs). The
authors show that the most basic counterexample to the Hirsch
conjecture, the Klee-Walkup polyhedron, in fact satisfies the
Hirsch bound. It would be interesting for software programs that
solve LPs to be able to *seamlessly* and *intelligently*
switch back and forth between interior point and simplex methods
(a basic ability to do so is already provided by some of the
state-of-the-art solvers)

Juan Pablo Vielma talked about when are Minkowski sums good/bad in the context of formulations for unions of polyhedra, and for unions of convex sets in general (the slides should be up soon here; but other versions are already available). For unions of polyhedra, aggregated formulations are often "short", but are not as tight as disaggregated ones (also termed extended formulations). The latter formulations are sharp/ideal, but are often too large in size (see the excellent review on MIP formulation techniques by JP Vielma, or lectures 5-7 from my IP class for a shorter overview). This interesting line of work tries to find a better middle ground by finding the sharpest formulations that are not extended, i.e., without having to add extra variables. Things get very interesting when one considers unions of convex sets (in place of polyhedra)!