Re: octave-glpk MIPGAP

[Marcelo Pinto]

Hi Jordi,

>From the fragment of the glpk code:

         /* check if the current point is optimal */
         if (csa->rpi < 1e-8 && csa->rdi < 1e-8 && csa->gap < 1e-8)
         {  if (csa->parm->msg_lev >= GLP_MSG_ALL)
               xprintf("OPTIMAL SOLUTION FOUND\n");
            status = 0;
            break;
         }

we have that the default relative gap is 1e-8. I have set the
param.mipgap = 1e-4 because others popular optimization packages like
IBM CPLEX use this value as default relative gap.

Here is the patch that needs to be applied to the current __glpk__.cc code:

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


The test file is attached. With the current version of the wrapper
this problem my never be solve, however after the patch, the problem
will be solved with a specified tolerance.

Best Regards,
Marcelo.


2011/4/1 Jordi Gutiérrez Hermoso <address@hidden>:
> Hi, Marcelo.
>
> 2011/4/1 Marcelo Pinto <address@hidden>:
>> 2011/3/28 Marcelo Pinto <address@hidden>:
>>> 2011/3/28 Jordi Gutiérrez Hermoso <address@hidden>:
>>>> 2011/3/28 Marcelo Pinto <address@hidden>:
>
>>>>> I'm not an expert in C++, but I have modified the __glpk__.cc
>>>>> source file and added the mipgap functionality.
>
>>>> Can you please post a patch or your modified source file? We can
>>>> work from there.
>
>>> The modified source file follows attached.
>
>> I have modified the __glpk__.cc with some help of glpk's folks. Now
>> the feature 'param.mipgap' works as expected.
>
> Do avoid top-posting if possible. It makes for awkward reading of a
> thread.
>
> I would like to push your patch, but I need some reassurance. As I
> don't know GLPK's options very well, can you write a short test that
> uses the mipgap option? I can add that test to Octave's GLPK code, and
> if your tests seem to pass, I can push the patch.
>
> From what I can read in the documentation, mipgap is relative
> tolerance for mixed integer programming. What does it default to if
> you don't set it, i.e. without your patch? Why did you choose 1e-4 for
> it?
>
> I can probably push this soon. I have been distracted by other Octave
> bugs and features.
>
> Thanks,
> - Jordi G. H.
>

mipgap_test.m
Description: Text Data