Originally posted by: jdeboeck

Hello,

I am trying to see the effects of adding a MIP start solution to a MIP optimization problem with the addMIPstart(,) method in a java application. When an initial solution is added I can see it is well taken into consideration at the beginning of the solving as the best integer solution starts directly at the added solution. What surprises me is that the solving time is strongly increased on some instances with a initial start solution rather than without (time sometimes doubles).

What is the exact effect of addMIPstart ? Is it possible to add an initial start solution that will only be used as a minimum bound for the objective function to avoid searching in branchs where the solution isn't good engough? I don't want to use the start values to make decision over the branching order, I would like the branching order to be the same with and without MIPstart (so that the solving time shouldn't be worse with a MIPstart).

What parameters should I modify to get the wanted effect ? What parameters affect the branching order ?

Kind regards,

Jérôme De Boeck

What you observe is sort of expected and is known as performance variability. Providing additional information (in this case the MIP start) will change the path CPLEX takes through the search tree in order to solve your problem instance. These different search paths may result in significantly different solution times. On average, providing a MIP start should speed up the solve but there may well be some outliers on which things become slower. There is not too much you can do about that, this is just inherent to solving NP hard problems.

Still, here are some ideas/answers:

• In case you don't want to provide a start vector but only want to tell CPLEX that a feasible solution with a particular objective exists, you can use either CPX_PARAM_CUTLO or  CPX_PARAM_CUTUP.
• Branching order is defined by using a priroity order
• It may be worth while to take a closer look at the instances for which solution time doubles. Maybe you can parameter settings (for example disabling heuristics or using aggressive heuristics) that improve solution times on these instances and are also helpful in general.

Originally posted by: jdeboeck

Thank you, the CPX_PARAM_CUTLO and  CPX_PARAM_CUTUP. were the ones I was looking for.