[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] MIP gap tolerance
From: |
Serveh Shalmashi |
Subject: |
[Help-glpk] MIP gap tolerance |
Date: |
Sun, 14 Nov 2010 19:47:47 +0100 |
User-agent: |
RoundCube Webmail/0.3.1 |
Hi,
I have an issue with the "mipgap" parameter in GLPK.
I have a mixed integer linear programming problem with (only) binary
integer variables. And I am using GLPK in MATLAB/Octave.
As I understood from the the help, setting the parameter "mipgap" to some
value, e.g., 0.1, should terminate the search "if the
relative mip gap for currently known best integer feasible solution falls
below this tolerance".
I need the solver to return a feasible solution when the gap is below a
certain value. However, in my example when the search is terminated,
although the output messages show some value for the objective value, the
solver returns "zero" for the objective value and all variables, and the
Status is 114 (which I did not find in the help).
Any idea what is the problem?
Here is the output messages of GLPK (for mipgap=0.1):
----------------------------------------------------
GLPK Integer Optimizer, v4.42
2502 rows, 629 columns, 11129 non-zeros
625 integer variables, all of which are binary
Preprocessing...
1728 constraint coefficient(s) were reduced
2073 rows, 629 columns, 9695 non-zeros
625 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.269e-003 max|aij| = 1.851e+000 ratio = 1.459e+003
GM: min|aij| = 1.887e-001 max|aij| = 5.300e+000 ratio = 2.810e+001
EQ: min|aij| = 3.766e-002 max|aij| = 1.000e+000 ratio = 2.655e+001
2N: min|aij| = 2.261e-002 max|aij| = 1.725e+000 ratio = 7.629e+001
Constructing initial basis...
Size of triangular part = 2073
Solving LP relaxation...
GLPK Simplex Optimizer, v4.42
2073 rows, 629 columns, 9695 non-zeros
* 0: obj = 0.000000000e+000 infeas = 0.000e+000 (0)
* 11: obj = -4.000000000e+000 infeas = 3.195e-035 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 11: mip = not found yet >= -inf (1; 0)
+ 797: >>>>> -3.837866915e+000 >= -3.990637406e+000 4.0% (146; 121)
+ 797: mip = -3.837866915e+000 >= -3.990637406e+000 4.0% (134; 145)
RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
---------------------------------------------------------
status = 114
Thanks,
Serveh
- [Help-glpk] MIP gap tolerance,
Serveh Shalmashi <=