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

From: Kish Shen <kisshen_at_cisco.com>
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_cisco.com 
> <mailto:kisshen_at_cisco.com>> wrote:
> 
>     Kim Lai wrote:
> 
>         hi, your reply is a great help for me. thanks.
>         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 @
>         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.2.0 : Thu Feb 02 2012 - 02:31:58 CET