What are the conditions to be met by a LP that allows to infer that its optimum solution will be integral? Is total unimodularity a necessary and/or sufficient condition? What if all variables are binary?
Asked
Active
Viewed 209 times
1 Answers
0
Total unimodularity is a sufficient condition. To see that there are probably no interesting general necessary conditions (except trivial necessary conditions like no equality has coefficients that are linearly independent over the rationals, unless 0 is a solution), note that you can take ANY set of integer points and take the convex hull, and the set of equations/inequalities that define this arbitrary convex hull will give you constraints for a linear program where an optimal solution can be assumed to only have integer entries.
user2566092
- 26,142