Attempting Eric Wastl’s Advent of Code introduced me to an integer linear programming problem:
\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 \}
Minimise \sum_i x_i=\mathbf{1}^T\mathbf{x} subject to A\mathbf{x}=\mathbf{b}.
Solution
If a solution exists, the solution (I learnt but did not discover) is to write x_i in binary:
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:
\mathbf{x}=\mathbf{x}^{(0)}+2\mathbf{x}'Consequently:
A\mathbf{x}=A\mathbf{x}^{(0)}+2A\mathbf{x}'=\mathbf{b}and, re-arranging:
A\mathbf{x}'=\frac{\mathbf{b}-A\mathbf{x}^{(0)}} {2} = \mathbf{b}'
We require that b'_j \in \mathbb Z_{\ge 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’. Also:
A\mathbf{0}=\mathbf{0}and
A\mathbf{x} \pmod 2 =A\mathbf{x}^{(0)} \pmod 2=\mathbf{b} \pmod 2
as
(u \bmod 2) \bmod 2 =u \bmod 2
(u + v) \bmod 2 =(u \bmod 2 + v \bmod 2)\bmod 2
uv \bmod 2 =(u \bmod 2)(v \bmod 2)
and
2u \bmod 2 = (2 \bmod 2)(u \bmod 2) = 0 \times (u \bmod 2) = 0
If n is relatively small, it is practical to find the possible solutions of:
A\mathbf{x}^{(0)} \pmod 2=\mathbf{b} \pmod 2, \quad b'_j \in \mathbb Z_{\ge 0}
by brute force.
For any given valid \mathbf{x}^{(0)}, any \mathbf{x}' that minimises \mathbf{1}^T\mathbf{x}' also minimises:
\mathbf{1}^T(\mathbf{x}^{(0)}+2\mathbf{x}')=\mathbf{1}^T\mathbf{x}^{(0)}+2\mathbf{1}^T\mathbf{x}'That is, the solution to (A, \mathbf{b}) is one minimising \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.