Bertrand Guenin - optimization

A number is dyadic if it is an integer multiple of \(\frac{1}{2^k}\) for some integer \(k\geq 0\). Dyadic numbers play an important role in computer science as they are exactly the numbers that have a finite binary expansion. A vector is dyadic if every entry is dyadic. A dyadic program is an optimization problem of the form,

We prove in that solving dyadic programs can be done in time polynomial in the size of the instance.

To the best of our knowledge, and somewhat surprisingly in light of its practical relevance, this is the first paper to look at this class of optimization problems in its full generality. However, dyadic solutions in optimization problems arise in a beautiful conjecture of Paul Seymour from the mid 1970s which will be discussed in the next section. The key insight is to prove that a rational polyhedron contains a dyadic point if and only if its affine hull does.

The sparsity of a vector is the cardinality of its support. Let \(A\) be an \(m\times n\) integer matrix and let \(b\) be an integer vector with \(m\) entries. We proved that if \(Ax=b\), \(x\geq{\bf 0}\) has a dyadic solution then it has one of sparsity of at most \(2m \log_3 (3\sqrt{m}\|A\|_{\infty})\). All of these results rely on Siegel's Lemma, a tool from the Geometry of Numbers. We also established lower bound on the sparsity of dyadic solutions. However, there remains a large gap between the lower and upper bounds.

Dyadic programs share features of both linear programs and integer programs. For instance, solving dyadic programs and linear programs can be done in polynomial time, however, the sparsity bounds for dyadic programs are similar to that of integer programs. Ultimately, a better understanding of where dyadic programs lie on the spectrum between linear and integer programs will benefit the integer programming community. Seymour's dyadic conjecture, to be discussed in the next section, was our original motivation for this project. We believe that to address this conjecture it needs to be viewed in the more general context of dyadic programs.

Seymour's Dyadic Conjecture

\[ \min\{c^\top x:Mx\geq{\bf 1}, x\geq{\bf 0}, \mbox{\(x\) is integer}\} \quad\quad (IP), \]

where \(M\) is a \(0,1\) matrix and \(c\) is non-negative. There has been a considerable interest in this problem, both because of its practical relevance and theoretical importance. The decision problem associated with (IP) is NP-complete. However (IP) can be solved via linear programming when the feasible region \(\{x:Mx\geq{\bf 1}, x\geq{\bf 0}\}\) forms an integral polyhedron, i.e., all extreme points are integer. In that case we say that \(M\) is ideal. When the polytope \(\{x:Mx\leq{\bf 1}, x\geq{\bf 0}\}\) is integral the matrix \(M\) is said to be perfect. By the work of Fulkerson, Padberg, and Chvatal, we know that the study of perfect matrices reduces to that of perfect graphs. Ideal matrices are not associated with a single combinatorial object and hence are both richer and more challenging to understand than perfect matrices.

A \(0,1\) matrix \(M\) is Mengerian if for every non-negative integer \(c\), the last Linear Program (D) has an optimal solution that is integer. It follows from a result of Edmonds and Giles that Mengerian matrices are ideal, however, the converse does not hold in general. (The matrix whose rows are the triangles of \(K_4\) (viewed as sets of edges) is ideal but not Mengerian.) Seymour in 1975 conjectured however, that the following weaker statement should hold,

The Dyadic Conjecture

If \(M\) is ideal and \(c\geq{\bf 0}\) is integer, then (D) has an optimal solution \(y\) that is dyadic.

The Dyadic Conjecture is settled for some special cases. This includes the cases where the columns of \(M\) correspond to the edges of a graph or arcs of a digraph, and the rows of \(M\) correspond any of,

For (1), (2), (3) it is proved that the dual (D) has an optimal \(\frac12\)-integer solution. Result (3) is a restatement of the celebrated result of Luchesi and Younger and says that (D) has an integer solution in that case.

The aforementioned results focus on special classes of matrix \(M\). We were able to recently show a result about arbitrary ideal matrices, namely we proved that the conjecture holds for all ideal matrices \(M\) and all integer \(c\geq{\bf 0}\) for which (IP) has optimal value two.

Total Dual Integrality and beyond

Consider a system of linear inequalities \(Mx\leq b\) where \(M,b\) are integer, and the matrix \(M\) has \(n\) columns. The system \(Mx\leq b\) is Totally Dual Integral (TDI) if for every \(w\in{\mathbb Z}^n\) for which the linear program,

has an optimal solution, it has an optimal solution that is integral. Many classical minimax results, such as Menger's theorem, can be stated as some associated TDI system being integral.

A necessary condition for \(Mx\leq b\) to be TDI is that the polyhedron \(Q=\{x \in {\mathbb R}^n : Mx\leq b\}\) be integral, i.e. that every extreme point of \(Q\) is integral. However, this is not a sufficient condition. TDI is defined as an algebraic condition, integrality of the associated polyhedron \(Q\) is a geometric condition.

Question

Can we find a ‘geometric’ characterization of TDI?

We can do so when we require that the system is non-degenerate. Here, \(Mx\leq b\) is non-degenerate if for every minimal proper face \(F\) of \(\{x:Mx\leq b\}\) the left-hand sides of the tight constraints defining \(F\), are linearly independent.

To state our results we need a key definition. Consider a matrix \(M\in{\mathbb Z}^{m\times n}\) and a vector \(b\in{\mathbb Z}^m\). The system \(Mx\leq b\) is resilient if \(Q:=\{x \in {\mathbb R}^n :Mx\leq b\}\) is integral and for every \(i\in\{1,2, \ldots,m\}\),

We prove the following result that characterizes TDI for the non-degenerate case,

Theorem 1

Consider matrix \(M\in{\mathbb Z}^{m\times n}\) and vector \(b\in{\mathbb Z}^m\). Suppose that \(Q=\{x \in {\mathbb R}^n : Mx\leq b\}\) is full-dimensional and \(Mx\leq b\) is non-degenerate. Then \(Mx\leq b\) is TDI if and only if \(Mx\leq b\) is resilient.

This result was an unexpected offshoot of a theory that studies variants of Total Dual Integrality. Namely, we say that a system \(Mx\leq b\) is Totally Dual \(p\)-adic if for every \(w\in{\mathbb Z}^n\) for which the linear program (\(\star\)) has an optimal solution, then it has an optimal solution where all variables \(y\) are \(p\)-adic where \(p\geq 2\) is a prime. Here, a number is \(p\)-adic if it is an integer multiple of \(\frac{1}{p^k}\) for some integer \(k\geq 0\).

The Dyadic Conjecture can be restated in this language, namely it predicts that given a \(0,1\) matrix \(M\) for which the polyhedron \(\{x\geq {\bf 0}:Mx\geq {\bf 1}\}\) is integral, the system \(Mx\geq {\bf 1}, x\geq {\bf 0}\) is Totally Dual \(2\)-adic.

Foundational theory for the study of Totally Dual \(p\)-adic system can be found in,

Bertrand Guenin - optimization

Dyadic Programming

Seymour's Dyadic Conjecture

Total Dual Integrality and beyond