RE: Re: Re: Re: octave-glpk MIPGAP

Hi All,

unfortunately, I’ve been way too busy lately to keep Savannah updated. Below you find the result I get using Octave 3.4.3 + the files attached on the problem Marcelo posed. If Marcelo can confirm a proper behavior on his machine, I think we’re pretty much where we want to be with this patch and the outstanding issue is resolved.

Kind regards,

Tommaso

/*****

GLPK Integer Optimizer, v4.46

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.46

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)

* 133: obj = 1.825400000e+05 infeas = 2.128e-14 (0)

OPTIMAL SOLUTION FOUND

Integer optimization begins...

+ 133: mip = not found yet >= -inf (1; 0)

+ 4006: >>>>> 1.826200000e+05 >= 1.825400000e+05 < 0.1% (59; 0)

+ 4006: mip = 1.826200000e+05 >= 1.825400000e+05 < 0.1% (35; 47)

RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED

ans = 235

fmin = 182620

status = 2

extra =

scalar structure containing the fields:

time = 0

mem = 1141.6

From: address@hidden [mailto:address@hidden On Behalf Of Marcelo Pinto
Sent: giovedì 22 dicembre 2011 22:50
To: Jordi Gutiérrez Hermoso
Cc: Octave Maintainers List
Subject: Re: Re: Re: Re: octave-glpk MIPGAP

I agree that the Tommasso implementation is more complete. Unfortunately, at that time Tommasso and I could verify that his implementation presented a strange behavior for small values of GAP.

In the last conversation we had, he said he would try to fix that. If he has already fixed, apply his patch would be perfect. Otherwise, once that the current implementation is working fine, we could just apply the patch that I suggested, while his code isn't ready.

Once the patch is very simple and successful tests have been done, I see no technical problems to add this feature in the next release, however you guys who knows the correct time for the things here.

Anyway I will submit the patch and demonstrate how it works!

Thanks,

Marcelo.

2011/12/22 Jordi Gutiérrez Hermoso <address@hidden>

2011/12/22 Marcelo Pinto <address@hidden>:

> Please, consider to apply the patch that I suggested some time ago. The
> MIPGAP is a really important functionality of GPLK that is missing in the
> wrapper.

It's been some time, but reading through my log of this conversation,
there were two competing implementations, one seemed more complete
than the other, and I asked for some tests that demonstrated the
correctness of the implementation. Preferrably of the more complete
one. It seems you only cared about one particular feature of GLPK,
whereas Tommaso had a more comprehensive patch that included yours as
a special case.

I don't understand GLPK and at the moment with the impending release I
don't want to spend time learning, but if you could please provide the
patch again and in the patch write some tests to demonstrate how it
works, I will be happy to push it, or perhaps someone else will.

Please submit the patch to our patch tracker so it's less likely to be
forgotten:

https://savannah.gnu.org/patch/?group=octave

Octave 3.6 is about to be released, so I'm not sure if this feature
will make it in time for the release. We're right now in the
stabilising phase of the release, so I don't think this is a good time
to add new features to 3.6. It may have to wait until a future stable
release of Octave.

Thanks,
- Jordi G. H.

From:	Tommaso Balercia
Subject:	RE: Re: Re: Re: octave-glpk MIPGAP
Date:	Fri, 23 Dec 2011 00:43:42 +0100