Topic
  • 7 replies
  • Latest Post - ‏2013-02-23T15:09:35Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Cutting plane implementation

‏2013-02-17T15:50:33Z |
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.
Updated on 2013-02-23T15:09:35Z at 2013-02-23T15:09:35Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-17T22: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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-18T14:31:01Z  
    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)
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-18T14:51:51Z  
    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
    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?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-18T22:27:12Z  
    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 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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-18T22:30:57Z  
    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?
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-22T13:42:36Z  
    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)
    Thank you =)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Cutting plane implementation

    ‏2013-02-23T15:09:35Z  
    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?
    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