[Help-glpk] MIP problem

[husalihas]

Hello,

Here is another sample MIP code named “1LMF_MathProg” written in MathProg 
language to solve a certain MIP problem (thanks to <xypron> who proposed 
several professional modifications to a similar code in a previous E-mail). 
But, unfortunately GLPK takes a lot of time to solve this problem. Actually, I 
do not know exactly how long it will take from GLPK to solve this problem, 
because I stopped the solution process after  six minutes, because in my 
application the problem should be solved in no more than 60 sec. 
If we reduced this code by disabling the constraint “H”,for testing purpose, 
then GLPK will take  180 sec. to solve it (on my Laptop).

The same code was converted to “AMPL” language and given a name “1LMF_AMPL” and 
a commercial solver “AMPL CPLEX 11.2” was used to solve it. It took only 15 
sec. from the commercial solver to solve this problem and produce the results 
shown in the attached file “1LMF_CPLEX_results”. 
If we reduce this code by disabling the constraint “H”, then “AMPL CPLEX 11.2” 
will take less than 1 sec. to solve it and produce the same results that were 
produced by GLPK in 180 sec.
So, what does that mean? Is GLPK not capable of solving large MIP problems? or 
is there a mistake in the MathProg Code above?
Are there some GLPK MIP solution options that we can change to reduce the time 
required to solve this problem? And how to use them?
I need to use an open source code to solve this problem. Are there any 
suggestions ?

Thanks,
-------------------------------------------------------------------------
#1LMF_CPLEX_results

ampl: model 1LMF.mod;
CPLEX 1.2.0: optimal integer solution; objective 351600
46509 MIP simplex iterations
42727 branch-and-bound nodes
31 Gomory cuts
50 implied-bound cuts
28 mixed-integer rounding cuts

cost_1LMF = 396360

--------------------------------------------------------------------------

#1LMF_MathProg.mod
#reset;
# 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 = 'L' or ( d = 'V' 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;
var TH{i in S}, >= if i = 1 then 60 else 50, <= if i = 1 then 60 else 70;

# 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 ;

############# V #######################

        Const_V2 {i in D: i = 'V'}: sum {j in S} W['V',j] = 6 ;

        Const_V3 {i in D, j in S: i = 'V' and j >= 7 and j <= 19} : sum {k in 
j-1..j+1} W ['V',k] <= 2 ;

############# 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;

############# H #################

    Const_H5 {j in S, i in D: i = 'H' and j!=1 }: - TH[j] + TH[j-1] - AC[j] + 5 
* W['H',j] - 1  = 0;


solve;

printf "\n";
printf  "cost_1LMF = %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";
}

printf "\n";


# Data  

data;

# uncomment the appropriate line(s)       
set D := 
 A  
 V  
 F 
 H
 L 
;  

# uncomment the appropriate line(s)   
param PO := 
  A   2000  
  V   1500  
  F   250
  H   1500  
  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;

-----------------------------------------------------------------------

#1LMF_AMPL.mod
reset;
# 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 = 'L' or ( d = 'V' 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;
var TH{i in S}, >= if i = 1 then 60 else 50, <= if i = 1 then 60 else 70;

# 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 ;

############# V #######################

        Const_V2 {i in D: i = 'V'}: sum {j in S} W['V',j] = 6 ;

        Const_V3 {i in D, j in S: i = 'V' and j >= 7 and j <= 19} : sum {k in 
j-1..j+1} W ['V',k] <= 2 ;

############# 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;

############# H #################

    Const_H5 {j in S, i in D: i = 'H' and j!=1 }: - TH[j] + TH[j-1] - AC[j] + 5 
* W['H',j] - 1  = 0;


# Data

data;

# uncomment the appropriate line(s)       
set D := 
 A  
 V  
 F 
 H
 L 
;  

# uncomment the appropriate line(s)   
param PO := 
  A   2000  
  V   1500  
  F   250
  H   1500  
  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  
;


solve;

printf "\n";
printf  "cost_1LMF = %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 "\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" ;
}
printf "\n";

--------------------------------------------------------------------------