Originally posted by: HDing

Hi all,

I am solving a MIP problem in C++, and CPLEX can provide me an optimal solution. Then I feed this optimal solution to the same model again as the initial value (using cplex.addMIPStart). CPLEX accepts it:

1 of 1 MIP starts provided solutions.                                                       
MIP start 'm1' defined initial solution with objective 15.0000.

But the number of iterations (cplex.getNiterations) is bigger than the results from the first run, should it always be smaller or equal? I mean in general, when we can provide a good guess for an optimization problem, the performance (e.g. computational efficiency) should be increased. Why does CPLEX need more time when it has already a good initialization?

Thanks,

Hao
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

MIP performance is always hard to predict. The problem is NP-hard, so it may very well be that even a small difference in the data, the model, the parameters, the hardware, the CPLEX version, and so on can result in very big (exponential) run-time differences.

On average, providing a good MIP start (or even an optimal one) will improve performance. What I mean is that you have, say, 1000 models then solving them with MIP start will usually give you a performance improvement for more than half of the models. But this doesn't tell you anything what will happen for a single model.

LP is somewhat more predictable. If you provide a pretty good starting basis to the simplex algorithm, you will most often see a performance improvement.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: HDing

Thanks Tobias.

I agree that the MIP performance is hard to predict. But I still try to improve it using a guess initial guess because I believe my problem should be above average :).

I try to strict the data, model, parameters, hardware, etc. the same in different runnings. Besides these, do you have any suggestion on tuning the model/parameters in order to gain a better performance?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: HDing

Additionally, I did not change anything in the second run, only setting the MIPStart.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: HDing

I found another interesting thing. After the initialization by the result from the first run, (if it is a feasible solution for the second run, actually sometimes it is not even for the same problem), the time for finding the feasible solution is indeed disappeared, but CPLEX sometimes uses much more time to find a solution (larger Niterations) even when I fixed the search strategy by IloCplex::NodeSel.

What does CPLEX intend to do :s
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I guess with the second "find a solution" you mean to find the optimal solution and prove that it is optimal. Why do you consider changing the node selection strategy? This is typically not so relevant for performance (but of course, MIP is NP hard so any change can make a huge difference on a single model).

Regarding parameter tuning, you could try the tuning tool that comes with CPLEX 11 or later.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: HDing

Thanks Tobias.

Yes, second run means to find the optimal solution (with relatively less computational effort) and verify the result.

The reason why I try to fix the node selection strategy is that I don't want CPLEX changing its searching strategy in the second run which might cause more iterations.

I am using CPLEX 12.2 C++ Concert.

I probably find out the problem but I don't know whether my analysis is right or not and if it is right then how to solve it. The problem might be:
After providing the initialization, if it is a feasible solution in the second run, an upper bound of the cost can be determined, the overall computational time should be somehow saved, The time for finding a feasible solution and an upper bound of the cost is indeed vanished, but unfortunately the overall time (Niterations) is sometimes increased. Actually, I still cannot get it so far. Then I try to determine a lower bound for the cost in the second run (retaining the initialization), a strange behavior comes:
"CPLEX needs much more time for computing an optimal solution with lower and upper bounds than without."

More specifically for my case, I define the cost as an integer, changing from 1 to 15. The optimal cost is 14. After initialization for all the boolean decision variables from the first run without a lower bound, CPLEX starts its guess from cost 9. The Niterations is c.a. 2e4. When I set the lower bound as 14 with also initialization, the Niterations is 0, it is obvious. But when I set the lower bound as 13, the Niterations becomes c.a. 2e6. It is somehow out of my imagination, but I am still thinking...

Additionally, if I use the results of all the variables (including continuous and boolean variables) in the second run, CPLEX always said: no solution found ...

Hao
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am not quite sure whether I understand you correctly, so I am summarizing how I interpret what you have been doing before answering:

1. You solve the MIP problem P to minimize an integer variable 1 <= y <= 15 to optimality. The initial root LP relaxation value yields a lower bound of 9. CPLEX finds and proves the optimal solution of value 15 in 20,000 simplex iterations.
2. You solve the same problem P again, giving the optimal solution of value 15 as a MIP start and changing the lower bound of the objective function variable y to 14. This time, CPLEX needs much longer (2,000,000 simplex iterations) to prove optimality of the MIP start solution.
3. You wonder why this is the case, as in (2) you gave much more information to CPLEX than in (1).
As I said earlier, providing a MIP start is usually a good idea, but because MIP is NP-hard you never know and for a single model it could very well happen that it deteriorates the solver performance.

But: Providing a valid lower bound for a minimization problem (in your case by means of increasing the lower bound of y; more generally by adding a constraint c*x >= l) is typically a very bad idea.
This sounds counter-intuitive (as you reduce the search space often substantially by this constraint), but there is an algorithmic reason for this. Namely, adding a constraint that is parallel to the objective function makes your LP relaxation of the problem terribly degenerate. In the LP relaxation, you have suddenly a very big face of the LP polyhedron that is LP optimal. So, whatever CPLEX tries to do to get away from fractional solutions on this face (cutting planes or branching) will almost never show any effect in the objective function. In your case, CPLEX will stay at value 14 for the whole solving process until it finally proves that no solution of value 14 exists. The change in the objective function after adding a cut or branching on a variable is an important measure that CPLEX uses heuristically to decide whether the cut or branching was a good choice or not. Introducing this degeneracy means that CPLEX will conclude that none of its strategies has a positive effect and everything looks completely identical. This is particularly harmful to branching, as usually CPLEX tries to learn from previous branching decisions what it should do in the future. Thus, you may end up with almost random branchings, while without the lower objective bound CPLEX can identify the structurally important variables and come up with a much smaller search tree.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: CplexUser1453

Hello Tobias

You gave an excellent answer to the original question in this thread so here is mine :

Is there a set of conditions where an providing an initial solution will always (usually) work? Do you know about any acadamic references that talk about this? Alternatively are you aware of any paper where providing an initial solution to a B&B type algorithm dramatically improved performance (and it's clearly stated there)? (did not find much myself...)

Let me explain why am I asking this : I am dealing with some academic economists that are working on something that involves solving an optimization problem in two stages with CPLEX - the result of the first stage determines some contraints in the second stage. The solution of the first stage would also qualify as an initial solution for the second stage but it is not done at this point.

My economist friends insists on having an academic reference before they give me the budget to get an intern to try it (and knowing CPLEX better than they do I could definitely find other stuff that works)... Any help will be appreciated.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Sorry, I do not know any references that have this as a topic. Of course there are lots of papers that deal with problem specific heuristics, and I am sure that some of them would use such a heuristic solution as MIP start for a subsequent CPLEX run. But I do not know any comparisons on how this improved performance compared to plain CPLEX. But since this is a reasonable investigation, I am sure that such papers exist as well.

A few years ago, Emilie Danna (who worked for CPLEX at this time) conducted an experiment to find out what the best possible impact of heuristics could be. To do so, she provided the optimal solution to each of our internal test model in advance, and compared the solving times of these runs to the ones of plain CPLEX MIP. The result was that
(a) on individual models, the effect can be dramatic,
(b) on some other models you can even see a degradation from providing the optimal solution in advance,
(c) overall (in geometric mean) the time to optimality was reduced by 50%.

But note that this is dealing with time to optimality only (i.e., the time needed for CPLEX to find the optimal solution and to prove its optimality).
In practice, this is often not the appropriate measure. It often happens that you want to find a good solution in reasonable time, but the dual bound may not be that relevant to practitioners. And for this metric, primal solutions (or providing good solutions as MIP start) is much more important.

Tobias
#CPLEXOptimizers
#DecisionOptimization