I can't find a way to efficiently use MIP starts in CPLEX java API.

I have a linear problem that I need to solve many times by changing just one constraint or changing the objective so I thought that starting from a solution (with MIP starts) could be a good way to speed up the calculations.

So in order to do that, after the first time I solve the problem, I save all variables in an array of IloNumVar and double that I pass to my other cplex objects with cplex.addMIPStart.

The problem is it doesn't speed up anything it makes it slower and gives me this message :

Warning: No solution found from 1 MIP starts.

So maybe I shouldn't give the MIP start all the variables but how do I know what variables to give it ?

I also tried to change the MIP start effort but it does not seem to make any difference ...

Why doesn't it make calculations faster ? Is there a better way to solve many problems that have just a few differences ?

asked 18 Mar '13, 04:30

lmarmiesse's gravatar image

lmarmiesse
2112
accept rate: 0%

You can experiment quite easily with this yourself. Using the old integer solution you can construct a sub mip problem in various ways, which acts as a "repair" problem. This will give you a better understanding of the difficulties your model changes poses. You might be able to use your local knowledge on the model structure and changes to construct a feasible solution.

(20 Mar '13, 06:45) Bo Jensen ♦

Btw : In the case of only changing the objective and your integer solution is for some reason still rejected, then you could calculate the new objective for the old integer solution and pass it as a cutoff as a fast fix.

(20 Mar '13, 06:47) Bo Jensen ♦

MIP start is a heuristics, in that it does not guarantee speedup. In the case of linear programming, it is relatively easy to update a solution (a basis) when you change one constraint. There is no such thing in MIP. When you provide a mip start, CPLEX will try to get a solution from it. If it can't it reports the warning you see. Then it resumes the search for a solution from scratch. Then, you get longer running times given the time spent on the mipstart is lost.

In you case it seems that the modifications you make to the problem yield to solutions that are quite different from the solution of the previous MIP problem. If you know of a way to modify the solution of the previous MIP into a solution to the second MIP then perform the transformation before providing it as a mip start.

link

answered 18 Mar '13, 05:25

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

edited 18 Mar '13, 18:10

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×1

Asked: 18 Mar '13, 04:30

Seen: 4,260 times

Last updated: 20 Mar '13, 06:47

OR-Exchange! Your site for questions, answers, and announcements about operations research.