RE: [AMPL 6176] Piecewise Linearization using SOS2 variables - AMPL - CPLEX
Robert Fourer
For modeling piecewise-linear functions of single variables, you should use the piecewise-linear notation described in chapter 17 of the AMPL book (www.ampl.com/BOOK/download.html), and then CPLEX will automatically be set up to use SOS2 branching if appropriate.
If you have some other kind of piecewise-linearity then probably SOS2 branching is not applicable, though it would be necessary to see the details to be sure.
Bob Fourer
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of Vinicius
Sent: Thursday, September 27, 2012 8:32 AM
To: am...@googlegroups.com
Subject: [AMPL 6176] Piecewise Linearization using SOS2 variables - AMPL - CPLEX
Please, could you give me an example of modeling Piecewise Linearization using SOS2 variables?
I have been searching it for a long time but I have not found an easy example of modelling it using CPLEX-AMPL.
Regards, Vinícius.
Paul
Robert Fourer
The GAMS statement "SOS2 Variables lambda(i,j,k),delta(i,j), ..." looks very easy because someone has already gone to the trouble of introducing an auxiliary variable for each piecewise-linear breakpoint and 3 auxiliary constraints for every piecewise-linear function. Ideally you would figure out the piecewise-linear functions that were present in the original model formulation, and would write those functions directly using AMPL's breakpoint-slope notation for piecewise-linear functions -- enabling all those extra variables and constraints to be dropped from your model.
If you are strongly motivated to convert the GAMS model directly to AMPL, without figuring out the forms of the piecewise-linear functions, then you can set the .sosno and .ref suffixes for all of the variables lambda, delta, ... First you need to know that when GAMS defines SOS2 variables lambda(i,j,k), it is implicitly defining a different SOS2 set for each separate combination of i and j; for fixed i and j, the SOS2 set consists of lambda(i,j,k) for all k. To specify SOS2 sets in AMPL, you're going to have to write something like
suffix sosno integer IN;
let {i in 1..I, j in 1..J, k in 1..K} lambda[i,j,k].sosno = -((i-1)*I + j);
`
so that all variables in any particular SOS2 set have the same negative .sosno value. (If it were positive then AMPL would interpret it as SOS1.) You should also set lambda[i,j,k].ref to the value of the piecewise-linear function breakpoint that is associated with the auxiliary variable lambda[i,j,k]. See for example http://yetanothermathprogrammingconsultant.blogspot.com/2009/06/gams-piecewise-linear-functions-with.html, where the auxiliary variable lambda_k would have the reference value xbar_k. (If the breakpoints tend to be equally spaced then reference values 1, 2, ... as suggested in that post should work about as well.)
If you try this and still get an error message then please post the complete text of the message and the command that was being executed when the error occurred.
On Behalf Of Vinicius
Sent: Friday, September 28, 2012 8:50 AM
To: am...@googlegroups.com
Cc: 4...@ampl.com
Subject: Re: [AMPL 6180] Piecewise Linearization using SOS2 variables - AMPL - CPLEX
Fourer, Thanks for your fast answer!
I am translating from GAMS to AMPL a code that I made which deals with a non smooth surface by piecewise linearization.Then, the problem is modeled as MIP and solved by CPLEX.
The piece of GAMS code that refers to piecewise linearization is:
SOS2 Variables lambda(i,j,k),delta(i,j),gama(i,k),beta(i,j,k),theta(i,l);
It is very easy. I am having some trouble to do it in AMPL. Today I saw in internet the piece of AMPL code:
suffix sosno integer IN;
let x.sosno:=-1;
let y.sosno:=-1;
in order to make variables x and y SOS2.
So, I have been trying to do it but it is not working at all. I aways receive a syntax error as a result.
Is there something wrong?
Thanks in advance, best regards, Vinícius.
Robert Fourer
This indeed appears to be a piecewise-linearization of functions over a surface. The way I think of it, the variables lambda(i,j,k), delta(i,j), and gama(i,k) are the "extra" variables that are needed to formulate the piecewise linearization in terms of linear expressions. The SOS2 condition does make it possible to avoid even more extra variables.
Because this is a two-dimensional piecewise-linearization, AMPL's piecewise-linear terminology is not relevant here, and it's indeed necessary to specify the SOS2 structure explicitly in AMPL. However as far as I can tell, the aim of the SOS2 restrictions on delta and gama in the model is to restrict the nonzero lambda(i,j,k) values to a 2 x 2 square of (j,k) indices for each i. The SOS2 restrictions on lambda seem to me to be redundant; maybe they are a mistake, or maybe they help with solution time (as redundancies sometimes do), or maybe someone more familiar with the problem can explain them.
Anyhow to specify the SOS2 conditions on delta and gama, the statements would be:
suffix sosno integer IN;
suffix ref integer IN;
let {i in 1..I, j in 1..J} delta[i,j].sosno = -i;
let {i in 1..I, j in 1..J} delta[i,j].ref = j;
let {i in 1..I, k in 1..K} gama[i,k].sosno = -I-i;
let {i in 1..I, k in 1..K} gama[i,k].ref = k;
That is, for the variables in each SOS2 set, a unique (negative) .sosno is assigned, and a .ref is assigned according to the position in the set.
Bob Fourer
P.S.: If the model is in English then "gama" would seem to be a misspelling of "gamma" but I have elected not to change the terminology as given.
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of Vinicius
Sent: Monday, October 01, 2012 7:51 AM
To: am...@googlegroups.com
Cc: 4...@ampl.com
Subject: Re: [AMPL 6185] Piecewise Linearization using SOS2 variables - AMPL - CPLEX
Fourer, thanks for your answer!
I want to apply piecewise linearization into a surface. At GAMS I have a matrix of breakpoints like this:
Table pwh(k,i)
1 2 3 4 5 6 7 8 9 10 11
1 10 10 10 10 10 10 10 10 10 10 10
2 12 12 12 12 12 12 12 12 12 12 12 . . .
Table qg(j,i)
1 2 3 4 5 6 7 8 9 10 11
1 0 0 0 0 0 0 0 0 0 0 0
2 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000
3 40000 40000 40000 40000 40000 40000 40000 40000 40000 40000 40000 . . .
Table qo(i,j,k)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1. 1 3873.2 3565.5 3214.7 2759.4 2166.7 0 0 0 0 0 0 0 0 0 0 0
1. 2 4050.4 3804.3 3529.7 3224.2 2874.2 2489.4 2051 1247.4 0 0 0 0 0 0 0 0
1. 3 4190.2 3975.2 3743.2 3495.2 3223 2943.9 2623.7 2315.9 1974.3 1595.7 1184.6 758.2 522.2 0 0 0
1. 4 4299.9 4108.9 3903.4 3689.7 3460.1 3213.3 2965.3 2703.8 2438.8 2175.4 1898.5 1612.2 1321.8 1037.1 827.1 642.4
. . .
11. 15 2968.9 2957.2 2944.1 2929.6 2913.7 2896.6 2878.3 2858.7 2838 2816.1 2793.2 2769.2 2744.2 2718 2690.9 2662.6
11. 16 2944.1 2933 2920.6 2906.8 2891.7 2875.4 2857.9 2839.1 2819.3 2798.4 2776.4 2753.4 2729.5 2704.4 2678.4 2651.4;
Where lambda (i,j,k) refers to qo(i,j,k) linearization, delta(i,j) refers to qg(j,i) linearization and gama(i,k) refers to pw(i,k) linearization. I could to it in GAMS by SOS2 variables considering lambda, delta and gama just like the link you posted. This model is one of the methods presented (the simplest one) in "Misener R., Gounaris C. E., Floudas C. A. (2009), Global Optimization of Gas Lifting Operations: A Comparative Study of Piecewise Linear Formulations. Industrial & Engineering Chemistry Research 48: 6098 - 6104. The variables lambda, delta, gama are convex combinations and there is no need for any extra variables to select a linear segment. I see that is hard to set .ref values for each breakpoint due to the large set of data (table qo(i,j,k)).
Here goes a piece of the GAMS model:
Variables qgl(i),qoleo(i),pw(i);
SOS2 Variables lambda(i,j,k),delta(i,j),gama(i,k);
qoleo(i) =e= sum(j,sum(k,lambda(i,j,k)*qo(i,j,k)))
qgl(i) =e= sum(j,sum(k,lambda(i,j,k)*qg(j,i)));
pw(i) =e= sum(k,sum(j,lambda(i,j,k)*pwh(k,i)));
eq1(i).. sum(j,sum(k,lambda(i,j,k))) - 1 =e= 0;
eq3(i,j).. delta(i,j) =e= sum(k,lambda(i,j,k));
eq5(i,k).. gama(i,k) =e= sum(j,lambda(i,j,k))
Sorry for the trouble but I am do not have the best skills in math programming. I could not figure out your tip exactly.
Thanks for all the help. Best regards, Vinícius.