[Help-glpk] [Fwd: Re: [Fwd: Find nearest point]]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Paul Chavent <address@hidden>
To: glpk xypron <address@hidden>
Cc: Andrew Makhorin <address@hidden>, address@hidden
Subject: Re: [Help-glpk] [Fwd: Find nearest point]
Date: Wed, 15 Jun 2011 22:17:03 +0200

Hello Xypron.

Thank you for your reply.

It works with a smallest value !

In the wikibook there is a paragraph on "scaling". Is it the same issue that 
the choice of the big M ?

Is there any way to initialise the big M : for example (pseudo code)
param M := max({i in 1..n}abs(x[i]))

The wikibook is very usefull. Thank you for adding the big M tip.

Regards.

Paul.

On 06/15/2011 09:30 PM, glpk xypron wrote:
>
>
> Hello Paul,
>
> GLPK only calculates with limited precision.
>
> Unfortunately you have chosen big_number unreasonably high. If
> you change it to 10, you get the expected result.
>
> In a big M approach you should always use the smallest possible
> number for M.
>
> The problem is recurring cf.
> http://lists.gnu.org/archive/html/help-glpk/2011-04/msg00021.html
>
> I added a paragraph in the Wikibook
> http://en.wikibooks.org/wiki/GLPK/Modeling_tips#Big_M
>
> Best regards
>
> Xypron
>
>> -------- Forwarded Message --------
>> Subject: Find nearest point
>> Date: Wed, 15 Jun 2011 10:10:25 +0200 (CEST)
>>
>> Hi.
>>
>> I'm currently working on a project that aims to compute the consign we
>> should give to an uav in order to reach a point.
>>
>> The first step has been to model the problem without obstacles. It seems
>> to work (we find the straight line :) ).
>>
>> Now we need to add obstacles. And in my new model, glpk seems to ignore
>> some constraints.
>>
>> I tried to make a minimalist example to reproduce the "problem".
>>
>> When i run this example, b[0] and b[1] both equals 0 and i wonder how c6
>> is satisfied ?
>>
>> I suppose that i have made a mistake. Could you explain my why ?
>>
>> Thank you.
>>
>> Paul.
>>
>>
>>
>>
>> # trivial.dat
>> data;
>> param big_number := 100000;
>> param xref := 5;
>> param xobs := 5;
>> param cobs := 1;
>> end;
>>
>> #trivial .mod
>> param big_number;
>> # reference coordinate
>> param xref;
>> # obstacle coordinate
>> param xobs;
>> # obstacle side
>> param cobs;
>>
>> var x;
>> var xerr;
>> var b{i in 1..2}, binary;
>>
>> minimize f : xerr;
>>
>> # xerr = abs(x - xref)
>> s.t. c1 :   x - xref<= xerr;
>> s.t. c2 :  -x + xref<= xerr;
>>
>> # b[1] = 0 if x is to the left of xobs
>> s.t. c3 : x>= xobs - cobs - big_number * (1 - b[1]);
>> s.t. c4 : x<= xobs - cobs + big_number *      b[1];
>>
>> # b[2] = 0 if x is to the right of xobs
>> s.t. c5 : x<= xobs + cobs + big_number * (1 - b[2]);
>> s.t. c6 : x>= xobs + cobs - big_number *      b[2];
>>
>> # x must be at least to the right or to the left
>> s.t. c7 : sum{j in 1..2} b[j]<= 1;
>>
>> solve;
>>
>> display xobs;
>> display cobs;
>> display x;
>> display b;
>>
>> end;
>
>