Originally posted by: alvarolorca

Suppose I am solving a linear program in maximization form and the optimal value is zstar (which I do not know before solving the problem). Now, suppose all I care about is not the exact value of zstar, but only of whether zstar is less than or equal to some value F or not. I understand the linear programming solvers implemented in Cplex maintain an upper bound of zstar, let's call it UB, obtained by solving a relaxed or dual version of the problem throughout the algorithm. Given this, can I stop the algorithm once UB is less than or equal to F, if this ever happens? (This would give me the guarantee that zstar is indeed less than or equal to F, without having to wait for full convergence, if that is the case.)

Thanks,

Alvaro

You are saying you solve a "linear program" but then you also speak about relaxations, so I am confused: does your problem contain integer variables or not?

Originally posted by: alvarolorca

I mean linear program. You are right, I should not have said "relaxed".

For a linear program I think parameter CPX_PARAM_OBJULIM should be helpful. It will stop the optimization as soon as the objective value goes beyond a certain limit.

You then have to check whether the CPLEX status is CPX_STAT_ABORT_OBJ_LIM to check why the optimization stopped.

Originally posted by: alvarolorca

But this is a maximization problem, so the current objective value only gives me a lower bound. What I meant is whether I can look at some UB and stop the process once UB is below a certain threshold.

Thanks anyways.

Originally posted by: RWunderling

Which limit is effective depends on the algorithm you use.  For a maximization problem, if you use the primal Simplex,
 CPX_PARAM_OBJULIM will be used, and if you use the dual Simplex CPX_PARAM_OBJLLIM will be used.  It would seem that using the dual serves your purpose.

Originally posted by: alvarolorca

I see what you mean. That works then, thanks so much.

Alvaro