What is the specific feature of the shortest path problem formulation the causes the integer solution?
The (constraint) matrix of the shortest-path problem formulation
is totally unimodular that guarantees the integral solution .
Thanks a lot dear Haldun;
If the technological matrix be totally uni-modular, can we conclude the linear relaxation solution is the same as integer solution? What are the right hand sides effects on this property? Do you have any document that proof uni-modularity of the constraint matrix?
It will be an integer solution. Right hand sides should be integer. Otherwise, it cannot be guaranteed. I suggest you look for sufficient conditions for total unimodularity, which can be find in the textbooks on integer/discrete optimization.
Here is a short proof of total unimodularity for the shortest path LP. By induction assume all square submatrices with fewer than n columns have determinants equal to 0,1 or -1. Let M be an square submatrix with n+1 columns. If any column of M is all zero M is singular and has determinant 0 If every column of M contains two nonzeros, they must be one 1 and one -1. so the sum of every column is zero, hence the rows are not linearly independent, M is singular, and thus M's determinant equals 0. Otherwise, compute the determinant of
M expanding by minors along a column with one nonzero. You get plus or minus 1 times the determinant of an n-1 by n-1 submatrix, which is 1,-1, or 0 by induction, so the determinant of M is +-1 or 0, completing the induction.
I took this proof from a book I'm finishing writing on linear programming with duality. --Craig
For the shortest path problem, the constraint matrix is totally unimodular, which guarantees the solution is on the extreme points of a polyhedron. One additional condition to guarantee the optimality after relaxing the integer constraint is that the objective function has to be separable convex (the objective of shortest path problem is linear).
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Materials Science
- Plating