7

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Mengfan Ma
  • 173
  • 5
  • Can you post the log that cplex prints before and after? – user3680510 Jul 07 '20 at 07:44
  • 4
    @prubin has addressed this here : https://or.stackexchange.com/questions/2931/how-to-use-warm-start-to-solve-mips-efficiently/2935#2935 – Kuifje Jul 07 '20 at 09:52
  • @Kuifje I didn't add the time to generate a feasible solution. I only count the time consumed by cplex. – Mengfan Ma Jul 07 '20 at 09:58
  • @MengfanMa Read prubin's answer carefully : he explains why warm starting may result in a longer running time. – Kuifje Jul 07 '20 at 10:19
  • @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? – Mengfan Ma Jul 07 '20 at 14:09

1 Answers1

6

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.

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • What do you mean by “use of warm start when we solve many similar problems”? – Mengfan Ma Jul 16 '20 at 06:41
  • 1
    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$. – Nikos Kazazakis Jul 16 '20 at 10:15