Re: [Help-glpk] MIP code

[husalihas]

Thankyou again,

using --cuts --tmlim 30, was really effective , now I have the same cost 
obtained using the commercial CPLEX11.2 (obtained within 15 sec.).
30 sec. is fast enough time for my research.

Regard,

Hussin

--- On Fri, 6/26/09, xypron <address@hidden> wrote:

> From: xypron <address@hidden>
> Subject: Re: [Help-glpk] MIP code
> To: address@hidden
> Date: Friday, June 26, 2009, 9:28 PM
> 
> Hello Hussin,
> 
> the following approaches allow cutting the solution time
> for your problem.
> 
> == Limit Solution Time ==
> 
> The optimum solution is obtained after less then 10 % of
> the runtime.
> The rest of the time is spent on proving optimality.
> 
> Hence it is possible to limit execution time. Solving with
> generated cuts is
> a bit faster. You can use the following command:
> 
> glpsol -m hussein.mod --cuts --tmlim 30
> 
> == Reduce Number of Constraints and Variables ==
> 
> The processing time and memory consumption for MathProg
> interpretation can
> be reduced by joining constraints with equal left hand
> side:
> 
> s.t. Const_A3_A4 {j in S: j >= 1 and j <= 24 } : 13
> <= TA[j] <= 23;
> 
> As the constraints Const_A3 and Const_A4 are valid for all
> j in S they
> should be completely removed and replaced by an adequate
> definition of the
> variable which also replaces Const_A1:
> 
> var TA{S}, >= if i = 1 then 20 else 13, <= if i = 1
> then 20 else 23;
> 
> Const_F1, Const_F3 and Const_F4 can be replaced by an
> adequate definition of
> TF:
> 
> var TF{s}, >= if i = 1 then -18 else -22, <= -18.
> 
> Const_L1, Const_A2, Const_F2 have no members and can be
> completely
> eliminated.
> 
> Const_A5, Const_F5, Const_S1 and Const_S3 should not be
> generated for each
> {i in D} as they do not depend on i.
> 
> IL will always be ceil(RI-OI) and does not influence other
> variables. It can
> be removed completely. RI and OI can be removed except for
> output (Z = ...).
> 
> Const_S1 can be replaced by an adequate definition of
> variable W:
> var W {d in D, j in S} binary, <= if d = 'S' and ( j
> < 7 or j > 19 ) then 0
> else 1;
> 
> Realizing that always W['L',*] = 0 gets us to:
> var W {d in D, j in S} binary, <= if d = 'W' or ( d =
> 'S' and ( j < 7 or j >
> 19 ) ) then 0 else 1;
> 
> These modeling changes reduce solution time by 68 %.
> 
> == Subdivide Problem ==
> 
> Great improvement is possible by separating the model into
> 4 independent
> models for each value {i in D}.
> 
> Taking all these changes cuts solution time by more then 99
> %.
> 
> See final model below.
> 
> Best regards
> 
> Xypron
> 
> 
> =========================================================================
> 
> # Sets
> set D;
> set S;
> 
> # Parameters
> 
> param OI {S};
> param RI {S};
> param PR {S};           
>   
> param PO {D};           
>         
> param AC {S};
> param OT {S};
> 
> # Variables
> 
> var W {d in D, j in S} binary, <= if d = 'W' or ( d =
> 'S' and ( j < 7 or j >
> 19 ) ) then 0 else 1;
> var TA{i in S}, >= if i = 1 then 20 else 13, <= if i
> = 1 then 20 else 23;
> var TF{i in S}, >= if i = 1 then -18 else -22, <=
> -18;
> 
> # Objective Function
> 
> minimize Z: sum {j in S} ( sum{i in D : i != 'L'}
> W[i,j]*PO[i]*PR[j]  );
> 
> subject to
>                
>                
>        
> ############# A ########################
> 
>         Const_A5 {i in D, j in S: i =
> 'A' and  j!=1 }: (- 1.1) * TA[j] +
> TA[j-1] + 0.1 * AC[j] - 4 * W['A',j] + 0.1 * OT[j] + 2 = 0
> ;
> 
> ############# F ######################
> 
>         Const_F5 {i in D, j in S: i =
> 'F' and j!=1 }: - TF[j] + TF[j-1] +
> 0.1 * AC[j] - 2 * W['F',j] + 1 = 0;
> 
> ############# S #######################
> 
>         Const_S2 {i in D: i = 'S'}: sum
> {j in S} W['S',j] = 6 ;
> 
>         Const_S3 {i in D, j in S: i =
> 'S' and j >= 7 and j <= 19} : sum {k
> in j-1..j+1} W ['S',k] <= 2 ;
>  
> 
> solve;
> 
> 
> printf  "Z = %8d",sum {j in S}
>                 (
> sum{i in D : i = 'L'} ceil(RI[j]-OI[j])*PO['L']*PR[j] +
> sum{i in D : i != 'L'} W[i,j]*PO[i]*PR[j] ) ;
> 
> printf "\n";
> printf " W(i,j) \n";
> 
> for {i in D}
> {  printf("%s: ",i);
>    for {j in S} printf " %s",if W[i,j] then
> "1" else ".";
>    printf("\n");
> }
> 
> 
> # Data  
> 
> data;
> 
> # uncomment the appropriate line(s)   
>    
> set D := 
>  A  
> # S  
> # F 
> # L 
>  ;  
> 
> # uncomment the appropriate line(s)   
> param PO := 
>   A   2000  
> #  S   1500  
> #  F   250  
> #  L   150  
>   ;             
>                 
> 
> set S := 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
> 21 22 23 24;
> 
> param PR := 1 4 2 4 3 4 4 4 5 4 6 4 7 7.2 8 7.2 9 7.2 10
> 7.2 11 8.8 12 8.8
> 13 8.8 14 8.8 15 8.8 16 8.8 17 8.8 18 7.2 19 7.2 20 7.2 21
> 7.2 22 4 23 4 24
> 4 ;
> 
> param AC := 1 1.25 2 1.15 3 1.05 4 1.1 5 1.2 6 1.4 7 1.7 8
> 1.8 9 1.9 10 2 11
> 2 12 2.1  13 2.2 14 2.3 15 2.4 16 2.7 17 2.8 18 3 19 3
> 20 3 21 3 22 4 23 2.4
> 24 1.7;
> 
> param OI := 1 0 2 0 3 0 4 0 5 0 6 0.1 7 0.1 8 0.1 9 0.5 10
> 0.5 11 0.7 12 0.7
> 13 0.7 14 0.7 15 0.7 16 0.5 17 0.1 18 0 19 0 20 0 21 0 22 0
> 23 0 24 0;
> 
> param RI := 1 0.1 2 0.1 3 0.1 4 0.1 5 0.1 6 1 7 1 8 1 9 2
> 10 2 11 2 12 2 13
> 2 14 2 15 2 16 2 17 3 18 3 19 3 20 3 21 2 22 2 23 2 24 1;
> 
> param OT := 1 15 2 14 3 14 4 13 5 13 6 13 7 14 8 14 9 15 10
> 17 11 17 12 20
> 13 24 14 25 15 27 16 26 17 25 18 24 19 24 20 20 21 18 22 16
> 23 16 24 15 ;
> 
> end;
> 
> hussin hassen wrote:
> > 
> > Hello everybody,
> > 
> > GLPK can solve the attached code in 360 sec. on my
> Laptop, which is very
> > long time.
> > Is there any suggestion to expedite the solution
> process?
> > Is there anything wrong with this code than does not
> match with MathProg?
> > Shall I modify the MIP options to make the process
> faster? and how?
> > 
> > I want the solution process to be finish within 10-30
> sec.
> > 
> > Anyone can help?
> > 
> > Thanks
> > 
> > set D;
> > set S;
> > 
> > 
> > # Parameters 
> > 
> > param PR {S};           
>           
> > param PO {D};           
>             
>         
> > param AC {S};        
> > param OI {S};       
>            
>     
> > param RI {S};       
>     
> > param OT {S};
> > 
> > 
> > # Variables 
> > 
> > var W {D,S} binary; 
> > var IL {S} integer >=1 <=3 ;  
> > var TF {S} ;        
> > var TA {S} ;       
>     
> > 
> > 
> > # Objective Function
> > 
> > minimize Z: sum {j in S} ( IL[j]*PO['L']*PR[j] + sum{i
> in D : i != 'L'}
> > W[i,j]*PO[i]*PR[j]  );
> > 
> > 
> > subject to
> >  
> > ############# L ###################
> > 
> >     Const_L1 {i in D, j in S : j < 1
> or j > 24}:  W['L',j] = 0 ;
> > 
> >     Const_L2 { j in S : j >= 1 and j
> <= 24 }:  OI[j] + IL[j] >= RI[j] ;
> >        
>             
> > ############# A ########################
> > 
> >         Const_A1 {j in S
> : j = 1 } : TA[j]   = 20 ;
> > 
> >     Const_A2 {i in D, j in S: j < 1
> or j > 24}:    W['A',j] = 0;
> > 
> >     Const_A3 {j in S: j >= 1 and j
> <= 24 } :     TA[j]  <=
> 23;
> > 
> >     Const_A4 {j in S: j >= 1 and j
> <= 24 } :     TA[j]  >=
> 13;
> > 
> >     Const_A5 {i in D, j in S : j!=1 }:
> (- 1.1) * TA[j] + TA[j-1] + 0.1 *
> > AC[j] - 4 * W['A',j] + 0.1 * OT[j] + 2 = 0 ;
> > 
> > ############# F ######################
> > 
> >         Const_F1 {j in S
> : j= 1} : TF[j] = (-18 ) ;
> > 
> >     Const_F2 {i in D, j in S : i = 'F'
> and (j < 1 or j > 24)}:  W['F',j] = 0;
> > 
> >     Const_F3 {i in D, j in S : j > 1
> and j <= 24}:    TF[j]  <= (-18);
> > 
> >     Const_F4 {i in D, j in S : j > 1
> and j <= 24}:     TF[j]  >=
> (-22);
> > 
> >     Const_F5 {i in D, j in S: j!=1 }: -
> TF[j] + TF[j-1] + 0.1 * AC[j] - 2 *
> > W['F',j] + 1 = 0;
> > 
> > ############# S #######################
> > 
> >     Const_S1 {i in D, j in S : j < 7
> or j > 19}: W['S',j] = 0;
> > 
> >     Const_S2 : sum {j in S} W['S',j] =
> 6 ;
> > 
> >     Const_S3 {i in D, j in S: j >= 7
> and j <= 19} : sum {k in j-1..j+1} W
> > ['S',k] <= 2 ;
> >          
> > 
> > solve;
> > 
> > 
> > printf  "Z = %8d",sum {j in S} 
> >         (
> IL[j]*PO['L']*PR[j] + sum{i in D : i != 'L'}
> W[i,j]*PO[i]*PR[j] ) ;
> > 
> > printf "\n";
> > printf " W(i,j) \n";
> > 
> > for {i in D}
> > {  for {j in S} printf " %s",if W[i,j] then "1"
> else ".";
> >    printf("\n");
> > }
> > 
> > 
> > # Data  
> > 
> > data;
> >     
> > set D := A  S  F  L
> ;   
> >    
> > param PO := A   2000 
> S   1500  F   250 
> L   150  ;       
>                
>           
>         
>      
> > 
> > set S := 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
> 19 20 21 22 23 24;
> > 
> > param PR := 1 4 2 4 3 4 4 4 5 4 6 4 7 7.2 8 7.2 9 7.2
> 10 7.2 11 8.8 12 8.8
> > 13 8.8 14 8.8 15 8.8 16 8.8 17 8.8 18 7.2 19 7.2 20
> 7.2 21 7.2 22 4 23 4
> > 24 4 ;
> > 
> > param AC := 1 1.25 2 1.15 3 1.05 4 1.1 5 1.2 6 1.4 7
> 1.7 8 1.8 9 1.9 10 2
> > 11 2 12 2.1  13 2.2 14 2.3 15 2.4 16 2.7 17 2.8
> 18 3 19 3 20 3 21 3 22 4
> > 23 2.4 24 1.7;
> > 
> > param OI := 1 0 2 0 3 0    4 0 5
> 0    6 0.1 7 0.1 8 0.1 9
> 0.5    10 0.5 11 0.7 12
> > 0.7 13 0.7 14 0.7 15 0.7 16 0.5 17
> 0.1    18 0 19 0 20 0 21 0 22 0 23 0 24 0;
> > 
> > param RI := 1 0.1 2 0.1    3 0.1 4 0.1
> 5 0.1 6 1 7 1 8 1 9 2 10 2 11 2 12 2
> > 13 2 14 2 15 2    16 2 17 3 18 3 19 3
> 20 3 21 2 22 2 23 2    24 1;
> > 
> > param OT := 1 15 2 14 3 14 4 13    5 13
> 6 13 7 14 8 14 9 15 10 17 11 17 12 20
> > 13 24 14 25 15 27 16 26 17 25 18 24 19 24 20 20 21 18
> 22 16 23 16 24 15 ;
> > 
> > 
> > end;
> > 
> 
> -- 
> View this message in context: 
> http://www.nabble.com/MIP-code-tp24207624p24224306.html
> Sent from the Gnu - GLPK - Help mailing list archive at
> Nabble.com.
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>