6
$\begingroup$

I have been working on a combinatorial optimization problem which can be modeled as an integer linear programming. I implemented it as a c++ project in visual studio 2017 and CPLEX1271. With the hope that my program would run faster, I use MIPStart to provide cplex a feasible solution. But the running time changed from 49s to 140s. All I did is providing a feasible solution to cplex, according to the answer, it cannot hurt the running time. Can anyone explain it?

UPDATE1: The log shows that cplex accept the solution.

UPDATE2: I've tested on hundreds of instances. It turned out that a warm start sometimes slows down cplex and at other times it accelerates cplex.

$\endgroup$
  • $\begingroup$ Can you post the log that cplex prints before and after? $\endgroup$ – user3680510 Jul 7 at 7:44
  • 4
    $\begingroup$ @prubin has addressed this here : or.stackexchange.com/questions/2931/… $\endgroup$ – Kuifje Jul 7 at 9:52
  • $\begingroup$ @Kuifje I didn't add the time to generate a feasible solution. I only count the time consumed by cplex. $\endgroup$ – Mengfan Ma Jul 7 at 9:58
  • $\begingroup$ @MengfanMa Read prubin's answer carefully : he explains why warm starting may result in a longer running time. $\endgroup$ – Kuifje Jul 7 at 10:19
  • $\begingroup$ @Kuifje I got it. But I think the answer is too short to get a full understanding. I was wondering if there is any other material on this topic? $\endgroup$ – Mengfan Ma Jul 7 at 14:09
3
$\begingroup$

If the solution you provided is not very good (i.e., it's far from the global optimum), it often leads the branch-and-bound algorithm down a different path, which ends up slowing down the overall solution time.

MIP solvers are very good in figuring this stuff out by themselves, so the best use of warm-start nowadays is when we solve many similar problems sequentially.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by “use of warm start when we solve many similar problems”? $\endgroup$ – Mengfan Ma Jul 16 at 6:41
  • $\begingroup$ This is part of many algorithms, e.g., a feasibility pump, where we only change the objective, or we fix some variables, or add a couple of constraints per iteration. In that case, the solution of problem $i+1$ is very likely to be very similar to the one of problem $i$. $\endgroup$ – Nikos Kazazakis Jul 16 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.