Re: Re: Re: octave-glpk MIPGAP

[Marcelo Pinto]

Hi Tommaso,

MIPGAP is a important resource for me and others who works with MIP, I
have no doubt that your patch should be accepted, Neils and your
efforts brings, not only that, but others important features for
octave-glpk interface.

I'm sorry, I messed up the values, the LINDO fmin value was 1.826200000e+05.

To facilitate our job, follows attached a fragment of the model where
I got the problem, so you can simulate that. Applying the two patches
and running this m file you will be able to compare the results.

Regards,
Marcelo.


On Wed, Apr 6, 2011 at 5:24 AM,  <address@hidden> wrote:
> On , Marcelo Pinto <address@hidden> wrote:
>
> Hi Marcelo, first of all let me thank you for the work that you're putting
> in verifying the correct behavior of the patch. If it gets pushed, any
> future Octave user will benefit from it.
>
>> The diff output that posted some days ago, does exactly that.
>
> Unfortunately, I used the .cc file that you distributed and not the patch
> and there's such check isn't present. But if eventually you added that check
> to the patch, it's fine.
>
>> 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:
>
> Patch #1
>> +   127: mip =     not found yet >=              -inf        (1; 0)
>> +   317: >>>>>   1.826200000e+05 >=   1.825400000e+05
>> +   317: mip =   1.826200000e+05 >=   1.825400000e+05
>> RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
>
> Patch #2
>> +   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)
>
> The problem is a minimization problem. As you can easily calculate, for
> Patch #2 the MIP GAP isn't reached, because it is indeed 0.12 something %,
> so it's normal that the optimization isn't finished. I would heavily
> recommend to check whether the solution calculated by Patch #1 is in the
> feasibility region of the problem, down to precision. If that's the case,
> the interesting question to answer here would be why, when you use
> lpx_simplex + lpx_integer instead of glp_intopt, you converge more rapidly.
> Before I venture into wild guessing, I would like to ask you to run the test
> again with GLPK 4.45 and post the results. Eventually if you could post the
> script that would also help.
>
> At the moment, because of what I see, I doubt that the problem, if there is
> one, is in how the patch handles the reach of the MIP GAP.
>
>> Note: The solution (fmin = 1.827600000e+05) with my patch matches the
>> LINDO solution.
>
> Patch #1 achieves 1.826200000e+05, which is better than what LINDO does.
> Patch #2 achieves 1.827600000e+05, which is what LINDO does, as you stated.
> This suggests that in the first case, you might be slightly off the
> feasibility region. Anyway, if LINDO returns at 1.827600000e+05, it simply
> means that rounding was used somewhere, because I would assume that the
> relaxed problem gives the same output anywhere.
>
> Regards,
>
> Tommaso

model.m
Description: Text Data