Integer Solutions of Linear Programming Problems
AnsweredIdentifying cases where the solution to an LP problem happens to be integervalued without explicitly formulating it as an Integer Linear Programming (ILP) problem.
I understand that in some LP problems, the optimal solution coincidentally falls on integer coordinates due to the structure of the problem or the relationships among the constraints.
I'm interested in whether there are any indicators or rules of thumb that could help me identify such cases ?

Hi Sudheer,
This is a very interesting topic.
A powerful property related to this is Total Unimodularity. See for example the resources:
 https://theory.stanford.edu/~jvondrak/MATH233B2017/lec3.pdf
 https://www.ise.ncsu.edu/fuzzyneural/wpcontent/uploads/sites/9/2018/04/Lecture6.pdf > also contains some examples of problems satisfying this property
As described in the first link,
Totally unimodular matrices are very well behaved, because they always define polytopes with
integer vertices, as long as the righthand side is integervalued.A related property is Total Dual Integrality (see https://math.mit.edu/~goemans/18438F09/lec7.pdf).
Best regards,
Elisabeth
1
Please sign in to leave a comment.
Comments
1 comment