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 <
[email protected]> 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
> [email protected]
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
