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 <[email protected]> wrote: > From: xypron <[email protected]> > Subject: Re: [Help-glpk] MIP code > To: [email protected] > 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 > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk > _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
