# Re: [eclipse-clp-users] Q: Linear Programming with Disjunction constraints

From: Kish Shen <kisshen_at_...5...>
Date: Fri, 25 Apr 2008 11:15:42 +0100
```Kim Lai wrote:
> hi, I found a strange behavior about the big-M constraints in eplex.
> Two code snippet with the same logic result in different opt solution.
> For code 1:
> => [A1, A2, A3] = [0, 0.2, 0] , Cost = 2.5
> For code 2:
> => [A1, A2, A3] = [ 0, 0.1, 2.6], Cost = 3.9
...
>
> Is there any thing that I misunderstand or need to set up ?
>

I am not really an expert on linear programming, but I think the problem
you are seeing is due to scaling -- the value you have chosen for the
Big-M, 10000000, is too big.

In the branch-and-bound performed by a MIP solver, when the relaxed
solution value of an integer variable is `close to' an integer, it is
considered an integer. So in the case of your 0/1 B variables, a value
of 0 may actually be a very small value, e.g. 1x10e-6. However,
1x10e-6*1000000 is not 0, and in fact is bigger than the range of
numbers you are working with.

I think the general recommendation for `Big-M' is that it should be just
`big enought', to avoid these sort of numeric problems. In your problem,
even 10 is sufficient. I tried your problem with M = 1000, and the two
problem you sent gave the same answer (2.5).

Cheers,

Kish

Kim Lai wrote:
> hi, I found a strange behavior about the big-M constraints in eplex.
> Two code snippet with the same logic result in different opt solution.
> For code 1:
> => [A1, A2, A3] = [0, 0.2, 0] , Cost = 2.5
> For code 2:
> => [A1, A2, A3] = [ 0, 0.1, 2.6], Cost = 3.9
> --------- code 1-----------------
> :- lib(eplex).
>
>
> solve(Vars, Cost) :-
>
>     model(Vars, Obj),
>
>     eplex_solver_setup(min(Obj)),
>
>     eplex_solve(Cost).
>
>
> model(Vars, Obj) :-
>
>     Vars = [A1, A2, A3 ],
>
>     Vars \$:: 0..inf,
>
>     M = 10000000,
>
>     B = [B1, B2],
>     B :: 0..1,
>     integers(B),
>
>     Obj \$>= A1 + 1.2,
>
>     Obj \$>= A2 + 2.3,
>
>     Obj \$>= A3 + 1.3,
>
>
>     A2 - A1 \$=< -2.2 + (1-B1)*M,
>     A2 - A1 + B1*M \$>= 0.1,
>
>
>
>     A3 - A2 \$=< -0.2 + B2*M,
>
>     A3 - A2 + (1-B2)*M \$>= 2.5.
> ------------code 2----------------------------------------
> :- lib(eplex).
>
>
> solve(Vars, Cost) :-
>
>     model(Vars, Obj),
>
>     eplex_solver_setup(min(Obj)),
>
>     eplex_solve(Cost).
>
>
> model(Vars, Obj) :-
>
>     Vars = [A1, A2, A3 ],
>
>     Vars \$:: 0..inf,
>
>     M = 10000000,
>
>     B = [B1, B2],
>     B :: 0..1,
>     integers(B),
>
>     Obj \$>= A1 + 1.2,
>
>     Obj \$>= A2 + 2.3,
>
>     Obj \$>= A3 + 1.3,
>
>
>     A2 - A1 \$=< -2.2 + (1-B1)*M,
>     A2 - A1 + B1*M \$>= 0.1,
>
>
>
>     A3 - A2 \$=< -0.2 + (1-B2)*M,
>
>     A3 - A2 + B2*M \$>= 2.5.
> --------------------------------------------------------------------
>
> Is there any thing that I misunderstand or need to set up ?
>
> ps.
> thanks for point out my wrong usage of "porting". It should be "embedded
> with C++" ?
>
>
> On Fri, Apr 25, 2008 at 7:26 AM, Kish Shen <kisshen_at_...5...
> <mailto:kisshen_at_...5...>> wrote:
>
>     Kim Lai wrote:
>
>         I use lib(eplex) to reformulate my problem as follow. and it
>         really got a solution.
>         But after I port the following code to C++. I'm getting trouble
>         with ""How to extract the variables result"".
>         A result like this "A2{0.0 .. 1.7976931348623157e+308 _at_
>         1.1999999992549422}"
>         I'd like to extract A2=1.199 = 1.2
>         But it's not even a string...
>         in C++: I usually use "EC_word(Vars[i]).is_double(&d) == EC_succeed"
>         to get a double or long int .....And this didn't work..
>         ------------eclipse code------------------------
>
>
>     Your specific problem is that when a problem is solved by eplex, the
>     problem variables are not instantiated. This allows you to modify
>     the problem and resolve it. eplex_var_get/3 allows you to extract
>     the solution value from the variable, e.g. for the variable A2 above,
>
>     ....
>     eplex_var_get(A2, solution, A2Sol),
>
>
>     will instantiate A2Sol to the solution value of A2
>
>     So you should exract the solution values, and pass these to C++.
>
>     A more general point: I am not quite sure what you mean exactly by
>     `porting to C++' - you seem to want to pass solution values from a
>     ECLiPSe program to C++. This is probably the best way to use ECLiPSe
>     as a constraint solver when you are using ECLiPSe with other
>     languages -- but I would not call this `porting', but interfacing.
>
>     Cheers,
>
>     Kish
>
>
>
>
> --
> ....Best Regards
> by Kim Lai, 賴廣甫
> Welcome to visit http://kimklai.blogspot.com
```
Received on Fri Apr 25 2008 - 03:15:57 CEST

This archive was generated by hypermail 2.3.0 : Sun Aug 25 2019 - 03:15:37 CEST