[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Problem with absolute value
From: |
Alessandro Saccoia |
Subject: |
[Help-glpk] Problem with absolute value |
Date: |
Mon, 14 Jan 2013 00:43:06 +0100 |
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] Problem with absolute value,
Alessandro Saccoia <=
- Re: [Help-glpk] Problem with absolute value, Jeffrey Kantor, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Alessandro Saccoia, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Reginald Beardsley, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Alessandro Saccoia, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Dmitry Nadezhin, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Reginald Beardsley, 2013/01/14
- Re: [Help-glpk] Problem with absolute value, Alessandro Saccoia, 2013/01/16
- Re: [Help-glpk] Problem with absolute value, Jeffrey Kantor, 2013/01/16
- Re: [Help-glpk] Problem with absolute value, Alessandro Saccoia, 2013/01/17