Re: [Help-glpk] Problem with absolute value

[Jeffrey Kantor]

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