Opened 6 years ago
Closed 6 years ago
#18734 closed enhancement (fixed)
Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  numerical  Keywords:  lp 
Cc:  ncohen, yzh, zwang, novoselt, dimpase, vdelecroix  Merged in:  
Authors:  Aedi Wang, Matthias Koeppe  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  e8ffa20 (Commits, GitHub, GitLab)  Commit:  e8ffa20d8dfabc07f3a8b59936835731a925e2d4 
Dependencies:  #18685, #18732  Stopgaps: 
Description (last modified by )
For teaching, presentation, and debugging purposes, it could be powerful
to have a function that sets up a sage.numerical.interactive_simplex_method.LPDictionary
corresponding to the current basis of a MixedIntegerLinearProgram
(with all variables real).
The plan is as follows:
MixedIntegerLinearProgram
.construct_interactive_lp() return an interactive LP (by querying the backend for problem data) and a list of basic variables (by querying the backend for col_stat, row_stat) from that information, can make an
LPDictionary
orLPRevisedDictionary
by invoking thedictionary
orrevised_dictionary
methods.
#18685 added the prerequisite basis status information for the case of the GLPK backend. #18763 did the same for the COIN backend.
Followup: #18804 (LPBackendDictionary)
Attachments (2)
Change History (55)
comment:1 Changed 6 years ago by
 Component changed from PLEASE CHANGE to numerical
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
 Cc zwang added
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
 Cc novoselt dimpase added
 Description modified (diff)
comment:6 Changed 6 years ago by
 Branch set to u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram
comment:7 Changed 6 years ago by
 Commit set to de7de749e507ccfe284033629fa51580825784a1
 Status changed from new to needs_review
comment:8 Changed 6 years ago by
 Commit changed from de7de749e507ccfe284033629fa51580825784a1 to c14b07d296e806f080711366dc1d720cc871abd9
comment:9 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
You assume in this code that the backend is GLPK. Also, I have to say that I do not like this get_variables
function much. It returns to the users the symbolic variables of the LP, to which he already has access through his calls to new_variable
. We may need this kind of things for our own methods, but in this case I think that it would be better to work directly with the integer id of the variables than with the symbolic ones.
That woud lead us to make function like get_values
accept an integer parameter (a variable's id), which is not a bad move. Especially if we plan to work with the dual LP later.
Also, return [k for k in self._variables.keys()]
is better written as self._variables().keys()
Nathann
comment:10 Changed 6 years ago by
 Commit changed from c14b07d296e806f080711366dc1d720cc871abd9 to 76a9d51fe5fbb85d231ade23e88c89468b7a59db
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
76a9d51  add functoin interactive_linear_program() to mip.pyx

comment:11 Changed 6 years ago by
 Commit changed from 76a9d51fe5fbb85d231ade23e88c89468b7a59db to 0ea963ebe950e2b3cd7218364b76f5a38d486fd5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
0ea963e  add function interactive_linear_program() to mip.pyx

comment:12 followup: ↓ 13 Changed 6 years ago by
 Status changed from needs_work to needs_review
Hi Nathann,
new_variable
has been dropped for this ticket, and the method has been renamed to interactive_linear_program
as you suggest.
The code is indeed GLPKspecific (explicit testing for it has been added)  more general support would require designing a common interface to basis status, which is #18688.
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Hello !
new_variable
has been dropped for this ticket, and the method has been renamed tointeractive_linear_program
as you suggest.
Thanks!
The code is indeed GLPKspecific (explicit testing for it has been added)  more general support would require designing a common interface to basis status, which is #18688.
Okayokayokay. For as long as a meaningful exception is raised when the backend is not one that the code handle, it's fine by me. Especially since in this case the 'right backend' is GLPK. It's more awkward when the only backend that supports a feature is one that Sage does not ship by default.
Nathann
comment:14 Changed 6 years ago by
Hello,
There are some possible improvements in the documentation:
 some of the lines are too long. Try to make them the same width as they are in the rest of the file.
 If you mention a class you can make a clickable reference to it by using :class:
name_of_the_class
 You wrote
``"std"``
(as a string) and``standard``
(as a variable). I guess both of them should be strings.  you should add a line break after
TESTS::
For all of these, look at the reference manual.
Vincent
comment:15 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:16 Changed 6 years ago by
 Commit changed from 0ea963ebe950e2b3cd7218364b76f5a38d486fd5 to 11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa
Branch pushed to git repo; I updated commit sha1. New commits:
11c72ac  doc string style fix

comment:17 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:18 Changed 6 years ago by
 Cc vdelecroix added
comment:19 Changed 6 years ago by
 Status changed from needs_review to needs_work
branch does not apply, needs rebase
comment:20 Changed 6 years ago by
 Commit changed from 11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa to a53762e046c8ed12335efa6694fe34dd4a4e127a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a53762e  add function interactive_linear_program() to mip.pyx

comment:22 Changed 6 years ago by
+ TESTS:: + sage: b = p.get_backend()
There should be a blank line in between these two lines.
comment:23 Changed 6 years ago by
 Commit changed from a53762e046c8ed12335efa6694fe34dd4a4e127a to 68860aa153c178a886324c9aad53f112b972b7c2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
68860aa  add function interactive_linear_program() to mip.pyx

comment:24 Changed 6 years ago by
Needs review.
comment:25 Changed 6 years ago by
 Commit changed from 68860aa153c178a886324c9aad53f112b972b7c2 to 2dbbd096e09efcc227e19e3c8dd743fb0ac07943
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2dbbd09  add function interactive_linear_program() to mip.pyx

comment:26 Changed 6 years ago by
 Commit changed from 2dbbd096e09efcc227e19e3c8dd743fb0ac07943 to 3a0b173e971a008c0f219410eaa25c5e258e69e2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3a0b173  add function interactive_linear_program() to mip.pyx

comment:27 Changed 6 years ago by
 Dependencies changed from #18685, #18688, #18732, #18733 to #18685, #18732
 Description modified (diff)
This supports two backends now: GLPK, COIN. Needs review.
comment:28 Changed 6 years ago by
 Milestone changed from sage6.8 to sage6.10
comment:29 Changed 6 years ago by
 Commit changed from 3a0b173e971a008c0f219410eaa25c5e258e69e2 to b073b6ec696cddd3b3d2dfef3b04569577a780e4
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b073b6e  add function interactive_linear_program() to mip.pyx

comment:30 Changed 6 years ago by
there is an indentation error that prevents docs from building. Here is how it should be:
diff git a/src/sage/numerical/mip.pyx b/src/sage/numerical/mip.pyx index 76a7eff..01ce34a 100644  a/src/sage/numerical/mip.pyx +++ b/src/sage/numerical/mip.pyx @@ 2489,9 +2489,9 @@ cdef class MixedIntegerLinearProgram(SageObject): INPUT:  ``form``  (default: ``"standard"``) a string specifying return type:  either ``None``, or ``"std"`` or ``"standard"``, respectively returns an  instance of :class:`InteractiveLPProblem` or an instance of  :class:`InteractiveLPProblemStandardForm` + either ``None``, or ``"std"`` or ``"standard"``, respectively returns an + instance of :class:`InteractiveLPProblem` or an instance of + :class:`InteractiveLPProblemStandardForm` OUTPUT:
comment:31 Changed 6 years ago by
please see doctest errors in the attachment. Looks like there should be more dependencies, no?
comment:32 Changed 6 years ago by
 Status changed from needs_review to needs_info
comment:33 Changed 6 years ago by
 Commit changed from b073b6ec696cddd3b3d2dfef3b04569577a780e4 to dece241d788c1d57fb9fa89ae377286140095c84
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
dece241  Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram

comment:35 Changed 6 years ago by
$ sage tp long src/sage/numerical/mip.pyx Running doctests with ID 2015111619563649d68035. Git branch: boo Using optional=bliss,cbc,d3js,database_gap,database_jones_numfield,gap_packages,mpir,nauty,python2,sage,scons Doctesting 1 file using 4 threads. sage t long warnlong 46.3 src/sage/numerical/mip.pyx ********************************************************************** File "src/sage/numerical/mip.pyx", line 2527, in sage.numerical.mip.MixedIntegerLinearProgram.number_of_variables.interactive_linear_program Failed example: d2.is_optimal() Expected: True Got: False ********************************************************************** 1 item had failures: 1 of 24 in sage.numerical.mip.MixedIntegerLinearProgram.number_of_variables.interactive_linear_program [514 tests, 1 failure, 1.41 s]  sage t long warnlong 46.3 src/sage/numerical/mip.pyx # 1 doctest failed  Total time for all tests: 1.5 seconds cpu time: 1.4 seconds cumulative wall time: 1.4 seconds
comment:36 Changed 6 years ago by
this is on Ubuntu 14.04, x86_64
comment:37 Changed 6 years ago by
 Status changed from needs_review to needs_work
tests do not pass, see patchbot reports
comment:38 Changed 6 years ago by
ping?
comment:39 Changed 6 years ago by
Just to comment on the test error: of course it is not optimal since it has a positive coefficient and of course it is optimal since that is just numerical noise. There were some places in interactive problems/dictionaries that were trying to mitigate such issues, but they were not perfect and we agreed to just get rid of them all together  the code is for learning "ideal simplex method" and works perfectly with rationals, numeric computations and errors are a different topic and are taken care off by "real solvers".
comment:40 Changed 6 years ago by
 Branch changed from u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram to u/mkoeppe/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram
comment:41 Changed 6 years ago by
 Commit changed from dece241d788c1d57fb9fa89ae377286140095c84 to 643ad4043715ce495095567201edf1fa99797d47
 Status changed from needs_work to needs_review
Changed the example so that the optimal dictionary is not dual degenerate, so the test should now work.
Also removed the "get_variables" method which had creeped in again. And rebased to current develop.
Needs review.
New commits:
eba0fc7  add function construct_interactive_lp() to mip.pyx

f9c9d2a  Fix docstring markup error

f07a942  Change construct_interactive_lp doctest so it is not dual degenerate.

643ad40  Improve doc markup

comment:42 Changed 6 years ago by
form == None
should be form is None
.
And there should be test(s) for nondefault value(s) of the parameter form
.
comment:43 Changed 6 years ago by
I also do not like that the code seems to assume that the default backend is always GLPK. If this is true this needs to be fixed. One might run
default_mip_solver()
to see the default.
comment:44 Changed 6 years ago by
 Commit changed from 643ad4043715ce495095567201edf1fa99797d47 to b17dd3a6524557b668870c60820c49443bdf44e6
Branch pushed to git repo; I updated commit sha1. New commits:
2cf02f1  Rename construct_interactive_lp to interactive_lp_problem

4fba316  Add solver backend methods is_variable_basic etc.

38bce15  interactive_lp_problem: Use new backend methods instead of GLPKspecific functions

138d4ed  interactive_lp_problem: Add doctests for form=None

acb2ae1  interactive_lp_problem: In tests, request GLPK solver explicitly

b17dd3a  Use "is None" instead of "== None", fix error messages

comment:45 Changed 6 years ago by
 Milestone changed from sage6.10 to sage7.2
comment:46 Changed 6 years ago by
you don't seem to need slack_names
if form is None
, why would you always create them?
+ # Construct slack names + slack_names = [format(back_end.row_name(i), 'w', i) for i in range(back_end.nrows())] + + A = coef_matrix + b = upper_bound_vector + c = objective_coefs_vector + x = var_names + w = slack_names + + if form is None: + from sage.numerical.interactive_simplex_method import InteractiveLPProblem + return InteractiveLPProblem(A, b, c, x), None + elif form == 'standard' or form == 'std': + from sage.numerical.interactive_simplex_method import InteractiveLPProblemStandardForm
comment:47 Changed 6 years ago by
 Commit changed from b17dd3a6524557b668870c60820c49443bdf44e6 to cb64327b597b39784adae750cc04808670445c38
Branch pushed to git repo; I updated commit sha1. New commits:
cb64327  interactive_lp_problem: Construct slack names only for standard form

comment:49 Changed 6 years ago by
 Status changed from positive_review to needs_work
sorry, please have a look at the patchbots' output:
OUTPUT::
in mip.pyx should be
OUTPUT:
comment:50 Changed 6 years ago by
after you fix this little typo, please feel free to set the ticket to positive review.
comment:51 Changed 6 years ago by
 Commit changed from cb64327b597b39784adae750cc04808670445c38 to e8ffa20d8dfabc07f3a8b59936835731a925e2d4
Branch pushed to git repo; I updated commit sha1. New commits:
e8ffa20  MixedIntegerLinearProgram.gen: Fix documentation markup

comment:52 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_work to positive_review
Fixed, it should have been "EXAMPLE::" actually.
Thanks for reviewing, Dima.
comment:53 Changed 6 years ago by
 Branch changed from u/mkoeppe/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram to e8ffa20d8dfabc07f3a8b59936835731a925e2d4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
new function construct_interactiveLPProblem() in mip.pyx
new function get_variables() in mip.pyx