octave-maintainers
[Top][All Lists]
Advanced

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

Re: Re: Re: octave-glpk MIPGAP


From: tommaso . balercia
Subject: Re: Re: Re: octave-glpk MIPGAP
Date: Wed, 06 Apr 2011 08:24:05 +0000

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
reply via email to

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