For a fixed
The set $ { x_h \mid Ax_h = 0, x_h \in \mathbb{Z}^d } $ is the set of integer solutions to the homogeneous system $ Ax = 0 $. This is a sublattice of $ \mathbb{Z}^d $ (a lattice contained within $ \mathbb{Z}^d $) because:
- It is closed under addition: if $ x_h, x_h' $ satisfy $ Ax_h = 0 $ and $ Ax_h' = 0 $, then $ A(x_h + x_h') = 0 $.
- It is closed under integer scaling: if $ Ax_h = 0 $ and $ k \in \mathbb{Z} $, then $ A(k x_h) = 0 $.
- It is discrete because $ \mathbb{Z}^d $ is discrete.
Thus, the set of integer solutions to $ Ax = b $ is a translate (by $ x_p $) of a sublattice of $ \mathbb{Z}^d $, which is itself a lattice.
We need to find one integer solution $ x_p $ to $ Ax = b $. This can be done using the SVD of $ A $ $$ A = U S V $$
The system $ Ax = b $ becomes:
$$ U S V x = b \implies S (V x) = U^{-1} b. $$
Let $ y = V x $ and $ b' = U^{-1} b
This system is easy to solve because $ S $ is diagonal.
Given that the set of integer solutions is a lattice $ { x_p + \sum_{i=1}^{d-r} k_i v_i \mid k_i \in \mathbb{Z} }
This is equivalent to: $$ \max \sum_{i=1}^{d-r} (c^T v_i) k_i + c^T x_p. $$
Since $ k_i \in \mathbb{Z} $, this is an unbounded problem unless $ c^T v_i = 0 $ for all $ i $. If $ c^T v_i \neq 0 $ for some $ i $, we can make $ c^T x $ arbitrarily large by choosing $ k_i $ appropriately (positive or negative depending on the sign of $ c^T v_i $).
Thus:
- If $ c^T v_i = 0 $ for all $ i $, then $ c^T x = c^T x_p $ is constant over all solutions, and $ x_p $ is optimal.
- Otherwise, the problem is unbounded.