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 size of 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 inequalities were $x_i \geq 0$, $x_i\leq 1$, and $x_i+x_j+x_k\leq 2$ whenever the three points $i,j,k$ form a line. The aim is then to maximize $\sum x_i$. 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 second application of integer programming was the following routine, 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. $$

Let $A$ be the solid cube $[0,1]^{3^n}$, and $B$ its set of vertices $\{0,1\}^{3^n}$. The following then holds, $$c'_n = \max_{x\in B} f(x) = \max_{x\in A} 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 minimized using Matlab's built-in minimization routine, and found a 124-point subset of $[3]^5$ with no geometric lines.

A third application of integer programming is expanded in some detail in Section \ref{moser-upper-sec}. Each point was classified by how many of its coordinates were 2. All the possible histograms or `statistics' of points in a low-dimensional line-free set were computed by brute-force. Since a low-dimensional space fits into a higher-dimensional space in many ways, the low-dimensional statistics have consequences for higher-dimensional sets. Many dozens of inequalities were found for six-dimensional and higher spaces, and Maple's integer programming routine was used to find upper bounds on $c'_n$.

A fourth application of integer programming found many of our best lower bounds for both the DHJ problem and the Moser problem. Assume that a solution is made up of complete $\Gamma(a,b,c)$ cells. This drastically reduces the number of variables, from $3^n$ to $(n+2)(n+1)/2$ binary variables, one for each Gamma set. In the DHJ problem, points in a combinatorial line will lie in cells of the form $\Gamma(a+r,b,c)$, $\Gamma(a,b+r,c)$ and $\Gamma(a,b,c+r)$ for some positive $r$. Thus the line-free condition is met if we prevent equilateral triangles of this sort. The Fujimura problem was to maximize the number of Gamma sets under this restriction, searching over the $(n+2)(n+1)/2$ binary variables. To maximize the total number of points, each Gamma set $\Gamma(a,b,c)$ is weighted by its size $(a+b+c)!/(a!b!c!)$, but the restrictions are the same.

Conversely, an attempt was made to disprove the `hyper-optimistic conjecture' mentioned in the Introduction. Each point of $[3]^n$ was given a weight of $1/(a!b!c!)$ when the point's coordinates included $a$ 1s, $b$ 2s and $c$ 3s. This gave each $\Gamma_{a,b,c}$ cell an equal weight of 1. In fact, since an integer programming routine was being used, each point was given the weight $(a+b+c)!/(a!b!c!)$. These numbers quickly grew too large for the routine.

In the Moser-Fujimura problem, we look for collections of $\Gamma(a,b,c)$ that do not contain geometric lines. This is satisfied if there are no isosceles triangles of the form $(a+r,b,c+s)$, $(a,b+r+s,c)$, $(a+s,b,c+r)$. Again, we run a search over the $(n+2)(n+1)/2$ binary variables, with $\Gamma(a,b,c)$ weighted by $(a+b+c)!/(a!b!c!)$, to maximize the total number of points.