Integer linear programming

Attempting Eric Wastl’s Advent of Code introduced me to two integer linear programming problems:

\mathbf{x}, \quad x_i \in \mathbb{Z}_{\ge 0}, \quad i \in \{ 0, \ldots, n-1 \}, \quad n \in \mathbb{Z}_{\gt 0} \mathbf{b}, \quad b_j \in \mathbb{Z}_{\ge 0}, \quad j \in \{ 0, \ldots, m-1 \}, \quad m \in \mathbb{Z}_{\gt 0}

A, \quad a_{j,i} \in \{ 0,1 \}

Both problems minimise \sum_i x_i=\mathbf{1}^T\mathbf{x} (the objective), the first subject to:

(A\mathbf{x})_j \bmod 2 =b_j \bmod 2 \in \{0,1\}

and the second subject to:

A\mathbf{x}=\mathbf{b}.

Zero vector

If \mathbf{b}=\mathbf{0}, then the solutions are straightforward, as:

A\mathbf{0}=\mathbf{0}

Parity

Before turning to the solutions, the term ‘parity’ of an integer u is used to refer to u \bmod 2. If u is even, its parity is 0. If it is odd, its parity is 1.

Binary representation

If solutions exists, the way to a solution (I learnt but did not discover) is to write x_i in binary (the superscripts denote indexation, not powers):

x_i=x_i^{(0)}+2x_i^{(1)}+4x_i^{(2)}+\ldots+2^kx_i^{(k)}, \quad x_i^{(l)} \in \{0, 1\}, \quad l \in \{0, \ldots, k\}

or:

x_i=x_i^{(0)}+2(x_i^{(1)}+2x_i^{(2)}+\ldots+2^{k-1}x_i^{(k)})=x_i^{(0)}+2x'_i \mathbf{x}=\mathbf{x}^{(0)}+2\mathbf{x}'

Consequently:

\mathbf{1}^T\mathbf{x}=\mathbf{1}^T(\mathbf{x}^{(0)}+2\mathbf{x}')=\mathbf{1}^T\mathbf{x}^{(0)}+2\mathbf{1}^T\mathbf{x}'

For any given valid \mathbf{x}^{(0)}, any valid \mathbf{x}' that minimises \mathbf{1}^T\mathbf{x}' also minimises the objective.

Also:

\begin{equation}A\mathbf{x}=A\mathbf{x}^{(0)}+2A\mathbf{x}'=\mathbf{b}\end{equation}

Maintaining parity:

\begin{equation}(A\mathbf{x})_j \bmod 2 =(A\mathbf{x}^{(0)})_j \bmod 2=b_j \bmod 2\end{equation}

as 2(A\mathbf{x}')_j \bmod 2=0.

Solution to first problem

If n is relatively small, it is practical to find the possible solutions of equation (2) by brute force. There are 2^n possible values of \mathbf{x}^{(0)} to be considered. We can also rely on (where \oplus is exclusive or):

(A\mathbf{x}^{(0)})_j \bmod 2=\bigoplus_i A_{j,i}x^{(0)}_i=\bigoplus_{i:x_i^{(0)}=1} A_{j,i}

For any \mathbf{x}^{(0)}, \mathbf{x'}=\mathbf{0} is valid and minimises the objective.

Solution to second problem

Re-arranging equation (1):

A\mathbf{x}'=\frac{\mathbf{b}-A\mathbf{x}^{(0)}} {2} = \mathbf{b}'

As well as equation (2), we require that b'_j \in \mathbb Z_{\ge 0}, so, if \Delta_j=b_j-(A\mathbf{x}^{(0)})_j:

\Delta_j \ge 0

and

\Delta_j \bmod 2=0

This problem, A\mathbf{x}'=\mathbf{b}', has the same form as the original problem, but b'_j \lt b_j and so it is ‘smaller’.

That is, the solution to (A, \mathbf{b}) is one that:

• minimises \mathbf{1}^T(\mathbf{x}^{(0)}+2\mathbf{x}') for all valid \mathbf{x}^{(0)} (satisfying the requirements above), where
• \mathbf{x}' is a solution to (A, \mathbf{b}'), given that \mathbf{x}^{(0)}.

The solution is, thereby, expressed recursively.