15
$\begingroup$

When using the C callable library to solve a large LP, how can I get the best bound after calling the method CPXXlpopt? Does it depend on the algorithm used to solve the LP? I need this for cases in which the LP is too large and the Time Limit is reached without necessarily having an optimal LP solution.

When solving a MIP I can call the method CPXXgetbestobjval, however this only works for problems with integer variables. Is there something equivalent for pure LPs?

$\endgroup$
12
$\begingroup$

One option I think is to use CPXbaropt (barrier method) that produces intermediate dual (lower, for minimization) bounds.

If you are brave enough (and the number of variables is not really huge) you can declare the LP to be a MIP with no integer variables (or add a fictitious one), start with few randomly-chosen constraints and use lazycallback to add the remaining ones, on the fly, when they are violated.

(Maybe you can obtain something similar without the callback, just adding a dummy integer variable in the model and declaring most of the constraints in your model as lazy constraints.)

This will produce a sequence of lower bounds (for minimization problems), so at the timelimit you can retrieve the last one (I guess CPXgetbestobjval should work now).

We recently used a similar trick for solving bilinear problems with Cplex paper

EDIT: I assume that the question refers to a dual bound, i.e., lower bound for minimization.

$\endgroup$
  • 1
    $\begingroup$ Interior-point (=barrier) methods may not produce feasible solutions before optimum. Particularly if the employ the homogeneous model. Hence, I would be careful about using intermediate objective values. $\endgroup$ – ErlingMOSEK Jun 22 '19 at 15:00
  • $\begingroup$ But intermediate dual bounds (column Dual Obj in the log file) should be reliable, correct? $\endgroup$ – Matteo Fischetti Jun 22 '19 at 21:11
  • $\begingroup$ I almost sure dual inf. shows dual infeasibility. So in the final iterates maybe yes. $\endgroup$ – ErlingMOSEK Jun 23 '19 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.