Originally posted by: SystemAdmin

Hi,
I'm using some kind of cutting plane method, and I need some help.

So basically I'm resolving the whole relaxed LP after adding cuts from each iteration, but when the number of iterations gets big, it takes long. I'm calling cplex solver from Java in Unix.

I'm wondering if there's a way I can partially update the solution without having to resolve a whole new LP from each iteration. I know you could do that in an IP, but I don't know if anything can be done for LP as well.

Thank you.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm not sure what you mean by "partially update the solution". If you mean stop the solution before it reaches optimality, you can set time and/or iteration limits. If the cuts you add make the previous solution infeasible and you set limits, though, you might stop the solver before it has restored feasibility.

If you mean supplying a hot start, by default CPLEX will use the last solution as an initial basis and then pivot to restore feasibility (if necessary) and optimality.

One thing you might try is adding the cuts as lazy constraints, which will reduce the amount of "drag" that nonbinding cuts create.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

But lazy constraints are only applicable for MIP problems, not for LPs.

If you solve the LP, add rows, and then solve again, CPLEX should already do the right thing, namely start from the basis of the previous solve. But this is only true if you leave the ADVIND parameter on its default value (1) and if you are using one of the simplex algorithms (primal simplex or dual simplex) for solving the LPs. The barrier solver does not have warm start capabilities.

With cutting plane separation methods it is usually be best to use the dual simplex algorithm, because adding rows to an LP does not destroy the dual feasibility of a solution.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul - Sorry for the language confusion. I did mean I wanted a hot start.

Tobias - I didn't specify the algorithm in solving LPs. I kinda assumed CPLEX will pick what's best fit, but does it save time if I fix the solving algorithm? The output prints out a dual objective each time. I assume it's using dual simplex. That means it solves a brand new system every time I add a constraint?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Dual simplex is typically fastest when you add a single constraint (or a small number of constraints). I'm pretty sure it is hot-starting from the last basis (feasible before you added cuts) and doing dual simplex pivots to "repair" the basis (restore feasibility).

If you add a lot of constraints, though, I think it might be faster to use primal simplex (or, if there is lots of degeneracy, the barrier method). In any case, if you stick to the default setting and let CPLEX choose, it will probably make the best choice. I doubt that you gain much by specifying dual simplex.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you =)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It is typically not needed to specify the algorithm. If you solve your LP, then add constraints, and then solve again, this will automatically use the dual simplex algorithm (since the previous basis will still be dual feasible after adding constraints).

The fact that you see dual objectives in the log output indeed indicates that the dual simplex is used. It does not say that it solves from scratch.

In order to provide more details I would need to take a look at the logs. Could you please post two successive log outputs here? Please make sure to enclose the output in "code" tags (the word "code" in curly brackets before and after the log output; see the right "Plain Text Help" box when you enter your forum post). This is a feature of this forum software to display stuff verbatim.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Tobias Achterberg wrote:
> But lazy constraints are only applicable for MIP problems, not for LPs.

Yes, but adding them to an LP just turns the LP into a "MIP" that is solved at the root node. That said, I probably should have suggested addUserCut rather than addLazyConstraint. (Or is this unnecessary? Does CPLEX automatically shift constraints that have not recently been binding to a pool and out of the active constraint set when solving an LP?)

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization