Originally posted by: SystemAdmin

[pinkopallino said:]

Dear all,

I have a good lower bound (LB) for a complex MIP model. In particular, the LB is often equal to the optimal solution of the MIP model (obviously, i know that because I solved the MIP model at the optimum value).

CPLEX spends a lot of time to prove that a solution found during the search is the optimum or not. In particular, I know that the GAP between the optimum solution (I know that is the best) and the LB generated by CPLEX is not good in this case, and I want to replace the CPLEX's LB with mine, that is better. Therefore, is somebody able to explain me how to set a lower bound for the objective function value in a minimization problem?

I know that I can add a constraint of the following type: O.F. >= LB
Somewhere, I found that the method to set a LB was to use the Double parameter ObjDif. But I see that this is not the right parameter.

So, please, suggest me the right way to solve this problem.

I'm using the callable library in Java.


Thanks in advance.
Robert
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=pinkopallino link=topic=1148.msg3291#msg3291 date=1242745232]
I know that I can add a constraint of the following type: O.F. >= LB


That's what I would do.

/Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[pinkopallino said:]

[quote author=prubin link=topic=1148.msg3303#msg3303 date=1242835716]
That's what I would do.


Ok, but in this case the performance of the search process decreases. It's like when, during a minimization process, you set a CutUp parameter too low.

Thanks.
Robert.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Well, if you know approximately what CPLEX's (looser) lower bound is going to be, say from a trial run, you can arguably accomplish what you want with a parameter.  Whether it would impact the solution performance (and, if so, whether the impact would be adverse or not) I have no idea; those things are generally random (at least from the user's viewpoint).

Let's say that CPLEX has a lower bound of LB' at the point that it bogs down trying to prove optimality, and your lower bound is LB > LB'.  Let Z* denote the current incumbent value (presumably Z* > LB, else you need to rethink your lower bound).  Now let's say that you set the parameter EpAGap to G = LB - LB' + epsilon for some not necessarily small epsilon.  If the gap drops down below G, then Z* < LB&#039; + G = LB + epsilon, so Z* is within epsilon of your bound and you&#039;ll want to declare victory and collect your winnings.&nbsp; Does that do you any good?<br />
/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[pinkopallino said:]

Thank you so much for your explanation.

How can I get the value of LB'?

Robert
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

The only way I can think of is a time-limited "pilot run" where you watch for the lower bound to get stuck.  It's important to understand that what I suggested only works if the lower bound gets permanently stuck at some level LB' lower than your valid bound LB.  Should CPLEX's lower bound increase above that before it gets an incumbent within epsilon of your bound, then the gap (which is based on that preliminary estimate LB', not the current lower bound) may cause CPLEX to stop with a solution you don't want.

Let me express that symbolically.  Let's say you do a pilot run and see the lower bound stabilize at some value LB' < LB (your bound).  So you set the absolute gap to G = LB - LB' + epsilon and restart.  If an integer feasible solution Z* is found [i]while the CPLEX lower bound is no bigger than[/i] LB', then Z* < current lower bound + G <= LB&#039; + G = LB + epsilon and you have a winner.&nbsp; However, if the CPLEX lower bound creeps up to some value LB&#039;&#039; > LB', and then an incumbent Z* is found, you have Z* < LB&#039;&#039; + G, but LB&#039;&#039; + G > LB' + G and you no longer know whether Z* < LB + epsilon.&nbsp; So CPLEX will stop, but the incumbent may not meet your standard for optimality.<br />
If there is any realistic chance that the CPLEX lower bound could exceed the "stable" lower bound LB' you observe in the pilot run before an optimal solution is found, then I think you have to bite the bullet and either (a) add a constraint asserting the lower bound LB on the objective or (b) add an incumbent callback that checks each new incumbent against your lower bound LB and stops the algorithm if an incumbent near enough to LB is found.

/Paul
#CPLEXOptimizers
#DecisionOptimization