Integer Solutions of Linear Programming Problems
Answered
Identifying cases where the solution to an LP problem happens to be integer-valued 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/MATH233B-2017/lec3.pdf
- https://www.ise.ncsu.edu/fuzzy-neural/wp-content/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 right-hand side is integer-valued.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