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.
Topic
This topic has been locked.
4 replies
Latest Post
 20130111T11:06:22Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Maximize piecewise linear convex functions through AMPL SOS2 instructions
20130107T12:14:41Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130111T11:06:22Z at 20130111T11:06:22Z by SystemAdmin

ACCEPTED ANSWER
Re: Maximize piecewise linear convex functions through AMPL SOS2 instructions
20130108T06:03:16Z in response to SystemAdminMaximizing a concave piecewiselinear function is a relatively easy problem that is equivalent to a continuous linear program. SOS2 is not need for maximizing a concave pl function.
Maximizing a convex piecewiselinear function is a much harder problem, which is equivalent to a mixedinteger 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 piecewiselinear 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
ACCEPTED ANSWER
Re: Maximize piecewise linear convex functions through AMPL SOS2 instructions
20130108T11:16:02Z in response to SystemAdminThank you very much for your answer, Bob Fourer.
I have already realized that for maximizing a concave piecewiselinear 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 dataset 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
ACCEPTED ANSWER
Re: Maximize piecewise linear convex functions through AMPL SOS2 instructions
20130110T15:26:52Z in response to SystemAdminWhen maximizing a concave piecewiselinear function, no integer variables are needed, and therefore the SOS2 mechanism is not used.
When maximizing a convex piecewiselinear function, the AMPLtoCPLEX interface automatically generates the SOS2 instructions.
After reading your data, AMPL can tell whether your piecewiselinear 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 piecewiselinear functions to be not concave. Thus you should let AMPL take care of this and not try to supply the SOS2 instructions yourself.
ACCEPTED ANSWER
Re: Maximize piecewise linear convex functions through AMPL SOS2 instructions
20130111T11:06:22Z in response to SystemAdminHello 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 nonconcave 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


