A good LP model, with a low gap is absolutely crucial for a good performance.
Unfortunately, this is not a guarantee ... you can have a good model, with a
small gap, but if there is a lot of symmetry in your model, it will still be a very
hard model to solve. Unfortunately symmetry is harder to measure.
As an example, one of my colleagues had a MIP model with a very bad
LP gap, and cplex was not able to solve if for more than 40 binary variables.
On the other hand, I have tried to see how far CPLEX could solve at knapsack
problem (5 min. time limit) and it could do that for up to 4 million binary variables.
This also shows that even NP-hard problems, of non-trivial size, can be solved
by modern solver software.
Define strong linear relaxation. I am familiar with LP relaxations, or relaxations of IPs or MIPs and the branch and bound technique and have not heard that term before.
If you mean LP relaxation, the answer will be simply "it depends" on the problem, the formulation of the original IP, and the IP that was relaxed to become a LP. If such is the question you are asking, it is kind of like asking if any sentence in a formal language once minimized will be short. Some may, some may not due to the construction. In some cases we may only have the basics to work off of (i.e., LP_opt
Dear Daniel
Good performance: The few numbers of explored nodes or the less computational time needed to obtain the optimum.
The integrality gap between the solution of an LP versus its IP may be an indication of how "far" away an answer is to its original counterpart. The quality of your LP solution will play a very important role on the number of nodes explored. With that being said, the closer the gap is between the IP and the LP solutions at best, the less nodes you will need to visit. Usually you don't want to solve the IP (as that's NP-hard), so it depends on the problem. Some will give you a nice gap that one can prove is true, while others really are elusive as their formulations do not work very well (for example, exponential number of constraints, etc...) or others are not even known to be produce constant-factored LP solutions away from an optimal value of a solution.
If anybody else can shed more light on this, I encourage it!
A good LP model, with a low gap is absolutely crucial for a good performance.
Unfortunately, this is not a guarantee ... you can have a good model, with a
small gap, but if there is a lot of symmetry in your model, it will still be a very
hard model to solve. Unfortunately symmetry is harder to measure.
As an example, one of my colleagues had a MIP model with a very bad
LP gap, and cplex was not able to solve if for more than 40 binary variables.
On the other hand, I have tried to see how far CPLEX could solve at knapsack
problem (5 min. time limit) and it could do that for up to 4 million binary variables.
This also shows that even NP-hard problems, of non-trivial size, can be solved
by modern solver software.
Dear Thomas,
I have also tried the knapsack with CPLEX. It could solve the large instances in a short time. However, your point about symmetry is right. I have experienced in symmetry breaking for the graph coloring problem . It has reduced the CPU time and node size. Moreover, symmetry breaking has improved the LP relaxation and the root node gap.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics