Hi All,
I have modeled an MILP model using two different formulations, one of the formulation uses three indexes, while the other formulation uses five indexes. Comparing the solution speed of two formulations using the same solver (Gurobi, CPLEX), it turns out that the formulation with five indexes is solved faster by the solver. Not sure why this is happening, has anyone had this experience or are any studies related to this problem available. Please let me know.
Thanks,
Bhawesh
Of the same problem? Yes, oh yes. In large-scale integer or mixed-integer optimization, this is legio. And indeed, quite often a "richer" formulation (which typically means MANY more integer variables) means that the solver has more alternatives. Quite often the richer formulation will have a better duality gap, too.
Of course yes. In general, if you can find a better formulation for a problem that lead to a better bound on objective function, you can expect a better performance. The best formulation is one which defines the convex hull of the integer feasible solutions. Just an example: if you can formulate a MILP problem as a Max Flow network optimization problem, you might be able to relax integrality constraint and solve a LP problem and still get the Integer solution.
In fact, there are many ILP problems important from the practical point of view, which can be solved without using integer/binary constraints, namely the ones with totally unimodular matrix of constraint coefficients. It includes the max flow prolem mentioned by Hossein Tohidi, but also for example min cost/shortest path problems or binary assignment problems.
The time taken to solve an MILP depends not only on the number of variables and constraints, but also on many other factors, such as (a) the density of the constraint matrix, (b) the gap between the LP bound and the optimum and (c) the amount of symmetry present in the formulation. One of the most popular exact solution methods, branch-and-cut, is based on the iterative *addition* of constraints (called cutting planes), which cut off fractional LP solutions, while leaving integer solutions intact. The effect of adding such constraints is (usually) to strengthen the LP bound.
These Wikipedia entries may be useful:
https://en.wikipedia.org/wiki/Cutting-plane_method
https://en.wikipedia.org/wiki/Branch_and_cut
Thanks all for the answers. Expanding on the question a little bit, in the first model I used x_{ij} (truck going from node i to node j) as the decision variable, while in the second model the variable was x_{kij} (truck k going from node i to j). While solving the model, I put value of k=1, and both the models have the same constraints. I observe that the model with x_{kij} runs faster. Thanks
Generally, the speed of a solver depends on the dimension of the the constraints matrix. When the number of variables is large, the algorithm takes much time to solve it. The speed of a solver depends also on other parameters: the complexity of the mplemented algorithm, the structure of the constraints matrix, etc. If the two formulations that you have proposed have a slight difference in the number of variables,the speed will be approximatly the same. However, if there exists a large difference in the size of the two problems,the difference in the speed will be signifient.
- Badges
- Science topic
- Similar topics
- Mathematics