AMPL non linear functions

[John]

HI! I have non linear functions in my model, I guess both convex and concave. I am using solver KNITRO.

According to the book there are several ways to do it:

1) use notation <<break points; slopes>>

2) handle non linear function with binary variables

3) SOS - special ordered sets

1. Which is better in terms of the speed?

2. which is easier to implement?

2. Is there any limitations to use built in mechanisms <<break points; slopes>> or SOS in terms of convexity?

BR

Evgeniy

[AMPL Google Group]

Knitro handles many kinds of nonlinear functions directly. Thus when using Knitro, you would only need to use <<breakpoints; slopes>> expressions if your application requires you to use piecewise-linear functions in the model formulation. Knitro cannot handle <<breakpoints; slopes>> expressions directly, but when possible, AMPL automatically transforms them to equivalent linear expressions before sending your problem to Knitro. Also where necessary (due to nonconvexity) AMPL's transformation adds integer variables and some auxiliary constraints. (Knitro does not handle SOS conditions.)

It is not possible to say what will work for your model, however, given only the information that you have provided. A lot depends on the specific objective and constraint functions that you are trying to use. Also if you have a choice of more than one formulation, you will need to test your formulations to determine which works better with the solver.

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

[John]

I am using AMPL and  knitroampl solver. I have continuous variable x and non linear function y=e^(-x) - like exponential distribution (for example). So how do I express this non linearity in the constraint?

среда, 12 февраля 2020 г., 17:48:35 UTC+1 пользователь AMPL Google Group написал:

[John]

I have just set not a good example. Lets say I have a chart (table) of values which are defined by the value of the x variable. for example param[x].

if x is continuous then the nearest x is selected and the value of param[x] is defined. If x integer the just param[x]. So here the point is that index is the variable.

среда, 12 февраля 2020 г., 17:48:35 UTC+1 пользователь AMPL Google Group написал:

Knitro handles many kinds of nonlinear functions directly. Thus when using Knitro, you would only need to use <<breakpoints; slopes>> expressions if your application requires you to use piecewise-linear functions in the model formulation. Knitro cannot handle <<breakpoints; slopes>> expressions directly, but when possible, AMPL automatically transforms them to equivalent linear expressions before sending your problem to Knitro. Also where necessary (due to nonconvexity) AMPL's transformation adds integer variables and some auxiliary constraints. (Knitro does not handle SOS conditions.)

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

[AMPL Google Group]

AMPL does not accept "p[x]" where p is a param and x is a variable. For a solver like Knitro, in general it's only possible to get the effect of p[x] by defining a lot of binary variables:

param N integer > 0;
param p {1..N}; # table of N values

var Xchoice {1..N} binary;
subject to oneX: sum {j in 1..N} Xchoice[j] = 1;
   # exactly one of the Xchoice[j] variables is 1
var X = sum {j in 1..N} j * Xchoice[j];
   # Xchoice[j] equals 1 if and only if X equals j

Then for p[X] you can write sum {j in 1..N} p[j] * Xchoice[j]. For a continuous X, you would need some constraints instead:

var X integer >= 1, <= N;
subj to Xlo: X >= sum {j in 1..N} j * Xchoice[j] - 0.5;
subj to Xhi: X <= sum {j in 1..N} j * Xchoice[j] + 0.5;

To answer your other question, for e^-x you can write exp(-x) in any AMPL objective or constraint expression.

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

On Wed, Feb 12, 2020 at 9:21 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I have just set not a good example. Lets say I have a chart (table) of values which are defined by the value of the x variable. for example param[x].

if x is continuous then the nearest x is selected and the value of param[x] is defined. If x integer the just param[x]. So here the point is that index is the variable.

On Wed, Feb 12, 2020 at 8:25 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I am using AMPL and knitroampl solver. I have continuous variable x and non linear function y=e^(-x) - like exponential distribution (for example). So how do I express this non linearity in the constraint?

On Wed, Feb 12, 2020 at 4:48 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Knitro handles many kinds of nonlinear functions directly. Thus when using Knitro, you would only need to use <<breakpoints; slopes>> expressions if your application requires you to use piecewise-linear functions in the model formulation. Knitro cannot handle <<breakpoints; slopes>> expressions directly, but when possible, AMPL automatically transforms them to equivalent linear expressions before sending your problem to Knitro. Also where necessary (due to nonconvexity) AMPL's transformation adds integer variables and some auxiliary constraints. (Knitro does not handle SOS conditions.)

It is not possible to say what will work for your model, however, given only the information that you have provided. A lot depends on the specific objective and constraint functions that you are trying to use. Also if you have a choice of more than one formulation, you will need to test your formulations to determine which works better with the solver.

--
Robert Fourer
am...@googlegroups.com

[John]

Dear Robert, thank you for reply. I have found that AMPL supports SOS2

https://ampl.com/faqs/how-can-i-use-the-solvers-special-ordered-sets-feature/

is it ok to use them with amplknitro solver for linearizon function y= f(x), x>=0 and continuous

John

четверг, 13 февраля 2020 г., 17:09:51 UTC+1 пользователь AMPL Google Group написал:

[AMPL Google Group]

Knitro does not handle special ordered set conditions. You can assign .sosno and .ref suffix values in AMPL (as described in the SOS FAQ), but Knitro will ignore those values.

Instead you should write the piecewise-linear approximation to f(x) in your model, using AMPL's << . . . ; . . . >> notation, and let AMPL convert this notation to a linear formulation that Knitro accepts.

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

On Fri, Feb 14, 2020 at 3:10 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Dear Robert, thank you for reply. I have found that AMPL supports SOS2
https://ampl.com/faqs/how-can-i-use-the-solvers-special-ordered-sets-feature/

is it ok to use them with amplknitro solver for linearizon function y= f(x), x>=0 and continuous

John

четверг, 13 февраля 2020 г., 17:09:51 UTC+1 пользователь AMPL Google Group написал:

AMPL does not accept "p[x]" where p is a param and x is a variable. For a solver like Knitro, in general it's only possible to get the effect of p[x] by defining a lot of binary variables:

param N integer > 0;
param p {1..N}; # table of N values

var Xchoice {1..N} binary;
subject to oneX: sum {j in 1..N} Xchoice[j] = 1;
# exactly one of the Xchoice[j] variables is 1
var X = sum {j in 1..N} j * Xchoice[j];
# Xchoice[j] equals 1 if and only if X equals j

Then for p[X] you can write sum {j in 1..N} p[j] * Xchoice[j]. For a continuous X, you would need some constraints instead:

var X integer >= 1, <= N;
subj to Xlo: X >= sum {j in 1..N} j * Xchoice[j] - 0.5;
subj to Xhi: X <= sum {j in 1..N} j * Xchoice[j] + 0.5;

To answer your other question, for e^-x you can write exp(-x) in any AMPL objective or constraint expression.

--
Robert Fourer

[url=javascript:]am...@googlegroups.com

On Thu, Feb 13, 2020 at 4:09 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

AMPL does not accept "p[x]" where p is a param and x is a variable. For a solver like Knitro, in general it's only possible to get the effect of p[x] by defining a lot of binary variables:

param N integer > 0;
param p {1..N}; # table of N values

var Xchoice {1..N} binary;
subject to oneX: sum {j in 1..N} Xchoice[j] = 1;
   # exactly one of the Xchoice[j] variables is 1
var X = sum {j in 1..N} j * Xchoice[j];
   # Xchoice[j] equals 1 if and only if X equals j

Then for p[X] you can write sum {j in 1..N} p[j] * Xchoice[j]. For a continuous X, you would need some constraints instead:

var X integer >= 1, <= N;
subj to Xlo: X >= sum {j in 1..N} j * Xchoice[j] - 0.5;
subj to Xhi: X <= sum {j in 1..N} j * Xchoice[j] + 0.5;

To answer your other question, for e^-x you can write exp(-x) in any AMPL objective or constraint expression.

--
Robert Fourer
am...@googlegroups.com

[Киселев Евгений]

Dear Robert,

Thank you for reply!

You have mentioned:

"Instead you should write the piecewise-linear approximation to f(x) in your model, using AMPL's << . . . ; . . . >> notation, and let AMPL convert this notation to a linear formulation that Knitro accepts".  

As well in one of the previous replies you mentioned that I could use the following (below is your example):

param N integer > 0;
param p {1..N}; # table of N values

var Xchoice {1..N} binary;
subject to oneX: sum {j in 1..N} Xchoice[j] = 1;
   # exactly one of the Xchoice[j] variables is 1
var X = sum {j in 1..N} j * Xchoice[j];
   # Xchoice[j] equals 1 if and only if X equals j

Then for p[X] you can write sum {j in 1..N} p[j] * Xchoice[j]. For a continuous X, you would need some constraints instead:

var X integer >= 1, <= N;
subj to Xlo: X >= sum {j in 1..N} j * Xchoice[j] - 0.5;
subj to Xhi: X <= sum {j in 1..N} j * Xchoice[j] + 0.5;

So the main question is  AMPL's << . . . ; . . . >> notation and notation with binary variables are the alternatives? Or in some cases << . . . ; . . . >> notation  will not work? My function is purely continuous not steep or discrete values.

As well have two subquestions:

1.  << . . . ; . . . >> notation requires << break  points ;  slopes >> ; .So, the "slopes" means degrees or some ratio. how slopes are defined for this notation?

2. If I have a non linear function of two or more variables, will  << . . . ; . . . >> notation work as well or formulation with binary variables isrequired?

In fact I could provide non linear piece wise formulation using continuous and binary variables for the function y=f(x):

#############

var x>=0; my decision variable    

set Vx := {0, 10, 20, 30, 40};  are the break points i.e some discrete points of my non linear function y= F (values of x)

set INTERVALS := {0-10, 10-20, 20-30, 30-40} ORDERED; intervals for the continuous  "x" decision variable  

param Y{Vx} := {0, 50, 90, 180, 450}; set of corresponding y values for set Vx

var Z{Vx} >=0 , <=1; continuous variable (fraction 0..1)

var W{ (i,j) in PAIRS} binary;

maximise efficiency: somCrazyfunction(x) 

subject to one :

sum  {(i,j) in INTERVALS }  W[i,j] =1;  #only one pair is selected for which the value "y" is interpolated

subject to fractionSUM :

sum  {i in INTERVALS }  Z[i] =1; #sum of all fractional variable equals to one

# logical statement if-then is used

subject to single {(i,j) in INTERVALS}:

if  i <= x <= j   then i*Z[i]  +  j*Z[j] = x; # here the neighbouring fractional values of z are defined (only two for all pairs)

subject to Y_value:

y = sum{ i in Vx }  Z[i] *Y[i]; #define the value of ours non linear function at "x"

subject to Some_constraint:

y > some_expression;

######################################

does if-then statement works for KNITRO?

BR)))))) and thank you in advance for the answer!!!

Yauheni

пт, 14 февр. 2020 г. в 23:16, AMPL Google Group <am...@googlegroups.com>:

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/-Mjpr_EXJ64/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1081975217-3074539218-1581718578-1930947021%40helpscout.net.

[AMPL Google Group]

Knitro requires smooth (continuously differentiable) functions in the objective and constraints. Thus the use of if-then expressions in constraints does not work well with Knitro.

You mention however that "My function is purely continuous not step or discrete values." In that case, you should try to send your function directly to Knitro, rather than making a piecewise-linear approximation. When Knitro is used with AMPL, it can automatically compute the derivatives of smooth functions and use efficient derivative-based algorithms.

If you must write a piecewise-linear function in a model to be solved by Knitro, the breakpoints should be the boundaries of the pieces. For two breakpoints b[i] and b[i+1] and some function f, the slope between them can be computed by

(f(b[i+1]) - f(b[i])) / (b[i+1] - b[i])

Piecewise-linear approximation is only easy for functions of one variable. For nonlinear functions of more than one variable, it is necessary to consider linearizing over some kind of grid, which is much more complicated; if you can send a continuous function of multiple variables to Knitro instead, it will work much better.

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

On Sat, Feb 15, 2020 at 9:27 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Dear Robert,

sum {i in INTERVALS } Z =1; #sum of all fractional variable equals to

one

# logical statement if-then is used
subject to single {(i,j) in INTERVALS}:

if i <= x <= j then i*Z + j*Z[j] = x; # here the neighbouring

fractional values of z are defined (only two for all pairs)

subject to Y_value:

y = sum{ i in Vx } Z *Y; #define the value of ours non linear

function at "x"

subject to Some_constraint:
y > some_expression;

######################################
does if-then statement works for KNITRO?

BR)))))) and thank you in advance for the answer!!!

Yauheni




пт, 14 февр. 2020 г. в 23:16, AMPL Google Group <am...@googlegroups.com>:

On Fri, Feb 14, 2020 at 10:16 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Knitro does not handle special ordered set conditions. You can assign .sosno and .ref suffix values in AMPL (as described in the SOS FAQ), but Knitro will ignore those values.

Instead you should write the piecewise-linear approximation to f(x) in your model, using AMPL's << . . . ; . . . >> notation, and let AMPL convert this notation to a linear formulation that Knitro accepts.

--
Robert Fourer
am...@googlegroups.com

[Киселев Евгений]

Hi Robert!

Thank you for valuable comments!

Yes, I have a function of two variables but I do not have its analytical expression. Just chart or table (based on experiments, it is numeric model in hydrodynamics). For this reason I have to use piece wise approximation. Is there any examples of how to write such approximations with some additional continuous or binary variables. I can try to it myself but not sure of efficiency since I am sure there several ways to do it. As I see the one with if-then will not work fine in my case.

BR

John

пн, 17 февр. 2020 г. в 00:07, AMPL Google Group <am...@googlegroups.com>:

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/-Mjpr_EXJ64/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1081975217-3077462029-1581894453-898436524%40helpscout.net.

[AMPL Google Group]

I don't have any examples for modeling piecewise-linear bivariate functions, but a web search on this topic will turn up a variety of examples. You might start with Paul Rubin's Piecewise Linear Approximations in MIP Models which covers the basics.

There are some easy cases that do not require integer variables:

• Convex in a minimization objective, or concave in a maximization objective.
• Convex and on the left-hand side of a ≤ constraint (or equivalently, the right-hand side of a ≥ constraint),
• Concave and on the left-hand side of a ≥ constraint (or equivalently, the right-hand side of a ≤ constraint).

All other cases are hard and do require integer variables.

--
Robert Fourer
am...@googlegroups.com

{#HS:1081975217-67798#}

On Mon, Feb 17, 2020 at 12:10 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi Robert!

Thank you for valuable comments!
Yes, I have a function of two variables but I do not have its analytical expression. Just chart or table (based on experiments, it is numeric model in hydrodynamics). For this reason I have to use piece wise approximation. Is there any examples of how to write such approximations with some additional continuous or binary variables. I can try to it myself but not sure of efficiency since I am sure there several ways to do it. As I see the one with if-then will not work fine in my case.

BR

John

пн, 17 февр. 2020 г. в 00:07, AMPL Google Group <am...@googlegroups.com>:

On Sun, Feb 16, 2020 at 11:07 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Knitro requires smooth (continuously differentiable) functions in the objective and constraints. Thus the use of if-then expressions in constraints does not work well with Knitro.

You mention however that "My function is purely continuous not step or discrete values." In that case, you should try to send your function directly to Knitro, rather than making a piecewise-linear approximation. When Knitro is used with AMPL, it can automatically compute the derivatives of smooth functions and use efficient derivative-based algorithms.

If you must write a piecewise-linear function in a model to be solved by Knitro, the breakpoints should be the boundaries of the pieces. For two breakpoints b[i] and b[i+1] and some function f, the slope between them can be computed by

(f(b[i+1]) - f(b[i])) / (b[i+1] - b[i])

Piecewise-linear approximation is only easy for functions of one variable. For nonlinear functions of more than one variable, it is necessary to consider linearizing over some kind of grid, which is much more complicated; if you can send a continuous function of multiple variables to Knitro instead, it will work much better.

--
Robert Fourer
am...@googlegroups.com

[Киселев Евгений]

Thank you for advice Robert!

пн, 17 февр. 2020 г. в 23:43, AMPL Google Group <am...@googlegroups.com>:

--

You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/-Mjpr_EXJ64/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1081975217-3080387277-1581979413-1944130794%40helpscout.net.