Re: Re: octave-glpk MIPGAP

[Marcelo Pinto]

Hi Tommaso,

The diff output that posted some days ago, does exactly that. Here it is again:

73c73
< #define NRealP 10
---
> #define NRealP 11
126c126,127
<   1e-7
---
>   1e-7,
>   1e-4
139c140,141
<   LPX_K_TOLOBJ
---
>   LPX_K_TOLOBJ,
>   LPX_K_MIPGAP
341c343
<   if (errnum == LPX_E_OK)
---
>   if (errnum == LPX_E_OK || errnum == LPX_E_MIPGAP)
812a815,816
>
>   OCTAVE_GLPK_GET_REAL_PARAM ("mipgap", 10);


With this patch applied to the current version of __glpk__.cc, the
values of fmin, xmin, status and extra returns normally, when the
optimization reach 0.1% from the optimal LP solution. Here is the
output to param.msglev = 3; and param.mipgap = 0.1/100;, with this
patch:


GLPK Simplex Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
Preprocessing...
99 rows, 288 columns, 5280 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 99
      0: obj =   0.000000000e+00  infeas =  4.266e+03 (0)
*   107: obj =   1.897850000e+05  infeas =  0.000e+00 (0)
*   127: obj =   1.825400000e+05  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none of which are binary
Integer optimization begins...
+   127: mip =     not found yet >=              -inf        (1; 0)
+   317: >>>>>   1.826200000e+05 >=   1.825400000e+05 < 0.1% (51; 0)
+   317: mip =   1.826200000e+05 >=   1.825400000e+05 < 0.1% (45; 10)
RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED


Now, here is the output to the same script (param.mipgap = 0.1/100),
with your patch applied to the current __glpk__.cc:

GLPK Integer Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none of which are binary
Preprocessing...
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 99
Solving LP relaxation...
GLPK Simplex Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
      0: obj =   0.000000000e+00  infeas =  4.266e+03 (0)
*   107: obj =   1.897850000e+05  infeas =  0.000e+00 (0)
*   127: obj =   1.825400000e+05  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   127: mip =     not found yet >=              -inf        (1; 0)
+   698: >>>>>   1.834800000e+05 >=   1.825400000e+05   0.5% (97; 0)
+   840: >>>>>   1.828800000e+05 >=   1.825400000e+05   0.2% (114; 15)
+   852: >>>>>   1.827600000e+05 >=   1.825400000e+05   0.1% (89; 63)
+  5724: mip =   1.827600000e+05 >=   1.825400000e+05   0.1% (735; 260)
+ 10490: mip =   1.827600000e+05 >=   1.825400000e+05   0.1% (1342; 446)
+ 15153: mip =   1.827600000e+05 >=   1.825400000e+05   0.1% (1941; 626)

As you can see, in this case, when the solution is 0.1% from the
optimal LP solution , the optimization continues running indefinitely,
like the current version.

Note: The solution (fmin = 1.827600000e+05) with my patch matches the
LINDO solution.

Regards,
Marcelo.


On Mon, Apr 4, 2011 at 4:46 PM,  <address@hidden> wrote:
> On Apr 4, 2011 7:36pm, Marcelo Pinto <address@hidden> wrote:
>> I applied the patch and could see that it really has much more
>> features. However, when I ran a script that I know that the best
>> solution is 0.1% away from the optimal solution, the optimization
>> doesn't stop, even configuring 'param.mipgap = 0.1/100'.
>
> One additional remark. Don't panic when you'll see that the patch you posted
> cannot produce solutions that make sense when the gap is reached. This is
> due to the fact that you didn't update the errnum check to include a reached
> gap. In other words, in your patch if the gap is reached, xmin is never
> retrieved and therefore it is always [NA,...,NA]. Fix that and go through 2)
> and 3) again. Of course make sure you don't have random matrices/vectors in
> your script, otherwise you won't get much insight by using CPLEX or Gurobi.
>
> Regards,
>
> Tommaso