Opened 9 years ago

Closed 9 years ago

#13518 closed enhancement (fixed)

Additions for sensitivity analysis in glpk_backend

Reported by: christiankuper Owned by: jason, jkantor
Priority: major Milestone: sage-5.6
Component: numerical Keywords: sensitivity analysis, lp, linear programming
Cc: john_perry, ncohen Merged in: sage-5.6.beta1
Authors: Christian Kuper Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

The GNU Linear Programming Kit (GLPK) provides functions to which SAGE currently does not provide access. These include:

  • Sensitivity analysis

The following enhancements might be helpful:

  • Access to glp_print_ranges to store results of a sensitivity analysis in a file
  • Access to GLPK function for getting shadow prices and reduced costs

Apply:

Attachments (1)

trac_13518_sens_analysis_imp.patch (11.1 KB) - added by ncohen 9 years ago.
glpk_backend extensions for sensitivity analysis (updated2)

Download all attachments as: .zip

Change History (27)

comment:1 Changed 9 years ago by christiankuper

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by christiankuper

I have reworked the patch (which was originally written for Sage 4.8) for 5.3. In addition access to the max_flow algo has been implemented.

comment:3 Changed 9 years ago by christiankuper

  • Cc john_perry ncohen added
  • Description modified (diff)

comment:4 follow-up: Changed 9 years ago by ncohen

Hello Christian. Let's make this straight from the beginning : I am very happy that you want to contribute to Sage, but what we are doing here is write a software, not your resume. In your patch there are 11 additions of your name inside of Sage's code. You add it to the documentation, you add it to the source code as comments, you even add it before 3 lines in a .pxd file where you import stuff from a library.

Now Sage is a free software, and everybody's work should be credited indeed. Your name will appear in Sage's release notes, it will appear on this website. That's enough. We're not about to add our name to Sage's source code each time we add one line, and the reason why you can still read this file is that we don't.

Well. You have not set this ticket to "needs_review", and judging from things like

sage: p.write_ccdata("/home/chris/graph.dat") 

it looks like you are still working on it. I will be glad to help with the review proces when it will be ready (or even before, or whenever needed), but in the meantime please try to imitate the writing style of the source code in its current state.

Nathann

comment:5 in reply to: ↑ 4 Changed 9 years ago by christiankuper

Hello Nathann. Thanks for the feedback - comments are well taken. Actually, I thought making changes visible would be helpful for the review process, the intention was not gaining credits. As it is my first contribution please excuse this "newbie" error. I will follow you advice and rework the code.

Christian

Hello Christian. Let's make this straight from the beginning : I am very happy that you want to contribute to Sage, but what we are doing here is write a software, not your resume. In your patch there are 11 additions of your name inside of Sage's code. You add it to the documentation, you add it to the source code as comments, you even add it before 3 lines in a .pxd file where you import stuff from a library.

Now Sage is a free software, and everybody's work should be credited indeed. Your name will appear in Sage's release notes, it will appear on this website. That's enough. We're not about to add our name to Sage's source code each time we add one line, and the reason why you can still read this file is that we don't.

Well. You have not set this ticket to "needs_review", and judging from things like

sage: p.write_ccdata("/home/chris/graph.dat") 

it looks like you are still working on it. I will be glad to help with the review proces when it will be ready (or even before, or whenever needed), but in the meantime please try to imitate the writing style of the source code in its current state.

Nathann

comment:6 follow-up: Changed 9 years ago by ncohen

Helloooooooooo Christian !

Well, I asked a friend of mine about the message I sent yesterday -- as I customarily get angry over trivial things -- and it looks like it was one of these times again... Sage is one of the few things people still work on for pleasure and not for money or anything, and these things are really hard to find right now, so... ^^;

About your patch : it is very large, and because it is one your first there are many things to fix (trivial things that Sage developpers agreed were necessary in a patch), and because your patch is so long... It shows. But we'll fix that ! :-)

There are actually two important things to keep in mind :

  • All the examples that are given in Sage's source code (inside of each function) are used both by users when they wonder how the method should be used, but also to automatically test sage. Before it is release, we run "sage -t " on every file, and all tests have to pass. And no patch is accepted whose "doctests" fail to pass. And of course a command like p.write_ccdata("/home/chris/graph.dat") is only valid on your computer. There's no /home/chris/ directory on mine ! Hence
    sage -b && sage -t glpk_backend.pyx
    
    would not pass tests on my computer. And all files should pass tests.
  • The documentation that you write in each function is useful in this text version, but it is also (badly) compiled to a html doc. That's how :
    sage -b && sage -docbuild reference html
    
    And of course the documentation should also be nicely displayed in this html files. Sometimes one forgets to use :: instead of :, and the documentation misses something

Once more, do you consider your file needing a review or not yet ? It's not a big decision to take : I just wonder whether I should spend the time necessary to read, understand and make comments on your patch right now, or whether you still work on the file at the moment. Actually, it would be nice if you could try to fix those two things : documentation and doctests, upate your patch, and then we'll begin the review.

Have fuuuuuuuun ! And thank you for your patch :-)

Nathann

comment:7 Changed 9 years ago by ncohen

Oh, and also : when you want to see what a patch changes in a file, there's something much easier that adding hints in the cod... Just look at the .patch file. For instance, reading this is very explicit already :-) http://trac.sagemath.org/sage_trac/attachment/ticket/13518/trac_13518_imp_for_sage5_3.patch

Nathann

comment:8 Changed 9 years ago by ncohen

OOps, and another thing I forgot. It's a tool to tell you whether you forgot to add a doctest to some method in Sage :

sage -coverage file.pyx

Nathann

comment:9 Changed 9 years ago by christiankuper

  • Status changed from needs_review to needs_work

comment:10 in reply to: ↑ 6 ; follow-up: Changed 9 years ago by christiankuper

Once more, do you consider your file needing a review or not yet ? It's not a big decision to take : I just wonder whether I should spend the time necessary to read, understand and make comments on your patch right now, or whether you still work on the file at the moment. Actually, it would be nice if you could try to fix those two things : documentation and doctests, upate your patch, and then we'll begin the review.

Thanks for you very helpful input. Before you or anybody else spending time on reviewing I will need to fix quite a number of things, thereroe I changed the status to "needs work".

Thanks again

Christian

comment:11 in reply to: ↑ 10 Changed 9 years ago by ncohen

Before you or anybody else spending time on reviewing I will need to fix quite a number of things, thereroe I changed the status to "needs work".

Nice ! If I can be of any help in the meantime, send me an email :-)

Nathann

comment:12 Changed 9 years ago by christiankuper

  • Description modified (diff)

comment:13 Changed 9 years ago by christiankuper

  • Status changed from needs_work to needs_review

comment:14 Changed 9 years ago by christiankuper

  • Summary changed from Additions for sensitivity analysis and mincost_okalg in glpk_backend to Additions for sensitivity analysis in glpk_backend

comment:15 follow-ups: Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooo Christian !

Thank you for this updated patch !

Well, there is not much to say at this level...

  • There's a double '-' before your name at the beginning of the file
  • Thank you for the lp->mps fix.. Could you also change the filename, which currently ends with .lp ?
  • It feels a bit weird to have a print_* method that does not print anything but writes the output to a file. Of course that's how the GLPK function is named, so it makes sense... What would you think of modifying it just a bit so that it can also "PRINT" the information that is being written to a file ? Something like, by default, write the information to a file and print it, unless the user explicitely wants the information to be written to a file, not displayed ? I can do that in another patch if you like the idea and don't want to spend time on it.
  • What about just having get_row_dual and not get_constraint_shadow_price, which is just an alias to it anyway ? Besides, get_row_dual is how the GLPK function is named, and this method's docstring can mention what a shadow price is at the same time ? And the same goes for cols.
  • In the documentation of get_backend, why do you put instance inside of quotes ? We usually do this for python expressions.

Thank you agaiiiiiiiiiiin ! :-)

Nathann

comment:16 in reply to: ↑ 15 Changed 9 years ago by christiankuper

Replying to ncohen:

Hello Nathann,

thank you for your fast feedback. All your comments are convincing, I will rework the patch accordingly. (Might take a few days as I will not have much time during next week). The suggestion regarding the "PRINT" function is really cool!

Thanks again!!!

Christian

comment:17 Changed 9 years ago by christiankuper

  • Status changed from needs_work to needs_review

comment:18 in reply to: ↑ 15 Changed 9 years ago by christiankuper

Replying to ncohen:

  • There's a double '-' before your name at the beginning of the file
  • Thank you for the lp->mps fix.. Could you also change the filename, which currently ends with .lp ?
  • It feels a bit weird to have a print_* method that does not print anything but writes the output to a file. Of course that's how the GLPK function is named, so it makes sense... What would you think of modifying it just a bit so that it can also "PRINT" the information that is being written to a file ? Something like, by default, write the information to a file and print it, unless the user explicitely wants the information to be written to a file, not displayed ? I can do that in another patch if you like the idea and don't want to spend time on it.
  • What about just having get_row_dual and not get_constraint_shadow_price, which is just an alias to it anyway ? Besides, get_row_dual is how the GLPK function is named, and this method's docstring can mention what a shadow price is at the same time ? And the same goes for cols.
  • In the documentation of get_backend, why do you put instance inside of quotes ? We usually do this for python expressions.

Hello Nathann,

I have implmented your suggested changes and updated it for Sage 5.4.

Looking forward to your feedback!

Christian

comment:19 follow-up: Changed 9 years ago by ncohen

Wow.. Thumbs up :-)

This patch is almost perfect : there is an occurrence of "algorthm" somewhere in the patch, and one line in the docstring of get_col_dual is very long too. Shot of that, I thought that the behaviour of the print_ranges method would be to display the table if no file argument is given, and to write it to the file (without displaying it) otherwise.

What do you think ? I never used these methods before so I will trust that what you think is the best behaviour should be the one we implement in Sage.

After this the ticket will be good to go :-)

Thank you again !

Nathann

comment:20 in reply to: ↑ 19 Changed 9 years ago by christiankuper

Hello Nathann,

thanks for your comments.

...there is an occurrence of "algorthm" somewhere in the patch,

I searched all over the place and could'nt find that typo :-(. I did find an "algorithn" in one place and replaced that. (I fear I am not a good proof reader ;-))

and one line in the docstring of get_col_dual is very long too.

Changed that.

Shot of that, I thought that the behaviour of the print_ranges method would be to display the table if no file argument is given, and to write it to the file (without displaying it) otherwise.

You're right, you suggestion is better due to the wide output of the analysis report and it gives more flexibility for applications. Implemented your approach.

Thanks a lot for your help.

Christian

comment:21 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Keywords out-of-kilter removed
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Welllllllll.... Nothing else to say.. Passes all tests, looks totally perfect to me.. Great work ! Thank you very much :-)

Nathann

comment:22 Changed 9 years ago by jdemeyer

Rebased to sage-5.5.rc0.

comment:23 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

On arando (32-bit Linux i686):

sage -t  --long -force_lib devel/sage/sage/numerical/mip.pyx
Writing problem data to `/var/lib/buildbot/.sage/temp/arando/15990/lp_problem.mps'...
17 records were written
Writing problem data to `/var/lib/buildbot/.sage/temp/arando/15990/lp_problem.lp'...
9 lines were written
GLPK Simplex Optimizer, v4.44
2 rows, 2 columns, 4 non-zeros
*     0: obj =   7.000000000e+00  infeas =  0.000e+00 (0)
*     2: obj =   9.400000000e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
**********************************************************************
File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.6.beta0/devel/sage-main/sage/numerical/mip.pyx", line 1853:
    sage: p.solve()
Expected:
    9.399999999999999
Got:
    9.4
**********************************************************************

comment:24 follow-up: Changed 9 years ago by ncohen

  • Status changed from needs_work to positive_review

Just added # tolerance flag to the doctests of this patch that return numerical values. Sorry for that !

Nathann

Changed 9 years ago by ncohen

glpk_backend extensions for sensitivity analysis (updated2)

comment:25 in reply to: ↑ 24 Changed 9 years ago by christiankuper

Replying to ncohen:

Just added # tolerance flag to the doctests of this patch that return numerical values. Sorry for that !

Nathann

Thanks for quickly jumping in here, Nathann!!!

Christian

comment:26 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.6.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.