Topic
  • 4 replies
  • Latest Post - ‏2013-01-11T11:06:22Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Maximize piece-wise linear convex functions through AMPL SOS2 instructions

‏2013-01-07T12:14:41Z |
I have been solving a problem of maximizing a utility function that can be convex or concave, with CPLEX through an AMPL file.

The function is linearized through the specific SOS2 instructions of AMPL for solvers (including CPLEX).
For maximization of concave functions CPLEX proves to have a good performance (better than formulating the SOS2 instructions by hand). However. if the linearized function is convex, CPLEX's performance decreases exponentially and is, for some problems, worse than if the SOS2 instructins were implicit into the model.

I would like to know how does CPLEX handle the problem if the AMPL SOS2 instructions represent a convex linear function (maximization), if does the same procedure as with concave or not and the reason of taking so many time to solve for this shape of objective function.

I have been checking the User's Manual for CPLEX (v12.1 PAGE 625), the AMPL book (Chapter 17) and the IBM ILOG AMPL v12.2 User’s Guide (pag. 30) but I am still not cleared about it.
I would appreciate any help.
Updated on 2013-01-11T11:06:22Z at 2013-01-11T11:06:22Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Maximize piece-wise linear convex functions through AMPL SOS2 instructions

    ‏2013-01-08T06:03:16Z  
    Maximizing a concave piecewise-linear function is a relatively easy problem that is equivalent to a continuous linear program. SOS2 is not need for maximizing a concave p-l function.

    Maximizing a convex piecewise-linear function is a much harder problem, which is equivalent to a mixed-integer linear program but not to a continuous linear program. Thus it is not surprising that CPLEX must do a lot more work to solve a problem of this kind. If you can describe your convex objective function using the piecewise-linear function notation described in Chapter 17 of the AMPL book, then you should use this notation and let AMPL set up the SOS2 formulation for CPLEX, rather than giving the SOS2 instructions explicitly yourself.

    Bob Fourer
    4er@ampl.com
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Maximize piece-wise linear convex functions through AMPL SOS2 instructions

    ‏2013-01-08T11:16:02Z  
    Maximizing a concave piecewise-linear function is a relatively easy problem that is equivalent to a continuous linear program. SOS2 is not need for maximizing a concave p-l function.

    Maximizing a convex piecewise-linear function is a much harder problem, which is equivalent to a mixed-integer linear program but not to a continuous linear program. Thus it is not surprising that CPLEX must do a lot more work to solve a problem of this kind. If you can describe your convex objective function using the piecewise-linear function notation described in Chapter 17 of the AMPL book, then you should use this notation and let AMPL set up the SOS2 formulation for CPLEX, rather than giving the SOS2 instructions explicitly yourself.

    Bob Fourer
    4er@ampl.com
    Thank you very much for your answer, Bob Fourer.

    I have already realized that for maximizing a concave piecewise-linear function, giving the SOS2 instructions through AMPL specific commands improves the performance of CPLEX to solve the problem because any extra integer variables are created and passed to CPLEX.

    But the shape of the utility function depends on a parameter which is set by the user in the data-set file before solving, so the objective function can be either convex or concave, being the model prepared to both. So my question is, if the user sets a parameter which puts the utility function with a convex shape, would the AMPL SOS2 instructions still compensate comparing with the SOS2 instructions given explicitly ?

    Once again thank you,

    Filipe
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Maximize piece-wise linear convex functions through AMPL SOS2 instructions

    ‏2013-01-10T15:26:52Z  
    Thank you very much for your answer, Bob Fourer.

    I have already realized that for maximizing a concave piecewise-linear function, giving the SOS2 instructions through AMPL specific commands improves the performance of CPLEX to solve the problem because any extra integer variables are created and passed to CPLEX.

    But the shape of the utility function depends on a parameter which is set by the user in the data-set file before solving, so the objective function can be either convex or concave, being the model prepared to both. So my question is, if the user sets a parameter which puts the utility function with a convex shape, would the AMPL SOS2 instructions still compensate comparing with the SOS2 instructions given explicitly ?

    Once again thank you,

    Filipe
    When maximizing a concave piecewise-linear function, no integer variables are needed, and therefore the SOS2 mechanism is not used.

    When maximizing a convex piecewise-linear function, the AMPL-to-CPLEX interface automatically generates the SOS2 instructions.

    After reading your data, AMPL can tell whether your piecewise-linear functions are concave or convex, and will process them correctly according to what it finds. AMPL will include the SOS2 instructions only in those cases where it finds the piecewise-linear functions to be not concave. Thus you should let AMPL take care of this and not try to supply the SOS2 instructions yourself.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Maximize piece-wise linear convex functions through AMPL SOS2 instructions

    ‏2013-01-11T11:06:22Z  
    When maximizing a concave piecewise-linear function, no integer variables are needed, and therefore the SOS2 mechanism is not used.

    When maximizing a convex piecewise-linear function, the AMPL-to-CPLEX interface automatically generates the SOS2 instructions.

    After reading your data, AMPL can tell whether your piecewise-linear functions are concave or convex, and will process them correctly according to what it finds. AMPL will include the SOS2 instructions only in those cases where it finds the piecewise-linear functions to be not concave. Thus you should let AMPL take care of this and not try to supply the SOS2 instructions yourself.
    Hello and thank you again,

    Ok, now I have got your point. If the shape is concave AMPL can translate into a LP problem and no additional integer variables are needed, contrary to non-concave shapes, where the variables created to linearize the function may be created introduced by AMPL to CPLEX in a special order, making easy the branching process of CPLEX.

    However, I have compared the overall performance of the AMPL+CPLEX solving process for maximizing the convex functions with the SOS2 AMPL instructions and a disaggregated formulation (where I create 2 real and one binary variable per linear segment) and curiously the best time performances (finding exactly the same final solution), were found in the second case.

    If is not asking too much, would you have some possible reason for this ?? Or, is it possible to happen in which conditions ? I was expecting SOS2 AMPL instructions for this convex functions to have best time performances.

    Thank you,
    Filipe