Opened 7 years ago
Closed 7 years ago
#18734 closed enhancement (fixed)
Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
Reported by:  Matthias Köppe  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  numerical  Keywords:  lp 
Cc:  Nathann Cohen, Yuan Zhou, Zeyi Wang, Andrey Novoseltsev, Dima Pasechnik, Vincent Delecroix  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 7 years ago by
Component:  PLEASE CHANGE → numerical 

Type:  PLEASE CHANGE → enhancement 
comment:2 Changed 7 years ago by
Description:  modified (diff) 

comment:3 Changed 7 years ago by
Cc:  Zeyi Wang added 

comment:4 Changed 7 years ago by
Description:  modified (diff) 

comment:5 Changed 7 years ago by
Cc:  Andrey Novoseltsev Dima Pasechnik added 

Description:  modified (diff) 
comment:6 Changed 7 years ago by
Branch:  → u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram 

comment:7 Changed 7 years ago by
Authors:  → Aedi Wang 

Commit:  → de7de749e507ccfe284033629fa51580825784a1 
Status:  new → needs_review 
comment:8 Changed 7 years ago by
Commit:  de7de749e507ccfe284033629fa51580825784a1 → c14b07d296e806f080711366dc1d720cc871abd9 

comment:9 Changed 7 years ago by
Status:  needs_review → 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
P.S.: Oh. And what about renaming "construct_interactive_lp" to "interactive_linear_program"? We usually try to write the long names in Sage.
comment:10 Changed 7 years ago by
Commit:  c14b07d296e806f080711366dc1d720cc871abd9 → 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 7 years ago by
Commit:  76a9d51fe5fbb85d231ade23e88c89468b7a59db → 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 7 years ago by
Status:  needs_work → 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 Changed 7 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 7 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 7 years ago by
Status:  needs_review → needs_work 

comment:16 Changed 7 years ago by
Commit:  0ea963ebe950e2b3cd7218364b76f5a38d486fd5 → 11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa 

Branch pushed to git repo; I updated commit sha1. New commits:
11c72ac  doc string style fix

comment:17 Changed 7 years ago by
Status:  needs_work → needs_review 

comment:18 Changed 7 years ago by
Cc:  Vincent Delecroix added 

comment:19 Changed 7 years ago by
Status:  needs_review → needs_work 

branch does not apply, needs rebase
comment:20 Changed 7 years ago by
Commit:  11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa → 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 7 years ago by
+ TESTS:: + sage: b = p.get_backend()
There should be a blank line in between these two lines.
comment:23 Changed 7 years ago by
Commit:  a53762e046c8ed12335efa6694fe34dd4a4e127a → 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:25 Changed 7 years ago by
Commit:  68860aa153c178a886324c9aad53f112b972b7c2 → 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 7 years ago by
Commit:  2dbbd096e09efcc227e19e3c8dd743fb0ac07943 → 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 7 years ago by
Dependencies:  #18685, #18688, #18732, #18733 → #18685, #18732 

Description:  modified (diff) 
This supports two backends now: GLPK, COIN. Needs review.
comment:28 Changed 7 years ago by
Milestone:  sage6.8 → sage6.10 

comment:29 Changed 7 years ago by
Commit:  3a0b173e971a008c0f219410eaa25c5e258e69e2 → 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 7 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 7 years ago by
please see doctest errors in the attachment. Looks like there should be more dependencies, no?
comment:32 Changed 7 years ago by
Status:  needs_review → needs_info 

comment:33 Changed 7 years ago by
Commit:  b073b6ec696cddd3b3d2dfef3b04569577a780e4 → 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 7 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
Changed 7 years ago by
what I get as 'view(d2)' in the latest test error
comment:37 Changed 7 years ago by
Status:  needs_review → needs_work 

tests do not pass, see patchbot reports
comment:39 Changed 7 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 7 years ago by
Branch:  u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram → u/mkoeppe/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram 

comment:41 Changed 7 years ago by
Commit:  dece241d788c1d57fb9fa89ae377286140095c84 → 643ad4043715ce495095567201edf1fa99797d47 

Status:  needs_work → 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 7 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 7 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 7 years ago by
Commit:  643ad4043715ce495095567201edf1fa99797d47 → 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 7 years ago by
Authors:  Aedi Wang → Aedi Wang, Matthias Koeppe 

Milestone:  sage6.10 → sage7.2 
comment:46 Changed 7 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 7 years ago by
Commit:  b17dd3a6524557b668870c60820c49443bdf44e6 → 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 7 years ago by
Status:  positive_review → needs_work 

sorry, please have a look at the patchbots' output:
OUTPUT::
in mip.pyx should be
OUTPUT:
comment:50 Changed 7 years ago by
after you fix this little typo, please feel free to set the ticket to positive review.
comment:51 Changed 7 years ago by
Commit:  cb64327b597b39784adae750cc04808670445c38 → e8ffa20d8dfabc07f3a8b59936835731a925e2d4 

Branch pushed to git repo; I updated commit sha1. New commits:
e8ffa20  MixedIntegerLinearProgram.gen: Fix documentation markup

comment:52 Changed 7 years ago by
Reviewers:  → Dima Pasechnik 

Status:  needs_work → positive_review 
Fixed, it should have been "EXAMPLE::" actually.
Thanks for reviewing, Dima.
comment:53 Changed 7 years ago by
Branch:  u/mkoeppe/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram → e8ffa20d8dfabc07f3a8b59936835731a925e2d4 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
new function construct_interactiveLPProblem() in mip.pyx
new function get_variables() in mip.pyx