Yesterday I promised to show how to solve partition problems with integer linear programming. Let us take the problem of yesterday: We want to split the numbers from 1 to 30 in 10 triplets (x,y,z) such that x+y+z=0 modulo 31. We will use linear problems of the following type.

\(Ax=b, \quad x_i \in \{0,1\}, \quad c^T x \to \text{max.}\)

There will be one variable in x for each possible triplet. The value of this variable determines if the triplet is in the selection (1) or not (0). So the j-th column of A refers to the triplet with number j. The i-th row of A is a linear constraint which makes sure that the number i is used only in one triplet. A contaoins only 0-1-values, and

\(a_{i,j} = 1 \quad\Leftrightarrow\quad i \in T_j = \{n_{1,j},n_{2,j},n_{3,j}\}.\)

The constraints will be

\(\sum_j a_{i,j} x_j = 1.\)

We just need any feasible point and could use any target function. Alternatively, we could use „less equal“ in the previous line and maximize the number of triplets used.

How to do that in EMT? We first store all possible triplets into one matrix.

>function makeT (n:index=31) ...
$T=[];
$for i=1 to n-2;
$   for j=i+1 to n-1;
$       k=n-mod(i+j,n);
$       if k!=i and k!=j then T=T_[i,j,k]; endif;
$   end;
$end;
$return T
$endfunction
>makeT(7)
             1             2             4 
             1             4             2 
             1             6             7 
             2             4             1 
             2             5             7 
             3             4             7 
             3             5             6 
             3             6             5 
             5             6             3 
>T=makeT(31);

Then we define the matrix A.

>function makeA (T) ...
$v=sort(unique(flatten(T)));
$A=zeros(cols(v),rows(T));
$for i=1 to cols(v);
$   for j=1 to rows(T);
$       if any(v[i]==T[j]) then A[i,j]=1; endif;
$   end;
$end;
$return A;
$endfunction
>makeT(5)
             1             4             5 
             2             3             5 
>fraction makeA(makeT(5))
         1         0 
         0         1 
         0         1 
         1         0 
         1         1 
>A=makeA(T);
>size(A)
 [31,  405]

The function makeA() can take any matrix with partitions in its rows. The first command simply selects the numbers that appear in any partition. In our case, A is simply the vector [1,…,30].

Now we need to solve the problem with integer linear programming. We use the LPSOLVE library for this (given to EMT by the developers).

>function solveP (A,T) ...
$  x=ilpsolve(A,ones(rows(A))',ones(cols(A)),
$         vlb=zeros(cols(A)),vub=ones(cols(A)),>max);
$  return T[nonzeros(x')];
$  endfunction
>solveP(A,T)
               1             5            25 
               2             7            22 
               3            11            17 
               4             6            21 
               8             9            14 
              10            23            29 
              12            24            26 
              13            19            30 
              15            20            27 
              16            18            28 

The return value of the function ilpsolve() is a 0-1-vector. We want to print the triplets which are marked by 1 in this vector. The variables vlb and vub are lower and upper bounds for the variables. Interestingly, the solution works without these restrictions. Nevertheless, more restrictions usually mean shorter calculations.