bug-glpk
[Top][All Lists]
Advanced

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

[Bug-glpk] big M constraint problem


From: Ercasta
Subject: [Bug-glpk] big M constraint problem
Date: Sun, 31 Oct 2004 00:03:11 +0200

I have defined a model and a data file as follows:

-------------------------MODEL FILE--------------------
param stazioni;
param p1{i in 1..stazioni};
param p2{i in 1..stazioni};
param costoatt{i in 1..stazioni};
param costopertonn{i in 1..stazioni};

param min1;
param min2;
param M;

var attivazione{1..stazioni} binary;
var quantita{1..stazioni} >=0;
minimize costototale: sum{i in 1..stazioni} (costoatt[i]*attivazione[i] + 
costopertonn[i]*quantita[i]);

#Minima depurazione richiesta
subject to minimadepurazione1: sum {i in 1..stazioni} quantita[i]*p1[i] >= min1;
subject to minimadepurazione2: sum {i in 1..stazioni} quantita[i]*p2[i] >= min2;

#Vincolo paesaggistico
subject to paesaggio: attivazione[1]+attivazione[2]<=1;

#Vincoli di M grande
subject to mgrande{i in 1..stazioni}: quantita[i]<=M*attivazione[i];

solve;
display {i in 1..stazioni} : attivazione[i],quantita[i];
display costototale;

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

-----------------------DATA FILE-------------------------
param stazioni := 4;
param min1 := 80;
param min2 := 50;
param M := 100000;

param p1:= 
1       0.4
2       0.25
3       0.30
4       0.15;

param p2:= 
1       0.35
2       0.25
3       0.20
4       0.22;

param costoatt:= 
1       100000
2       70000
3       80000
4       40000;

param costopertonn:= 
1       20
2       30
3       30
4       35;

-----------------------------------------------------
When i run glpsol, the output is:

glpsol -m stazionidepurazione.mod -d stazionidepurazione.dat
Reading model section from stazionidepurazione.mod...
stazionidepurazione.mod:27: warning: final NL missing before end of file
stazionidepurazione.mod:27: warning: unexpected end of file; missing end 
statement inserted
27 lines were read
Reading data section from stazionidepurazione.dat...
stazionidepurazione.dat:29: warning: unexpected end of file; missing end 
statement inserted
29 lines were read
Generating costototale...
Generating minimadepurazione1...
Generating minimadepurazione2...
Generating paesaggio...
Generating mgrande...
Model has been successfully generated
lpx_simplex: original LP has 8 rows, 8 columns, 26 non-zeros
lpx_simplex: presolved LP has 7 rows, 8 columns, 18 non-zeros
lpx_adv_basis: size of triangular part = 7
      0:   objval =   0.000000000e+00   infeas =   1.000000000e-00 (0)
      3:   objval =   6.000000000e+03   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     3:   ip_obj =     not found yet >=              -inf (1; 0)
+     7:   ip_obj =   8.800000000e+04 >=   6.000000000e+03 (3; 0)
+    11:   ip_obj =   5.866666667e+04 >=   1.184000000e+04 (3; 2)
+    12:   ip_obj =   5.866666667e+04 >=     tree is empty (0; 9)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2M (166651 bytes)
Display statement at line 26
attivazione[1] = 0
quantita[1] = 0
attivazione[2] = 0
quantita[2] = 0
attivazione[3] = 0
quantita[3] = 0
attivazione[4] = 1
quantita[4] = 533.333333333333
Display statement at line 27
costototale:
   20 quantita[1]
   100000 attivazione[1]
   30 quantita[2]
   70000 attivazione[2]
   30 quantita[3]
   80000 attivazione[3]
   35 quantita[4]
   40000 attivazione[4]
Model has been successfully processed

Compilation finished at Sat Oct 30 23:44:45
-------------------------------------------------------------------

I don't know if this solution is correct. What i know for sure is that if i 
change the value of parameter M to 

 param M := 100000000000;

I get an obviously wrong solution:

glpsol -m stazionidepurazione.mod -d stazionidepurazione.dat 
Reading model section from stazionidepurazione.mod...
stazionidepurazione.mod:27: warning: final NL missing before end of file
stazionidepurazione.mod:27: warning: unexpected end of file; missing end 
statement inserted
27 lines were read
Reading data section from stazionidepurazione.dat...
stazionidepurazione.dat:29: warning: unexpected end of file; missing end 
statement inserted
29 lines were read
Generating costototale...
Generating minimadepurazione1...
Generating minimadepurazione2...
Generating paesaggio...
Generating mgrande...
Model has been successfully generated
lpx_simplex: original LP has 8 rows, 8 columns, 26 non-zeros
lpx_simplex: presolved LP has 7 rows, 8 columns, 18 non-zeros
lpx_adv_basis: size of triangular part = 7
      0:   objval =   0.000000000e+00   infeas =   1.000000000e-00 (0)
      2:   objval =   4.000000000e+03   infeas =   5.833333333e-16 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     2:   ip_obj =     not found yet >=              -inf (1; 0)
+     3:   ip_obj =   4.000000000e+03 >=   4.000000000e+03 (1; 0)
+     3:   ip_obj =   4.000000000e+03 >=     tree is empty (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2M (166651 bytes)
Display statement at line 26
attivazione[1] = 0
quantita[1] = 200
attivazione[2] = 0
quantita[2] = 0
attivazione[3] = 0
quantita[3] = 0
attivazione[4] = 0
quantita[4] = 0
Display statement at line 27
costototale:
   20 quantita[1]
   100000 attivazione[1]
   30 quantita[2]
   70000 attivazione[2]
   30 quantita[3]
   80000 attivazione[3]
   35 quantita[4]
   40000 attivazione[4]
Model has been successfully processed

Compilation finished at Sat Oct 30 23:57:47
-----------------

Here quantita[1]=200, attivazione[1] = 0, but i had a constraint 
quantita[i]<=M*attivazione[1];

Is this because a used a value for M which is too big?

Thanks,
Antonio







reply via email to

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