Quantcast

Re: octave-glpk MIPGAP

classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Tommaso Balercia
On Apr 6, 2011 3:35pm, Marcelo Pinto <[hidden email]> wrote:

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

Thanks for the script. I can indeed replicate the problem you mention both with GLPK 4.44 and GLPK 4.45.

The strange thing is that your program in GLPKMEX is solved correctly, but with a third path even. Ideally, Patch #2 should produce the very same result, but that's not the case. I looked through the code, but at the moment a solution is not apparent. I will try to spend some time on it over the week.

Regards,

Tommaso
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Marcelo Pinto
Hello Jordi,

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.

Best Regards,
Marcelo.


On Wed, Apr 6, 2011 at 3:53 PM, <[hidden email]> wrote:
On Apr 6, 2011 3:35pm, Marcelo Pinto <[hidden email]> wrote:

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

Thanks for the script. I can indeed replicate the problem you mention both with GLPK 4.44 and GLPK 4.45.

The strange thing is that your program in GLPKMEX is solved correctly, but with a third path even. Ideally, Patch #2 should produce the very same result, but that's not the case. I looked through the code, but at the moment a solution is not apparent. I will try to spend some time on it over the week.

Regards,

Tommaso

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Jordi Gutiérrez Hermoso-2
2011/12/22 Marcelo Pinto <[hidden email]>:
> 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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Marcelo Pinto
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 <[hidden email]>
2011/12/22 Marcelo Pinto <[hidden email]>:
> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Marcelo Pinto
In reply to this post by Jordi Gutiérrez Hermoso-2
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 <[hidden email]>
2011/12/22 Marcelo Pinto <[hidden email]>:
> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Tommaso Balercia

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: [hidden email] [mailto:[hidden email]] 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 <[hidden email]>

2011/12/22 Marcelo Pinto <[hidden email]>:

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

 


glpk.m (25K) Download Attachment
__glpk__.cc (38K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Marcelo Pinto
Hi Tommaso,

Your patch works very well in my machine and I got the same results that you have had for the problem.

Jordi, follows attached the script "model.m" that people can use to compare the behavior of the current implementation of GPLK and the Tommaso one. As one can see, between other improvements, the MIPGAP now is avaliable.

Great job!
Marcelo.


2011/12/22 Tommaso Balercia <[hidden email]>

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: [hidden email] [mailto:[hidden email]] 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 <[hidden email]>

2011/12/22 Marcelo Pinto <[hidden email]>:

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

 


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Jordi Gutiérrez Hermoso-2
You guys really need to stop top-posting... ;-)

    http://en.wikipedia.org/wiki/Top-posting#Top-posting

On 23 December 2011 13:03, Marcelo Pinto <[hidden email]> wrote:
> Your patch works very well in my machine and I got the same results that you
> have had for the problem.

Okay, so you confirm that Tommaso's patch should be applied?

I think I need confirmation from our release manager if this can go
into 3.6 or if it should wait until the next stable release.

> Jordi, follows attached the script "model.m"

You seem to have forgotten this.

- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Marcelo Pinto
Sorry about the top-posting... 

I have tested some LP and MIP models, using Tommaso patch, and all of them ran properly. So, if nobody disagree, I think his patch should be applied as soon as possible.
The file "model.m" was attached some messages ago. Anyway here it is.

Best Regards,
Marcelo.

model.m (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Jordi Gutiérrez Hermoso-2
2011/12/23 Marcelo Pinto <[hidden email]>:

> I have tested some LP and MIP models, using Tommaso patch, and all
> of them ran properly. So, if nobody disagree, I think his patch
> should be applied as soon as possible. The file "model.m" was
> attached some messages ago. Anyway here it is.

I wish Tommaso had followed our coding standards... It's very
difficult for me to know if all of his changes are important or not. I
also wish I could get an explanation of what the changes are (a commit
message). Having to do this work myself makes me lazy and delays
pushing this patch. A diff would have been preferrable.

At any rate, it's obviously too late to include this in 3.6. I started
working on creating a patch starting from this, but I got lazy again.

So, in order to push this change into Octave we need:

   1) A proper patch
   2) A commit message
   3) Reformat to follow Octave's GNU coding standards
   4) Properly written tests to show that the changes work (i.e.
      included as part of the patch, in the glpk.m source file)

I have just been lazy about doing these things myself, so if you want
this done, either Tommaso or Marcelo or someone who cares needs to
handle the paperwork, or you can wait until I or someone else gets
unlazy. With some luck, I might do it today, if I feel sufficiently
motivated.

Tommaso said he started the modifications from the 3.4.3 tarball, so
that's the first step to generating a proper patch.

Sorry,
- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Tommaso Balercia
2012/01/20 Jordi Gutiérrez Hermoso

> I wish Tommaso had followed our coding standards... It's very difficult
> for me to know if all of his changes are important or not. I also wish
> I could get an explanation of what the changes are (a commit message).
> Having to do this work myself makes me lazy and delays pushing this patch.
> A diff would have been preferrable.

Hi Jordi, I'm sorry but I'm in a serious shortage of spare time at the moment.
And I'm afriad I can't be of assistance in trimming the patch.

This said, the commit message could be something in the range of:

'Updated glpk to support all the features offered by GLPK 4.36+'

As for the diff, they are just two files. The diffs can be easily generated
from the originals in 3.4.3. Just keep a vanilla version of 3.4.3 and one with
the files I attached in the other email and let hg do the magic.

Finally, I would like to say that I adhered to the style used in GLPKMEX,
the MATLAB counterpart of the patch. Keeping the two pieces of code with
a similar look might make sense, but feel free to manipulate it according
to Octave's guidelines. Maybe using astyle as somebody else suggested in
another occasion?

> At any rate, it's obviously too late to include this in 3.6.

No problem. I wrote the patch because I needed it myself. It served its
purpose. If you want to include it, I think others could benefit from the
potentialities it offers. Otherwise, no hard feelings. :-)

> 1) A proper patch
> 2) A commit message
> 3) Reformat to follow Octave's GNU coding standards

See above.

> 4) Properly written tests to show that the changes work (i.e.
>    included as part of the patch, in the glpk.m source file)

If Marcelo agrees, we can use his own code as a test. Additionally we can point
to MIP libs for more elaborate test. GLPKMEX includes my own Python script to
import MPS files. We can reuse that if you want.

Kind regards,

Tommaso Balercia

12
Loading...