Re: [Help-glpk] Problem with absolute value

[Alessandro Saccoia]

Hi Jeff,
that works wonders! Now I would just like to find a way to use the library 
instead of the executable, and insert all this information programmatically. In 
the glpk docs it seems that it's up to me to introduce all the variables and 
create the A matrix, but from another answer I got in pvt it looks like I can 
use this syntax and have the library do the necessary calculations.
If I can't avoid reading the model from file, I would at least like to be able 
to provide the data at runtime. Thanks for your time!
Alessandro
 
On Jan 14, 2013, at 1:04 PM, Jeffrey Kantor <address@hidden> wrote:

> Hi Alessandro,
> 
> I don't exactly the geometry, but here's a MathProg model for your problem. 
> If you want to try this out, cut and paste it into the web page at 
> http://www3.nd.edu/~jeff/mathprog/mathprog.html
> 
> Jeff 
> 
> 
> set N := 0..3;
> param q{N};
> param r{N};
> 
> param a := 0.95;
> param b := 1.05;
> 
> var z{N} >= 0;
> var s{N};
> 
> s.t. c1 {n in 0..3}: z[n] >= r[n] - s[n];
> s.t. c2 {n in 0..3}: z[n] >= s[n] - r[n];
> s.t. c3 {n in 0..2}: s[n+1] - s[n] >= a*(q[n+1]-q[n]);
> s.t. c4 {n in 0..2}: s[n+1] - s[n] <= b*(q[n+1]-q[n]);
> 
> minimize obj: sum{n in N} z[n];
> solve;
> 
> data;
> 
> param q :=
>     0    3
>     1    5
>     2    8
>     3   12 ;
>     
> param r :=
>     0    2
>     1    5
>     2    7
>     3   11 ;
>     
> end;
> 
> 
> On Sun, Jan 13, 2013 at 6:43 PM, Alessandro Saccoia <address@hidden> wrote:
> Hi list,
> I am new here, and not that experienced with mathematical methods such as 
> Linear Programming. I am trying to solve a problem (related to audio 
> alignment) for which, on stack exchange, I have been told to use LP. Please 
> check my original question:
> 
> http://math.stackexchange.com/questions/276492/stretching-of-a-set-of-numbers-to-align-to-a-reference
> 
> I have then studied it the whole afternoon, and it opened me a world, this is 
> so useful! But the absolute value in my problem is giving me a big headache 
> and I don't fully understand the suggestion I got.
> 
> If you have read the formulation of the problem in the link above, here 
> follows the modeling I am trying to plug into gplk: please try to follow my 
> solution. As this is the first time I try gplk I am going to use numbers, 
> then of course my program will use runtime data.
> 
> I want to find the alignment S from the following points:
> Q0 = 3
> Q1 = 5
> Q2 = 8
> Q3 = 12
> 
> with reference points
> 
> R0 = 2
> R1 = 5
> R2 = 7
> R3 = 11
> 
> where the segments Si-Si+1 can't move more than 50% of the original length
> 1 <= S1 - S0 <= 3               (original length Q0-Q1 = 2)
> 1.5 <= S2 - S1 <= 4.5  (original length Q1-Q2 = 3)
> 2 <= S3 - S2 <= 6               (original length Q2-Q3 = 4)
> 
> 
> The problem is a minimization problem with
> 
> min: |r0 - s0| + |r1 - s1| + |r2 - s2| + |r3 - s3|
> 
> for each one of the absolute values i we need introduce one variable Zi and 
> two contraints
> 
> Zi >= Ri - Si
> Zi >= -Ri + Si
> 
> (this is what I have understood by the answer on SE, and to get it I have 
> also read the page http://lpsolve.sourceforge.net/5.1/absolute.htm : 
> paragraph "minimization and sign is positive or maximization and sign is 
> negative")
> 
> To create the matrix A I use just my relationships over the segment lengths: 
> since these are inequalities, I introduce for each "i" two new variables 
> called SLi (stretch low) and SHi (stretch high), and so I can remove the >= 
> and <= by adding constraints.
> 
> for each i from 0 to 2:
> 
> Lower bound of the length of the segment
> Si+1 - Si >= Qi - alpha * (Qi+1 - Qi)
> Si+1 - Si = SLi (Stretch lower)
> Introduces constraint SLi >=  Qi - alpha * (Qi+1 - Qi)
> 
> Upper bound of the length of the segment
> Si+1 - Si <= Qi +  beta * (Qi+1 - Qi)
> Si+1 - Si <= SHi
> Introduces constraint SHi <= Qi +  beta * (Qi+1 - Qi)
> 
> Since all the Q values are known, the constraint on SLi and SHi sems very 
> simple.
> 
> Now my problem arrives: for what I got, each one of the new variables just 
> introduced creates a row,
> while each of the original unknowns is a column.
> 
> S0  S1  S2  S3    Variable
> -1  1   0   0   0       Sl0
> -1  1   0   0   0       Sh0
> 0   -1  1   0   0       Sl1
> 0   -1  1   0   0       Sh1
> 0   0   -1  1   0       Sl2
> 0   0   -1  1   0       Sh2
> 
> At this point I am stuck: I have an objective function made of the Zs 
> introduced before, and I know the constraints on them. But those Zs do not 
> show up in the A matrix, so… stuck, and I don't know if any of the above is 
> correct. Thanks in advance for your precious help.
> 
> Alessandro
> 
> 
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
>