[Top][All Lists]
[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.