1
$\begingroup$

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

$\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$
    – Math1000
    Feb 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$
    – beeflavor
    Feb 20, 2020 at 16:58

1 Answer 1

2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.