6
$\begingroup$

I have an IloCplex object which contains a MILP. Is there a way to obtain the objective value of its LP relaxation, without having to rewrite the entire model as an LP?

$\endgroup$
  • 1
    $\begingroup$ You can add an IloConversion of each variable to you IloModel object, and then solve the resulting model using a corresponding IloCplex object. In OPL you can run the covertAllIntVars() function on your OPL model and then solve the resulting model. I am almost sure that there is no equivalent to this function in Java or C++. $\endgroup$ – Sune Mar 15 at 15:52
  • $\begingroup$ @Sune: you should make this an answer. $\endgroup$ – prubin Mar 15 at 19:30
5
$\begingroup$

Based on @prubin's instigation, I have turned my comment into an answer: You can add an IloConversion of each variable to you IloModel object, and then solve the resulting model using a corresponding IloCplex object. In OPL you can run the covertAllIntVars() function on your OPL model and then solve the resulting model. I am almost sure that there is no equivalent to this function in Java or C++.

You can only add one IloConversion of a variable to a model, implying that you cannot add a conversion from ILOBOOL/ILOINT to ILOFLOAT, and then convert the LP relaxation back to a MIP by adding another IloConversion from ILOFLOAT to ILOBOOL/ILOINT. However, you can remove the first IloConversion by invoking the end() method on the corresponding IloExtractable. For more information, you can check this link https://www.ibm.com/support/knowledgecenter/SSSA5P_12.5.0/ilog.odms.ide.help/refcppopl/html/classes/IloConversion.html

| improve this answer | |
$\endgroup$
3
$\begingroup$

I think the standard method is to stop just after the root node has been solved. For example, using the C++ API:

// Uncomment the following line to disable CPLEX cuts:
// cplex.setParam(IloCplex::NumParam::CutsFactor, 0.0);

cplex.setParam(IloCplex::IntParam::NodeLim, 0);
cplex.solve();

const auto linear_relaxation_obj = cplex.getBestObjValue();

// If you want to continue solving the MILP via branch-and-bound:
// cplex.setParam(IloCplex::NumParam::CutsFactor, -1.0);
cplex.setParam(IloCplex::IntParam::NodeLim, 999999999);

if(cplex.solve()) {
    // Fully solved the MILP
}

Setting NodeLim to 0 means CPLEX will stop after the root node is fully explored. Setting it to 1 will also perform branching and select the next node to explore.

Setting CutsFactor to a value between 0.0 and 1.0, CPLEX won't generate any cuts, thereby solving the linear relaxation of your original model. With CutsFactor at its default value -1.0, or at a value strictly larger than 1.0, CPLEX might add cuts at the root node, thus giving a tighter dual bound that you might have if solving the linear relaxation of the model.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Does CPLEX terminate after the first time the root node is solved, or just before it starts branching? There is a layer of cuts added in between those two. $\endgroup$ – Sune May 2 at 9:18
  • $\begingroup$ My understanding is that the root node is fully explored, including adding the cuts. I edited the answer. $\endgroup$ – Alberto Santini May 2 at 9:26
  • 1
    $\begingroup$ I thought so. It means that this method doesn't really solve the LP relaxation of the model extracted. So, if you want to compare the strength of a model, you have to be careful. $\endgroup$ – Sune May 2 at 10:36
  • $\begingroup$ Ah, I see what you mean. On the other hand, solving with all variables IloFloat doesn't add cuts? $\endgroup$ – Alberto Santini May 2 at 10:57
  • 1
    $\begingroup$ I think, in some sense, you are right. However, yet another thing you need to be aware of is that the presolve performs a lot of presolve reduction and tightening on a MIP, which it cannot do on an LP. Basically, it utilizes the logical implications from binary and integer variables in order to strengthen the formulation. Thus, using a node limit does not lead to a solution of the LP relaxation, but to a solution of a presolved, reduced and cut enhanced relaxation of the original model. $\endgroup$ – Sune May 2 at 12:58

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.