help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] MIP code


From: xypron
Subject: Re: [Help-glpk] MIP code
Date: Fri, 26 Jun 2009 10:28:47 -0700 (PDT)

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.





reply via email to

[Prev in Thread] Current Thread [Next in Thread]