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.
Topic

Re: Cutting plane implementation
20130217T22:28:55ZThis is the accepted answer. This is the accepted answer.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) 
Re: Cutting plane implementation
20130218T14:31:01ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130217T22:28:55Z
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)
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 
Re: Cutting plane implementation
20130218T14:51:51ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T14:31:01Z
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
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? 
Re: Cutting plane implementation
20130218T22:27:12ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T14:31:01Z
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
> 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) 
Re: Cutting plane implementation
20130218T22:30:57ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T14:51:51Z
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?
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) 
Re: Cutting plane implementation
20130222T13:42:36ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T22:30:57Z
Dual simplex is typically fastest when you add a single constraint (or a small number of constraints). I'm pretty sure it is hotstarting 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) 
Re: Cutting plane implementation
20130223T15:09:35ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T14:51:51Z
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?
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