Opened 6 years ago
Closed 5 years ago
#18734 closed enhancement (fixed)
Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.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.
Follow-up: #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
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 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 follow-up: ↓ 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 GLPK-specific (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 GLPK-specific (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 5 years ago by
- Status changed from needs_review to needs_work
branch does not apply, needs rebase
comment:20 Changed 5 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 5 years ago by
+ TESTS:: + sage: b = p.get_backend()
There should be a blank line in between these two lines.
comment:23 Changed 5 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 5 years ago by
Needs review.
comment:25 Changed 5 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 5 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 5 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 5 years ago by
- Milestone changed from sage-6.8 to sage-6.10
comment:29 Changed 5 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 5 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 5 years ago by
please see doctest errors in the attachment. Looks like there should be more dependencies, no?
comment:32 Changed 5 years ago by
- Status changed from needs_review to needs_info
comment:33 Changed 5 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 5 years ago by
$ sage -tp --long src/sage/numerical/mip.pyx Running doctests with ID 2015-11-16-19-56-36-49d68035. 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 --warn-long 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 --warn-long 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 5 years ago by
this is on Ubuntu 14.04, x86_64
comment:37 Changed 5 years ago by
- Status changed from needs_review to needs_work
tests do not pass, see patchbot reports
comment:38 Changed 5 years ago by
ping?
comment:39 Changed 5 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 5 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 5 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 5 years ago by
form == None
should be form is None
.
And there should be test(s) for non-default value(s) of the parameter form
.
comment:43 Changed 5 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 5 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 GLPK-specific 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 5 years ago by
- Milestone changed from sage-6.10 to sage-7.2
comment:46 Changed 5 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 5 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 5 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 5 years ago by
after you fix this little typo, please feel free to set the ticket to positive review.
comment:51 Changed 5 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 5 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 5 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