8
$\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?

Improve this question
$\endgroup$
2
  • 2
    $\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, 2020 at 15:52
  • $\begingroup$ @Sune: you should make this an answer. $\endgroup$
    – prubin ♦
    Mar 15, 2020 at 19:30

3 Answers 3

Reset to default
8
$\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$
8
  • $\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, 2020 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, 2020 at 9:26
  • 2
    $\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, 2020 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, 2020 at 10:57
  • 2
    $\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, 2020 at 12:58
2
$\begingroup$

I want to expand on @Sunes answer, as I too wanted to solve the LP relaxation of my MIP and thought, there must be another solution than to convert each variable manually (at least this is how I interpreted @Sunes answer and it sounded needlessly complex). Therefore, I unnecessarily used up a lot more time searching through the internet for alternatives (without success).

It happens that you can convert a whole IloNum/Int/BoolVarArray at once and using IloConversion is way simpler than it sounds. Assuming you have your MIP model in an IloModel model and that you have all your integer variables in an array y. Then creating the LP relaxation of your MIP is as easy as

IloConversion relax_y = IloConversion( env, y, ILOFLOAT );
model.add( relax_y );

To regain the original MIP model just execute

relax_y.end();
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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