# Total unimodularity and the set of optimizers

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}$$?

• I would like to say that (assuming the polyhedron defined by $Ax\leqslant b$ is bounded) an optimal solution to the LP is a convex combination of vertices at which the optimal value is attained, from which this claim follows readily. But I am not sure about this. Feb 19, 2020 at 22:30
• Thank you. In my application, $\{x: Ax \le b\}$ is unbounded but the set of optimizers are bounded. Feb 20, 2020 at 16:58

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.