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}$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– Math1000Feb 19, 2020 at 22:30
-
$\begingroup$ Thank you. In my application, $\{x: Ax \le b\}$ is unbounded but the set of optimizers are bounded. $\endgroup$– beeflavorFeb 20, 2020 at 16:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
