Integer.tex

\section{Integer programming}\label{integer-sec}

Integer programming is linear programming with solutions restricted to the integers. A number of packages, for example Maple.12, can solve these problems. It was used in several places during this project.

The first place it was used was to find $c_5$, the maximal subset of $[3]^5$ with no combinatorial lines. One 0/1-variable was used for each point in the cube, and one linear inequality for each combinatorial line. The computer found twelve solutions with 150 points, and found that there were no solutions with 151 points, so $c_5 = 150$. It follows easily that $c_6 = 450$, but the same program was used as a check to show that any set of 451 points in $[3]^6$ has a combinatorial line.

The following routine was used for the 5 dimensional Moser problem to show that $c'_5\ge 124$. Let G be the 3-hypergraph with vertex set equal to $[3]^5$ as before and set $(I,J,K)\in E_3$ to be a 3-edge if and only if it is a geometric line. $c'_5$ is then the size of a maximal independent set. Let

$$ f(x) = \Sum_I x_I - \Sum_{(I,J,K)\in E_3} x_Ix_Jx_K. $$

The following then holds,

$$c'_n = max_{x\in\{0,1\}^{3^n}} f(x) = max_{x\in [0,1]^{3^n}} f(x).$$

To check the first equality, if $V$ is a line-free set in $G$ of size $k$, set $x_J=1$ for $J\in V$, and zero otherwise. Then $f(x) = $k$ because $V$ is line-free, so all the cubic terms are zero. So $c'_n \le max_{x\in\{0,1\}^{3^n}} f(x)$. Conversely, if for some $x\in\{0,1\}^{3^n}$, $f(x)=k$ and if there are triplets $x_I=x_J=x_K=1$ with $(I,J,K)\in E_3$, we change $x_I$ to 0. This reduces $\sum_I x_I$ by 1 but also reduce the second term of $f(x)$ by at least one. So repeating we can find an $x\in\{0,1\}^{3^n}$ with $f(x)\ge k$ and $x_Ix_Jx_K=0$ if $(I,J,K)\in E_3$, i.e. an independent set of size $\ge k$. So $c'_n \ge max_{x\in\{0,1\}^{3^n}} f(x)$. The second equality follows from the maximum principle since $f$ is a square free polynomial. $-f$ was then minimized using Matlab's built-in minimization routine, and found a 124-point subset of $[3]^5$ with no geometric lines.

This is where we will discuss the integer programming algorithms used in the paper, including those for DHJ, Moser, Fujimura, weighted Fujimura, and weighted Moser-Fujimura. Please edit at

http://michaelnielsen.org/polymath1/index.php?title=Integer.tex