7
$\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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you post the log that cplex prints before and after? $\endgroup$
    – user3680510
    Jul 7, 2020 at 7:44
  • 4
    $\begingroup$ @prubin has addressed this here : or.stackexchange.com/questions/2931/… $\endgroup$
    – Kuifje
    Jul 7, 2020 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, 2020 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, 2020 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, 2020 at 14:09

1 Answer 1

Reset to default
6
$\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$
2
  • $\begingroup$ What do you mean by “use of warm start when we solve many similar problems”? $\endgroup$
    – Mengfan Ma
    Jul 16, 2020 at 6:41
  • 1
    $\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, 2020 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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