Total unimodularity and the set of optimizers

Question

Suppose I have a totally unimodular matrix $A$ and an integral vector $b$. Consider for a vector $c$ the following linear program: $$ \max_x c^Tx \quad s.t.\quad Ax\le b $$ Let $S$ be the set of maximizers and let $S_{int} \subseteq S$ be the subset of integer-valued maximizers. Then is it true that $S = \mathrm{conv}(S_{int})$, i.e., $S$ is the convex hull of $S_{int}$?

Answer 1

According to the Minkowski representation theorem, every point in your feasible set is the sum of a convex combination of extreme points and a nonnegative combination of extreme directions. Every extreme point corresponds to at least one basic feasible solution (possibly more than one if the point is degenerate), and $A$ being TUM and $b$ being integer-valued means that every BFS (and so every extreme point) is integer-valued.

So it comes down to the extreme rays.

• If the feasible set is bounded (no feasible rays), your answer is yes.
• If it is unbounded but the objective function is strictly decreasing along every extreme ray, then your answer is yes, because the Minkowski representation of every optimal solution will necessarily have zero coefficients for every extreme ray.
• If it is unbounded and the objective increases along any extreme ray, the problem is unbounded and the question is meaningless (there are no optima).
• Finally, if the feasible region is unbounded, the objective function is nonincreasing along all extreme rays but constant along at least one, then the answer is no, because any optimal extreme point will anchor a ray of optimal solutions.