I have formulated an Integer programming problem with around variables and 30 constraints. I observe that the relaxed LP takes same time to execute (around 5 minutes) as the original IP. How is it possible when Linear programming problem is polynomial time solvable and IP is not?
Perhaps your IP is equivalent to an LP - for example single-commodity flows (including shortest path) are solvable as LP.
@Charlie: I am using glpk to solve both IP and lp. And I know the original problem for which IP is formulated is np complete. So the IP and LP cannot be equivalent
Rajib K Das , it's not quite clear to me the following issue
You have the same solution time for the original problem (IP) and the the relaxed one. But what about the solution itself - is the solution of the relaxed problem also integer or not? If it is, it may mean that the software just solves the relaxed version of an IP problem and if the result is already integer, does nothing more?
By the way, how many variables is in your problem? Solving an LP problem with 30 constraints in 5 minutes is very long as for the present day computers.
@prez...Thanks for the reply. It may be possible if the software solves IP that way. Indeed the solution to the relaxed problem are integers. Solution takes 5 minutes for 500 variables and 45 constraints.
500 variables and 45 constraints - it made me think it may be a kind of the transportation problem. The variables are double indexed (x_ij, i=1,2,....24,25;j=1,2....19,20). Your constraints are 25 sums of variables over the index i equal to integers, 20 sums of variables over the index j equal to integers (and probably also 500 non-negativity constraints on variables). If I am right about your model, then the existence of at least one integer solution is "guaranteed" since all the vertices of the feasible set are integer (this is what Michael Patriksson said about single-commodity flows).
PS. I created a test problem ("compatible" with what described above) with random parameters and I solved it in Excel 2019 with OpenSolver 2.9.0. The computation took about 5 seconds rather minutes, no matter with integers constraints on variables or without.
In the case when the constraints matrix is totally unimodular (every square nonsingular submatrix has determinant equal to +1 or -1), the relaxation of the considered integer LP can be solved by the simplex algorithm and the obtained solution will be also integer. In this situation, you will get the same execution time. However, when the matrix does not verifiy this property, the problem will be solved by the branch and bound or the branch and cut algorithm, so the execution time necessary for solving the orginal problem will be greater than the execution time necessary for solving the relaxed problem.
@prze.. I was wrong about the problem size it is actually much bigger. This is not transportation problem. Your idea that solution of Lp was used to solve IP led me to think why solution of lp would be integers in this case and I figured it out. Thanks all the same.
- Badges
- Science topic
- Similar topics
- Computer Science
- Computer Communications (Networks)
- Internet