Converting exponential contraints into piecewise-linear constraints

[Farhana Sharmin Snigdha]

Hi Everyone,

I am very new in CPLEX world. I need to solve a problem where some of the constraints contain exponential terms. I was thinking to convert those exponential terms into piecewise linear constraints. Is it possible to implement that? Can anyone please provide an example how to write these constraints.

The constraints of the problem somewhat looks like below:

c1: x+y+z<=100;

c2: y-exp(p)=0;

c3: z-exp(q)=0;

Thanks

Farhana

[Robert Fourer]

There is a way to write piecewise-linear functions of one variable in AMPL; it is described in Chapter 17 of the AMPL book: http://ampl.com/BOOK/CHAPTERS/20-piecewise.pdf. This feature can be used to describe a piecewise-linear approximation to a nonlinear function of one variable, but you will need to choose your breakpoints and then compute the slopes between the breakpoints.

Probably a better approach is to use, instead of CPLEX, a solver designed for nonlinear problems; many nonlinear solvers are described on the solver pages of the AMPL website: http://ampl.com/products/solvers/. You can experiment with these solvers using the NEOS Server: http://www.neos-server.org/neos/.

Bob Fourer
am...@googlegroups.com

=======

[Farhana Sharmin Snigdha]

Thanks a lot. I was also looking into this chapter. As I am new at this, all these syntaxes seem difficult.

Previously I was trying to solve my problem using BARON solver as it is a nonlinear solver. But I only had the trial version which only supports upto 10 variables. Does KNITRO solver work in the same manner? My supervisor was suggesting to go with linear solver as these are more efficient. What is the speed ratio for CPLEX and KNITRO?  Will it be more efficient if I convert all the nonlinear constraints into piecewise-linear forms?

Thanks

Farhana

[Robert Fourer]

Linear solvers are more efficient in solving linear problems, but piecewise-linearization tends to slow them down because a lot more variables are created in forming the piecewise-linear approximation; also since it is only an approximation, the results are not exact. Moreover for all solvers, performance depends on the structure of the problem in ways that are very hard to predict. Thus to find out which solver works best for the problems of interest to you, you will have to experiment with different solvers. I suggest trying to get results with nonlinear solvers like KNITRO first, since they are designed for nonlinear problems; if they do not give good solutions, then try switching to piecewise-linear formulations with some linear solvers.

[Farhana Sharmin Snigdha]

Thanks a lot.