Originally posted by: Gilead

Dear all,

I have implemented (Cplex and C++API) a cutting plane algorithm to solve a LP with an exponential number of constraints. To solve this LP, I'm extracting the initial model, I solve it and then, while I'm able to find violated constraints, I'm adding them using the addCut method of IloCplex and solve the problem again.

Everything seem to work correctly.

As the initial model is already big, I'm not surprised that the reopimization is quite long.

Nevertheless, when I turned to 5 the parameter IloCplex::Param::MIP::Display, I observed that each time I'm adding constraints, the reoptimization seems to restart from the solution of the initial model (the first dual objective is more or less the value of the first LP solution) and not from the last solution.

Is it a normal behaviour ?

As the convergence is slow, it takes a lot of time just to reach the dual bound I get from the last iteration of my algorithm. Is there an easy way to tell cplex to start with the very last solution ?

Pierre

The default setting for the advanced start switch parameter is 1.  If I understand correctly, you should try setting it to 2.

Originally posted by: Gilead

Thanks for this quick answer.

But unfortunately, it doesn't work. It still starts each reoptimization from the solution of the original model.

For what you are doing a UserCutCallback seems more appropriate than calling CPLEX in a loop. Any reason not to use that?

Originally posted by: Gilead

In fact, I'm studying formulations for the ATSP by comparing the dual bounds I can obtain from their linear relaxation.

I think UserCutCallback is called only when solving a MIP and not a LP. I could switch my formulation in a MIP and use a UserCutCallback, but in this case, I have to turn off, one by one, all the generation of generic cuts of cplex and other features (like heuristics and preprocessing ?) that can interfere on the solution of the linear relaxation. And I'm never sure to have turned off everything correctly.

Sorry, I am confused. In your first post you said you were adding additional constraints using addCut() but now you are saying you are solving your problem as an LP? Cuts are ignored for LPs, so I wonder what exactly you are doing?
 

Originally posted by: Gilead

     Hello,

I'm back from holidays !

Let me start again from beginning.

I have a LP with a class of constraints of exponential size. I can separate in polynomial time on this class of constraints and thus, I can solve the LP using a cutting planes method. To write a cutting planes using Cplex/Concert, I have two options :

1) define all my variables as continuous variables, and a starting reduced LP

solve the LPs with the solve() method of an IloCplex instance.

for each obtained solution, run my separation algorithm.

If the separation routine do not return any violated cuts, stop !

else add  the vioaletd cuts to my IloCplex instance with the method addCut() and start again the optimization.

The drawback of this method is that, at each iteration, the reoptimization starts from the solution of the first iteration and not the last one. This means that it has to add again and again all the generated inequalities instead of taking advantage from the last solution. As a result, the reoptimization becomes time consuming.

2) the second option is to declare my (or some) variables as integer and use the usercut and lazy constraints callbacks to manage the generation of the cutting planes.

The advantage of this method is that the reoptimization starts from the last solution and thus is quite faster than the previous method.

However, it has also some drawbacks. The main drawback is that, as I am interested in the LP relaxation solution of the formulation, I have to turn off all the feature given by Cplex for integer programs, that is generation of generic inequalities, preprocessing, heuristics, nad so on. The problem in this case is to guarantee that I have turned off everything and that the solution I get at the root node of the Branch-and-Bound correspond to the LP relaxation solution.

For the moment, I'm using the second method. But if anyone has a method to solve LP formulations with a pure cutting planes technique and Cplex as a linear solver, he's wellcome.

Pierre

First of all, in variant 1, since all variables are continuous, you are solving an LP, not a MIP. Thus you should use add(IloRange) (and not addCut(IloRange)) to augment the LP. With this CPLEX should use dual simplex and re-optimize from the previous optimal solution. Can you try using add() instead of addCut()?

If you really want to disable presolve and CPLEX cuts, then right now it looks like you are better off with variant 1. However, I am not clear what your concern is about the solution you get at the root of B&B. This should always correspond to the LP relaxation (which has potentially been enhanced by cuts). What exactly are you afraid of here?

Originally posted by: Gilead

Yes, in variant 1 I'm solving an LP. However, the class IlpCplex does not seem to contain an add(IloRange) method (it does not appear in the documentation and my code is not compiling) . Do you mean that I use the add(IloRange) method of the IloModel instance and extract again the model ? 

In variant 2, I would like to get the linear relaxation of the formulation, and not a solution enhanced by cuts, or anything else. Cplex is quite powerfull for MIP and I think part of it is due to the generation of inequalities and preprocessing. Cplex isn't it able to preprocess constraints and  reduce the domain definition of integral variables, based on the fact the problem is an IP instead of an LP ? If yes, the solution of the root node can be enhanced (wrt the linear relaxation solution) by preprocessing.

Yes, you should IloModel::add(IloRange). If the model is already extracted then there is no need to re-extract, since since should happen automatically.

If you have a MIP and want to solve its linear relaxation then you may want to temporarily drop the integrality constraints using IloConversion.

Originally posted by: Gilead

   Hi Daniel,

I didn't know that we could add constraints to the model without extracting and restarting from scratch.

Now, it's working well.

Thank's a lot.

Pierre