Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram

[mkoeppe]

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 or LPRevisedDictionary by invoking the dictionary or revised_dictionary methods.

#18685 added the prerequisite basis status information for the case of the GLPK backend. #18763 did the same for the COIN backend.

See also: #18688, #18733

Follow-up: #18804 (LPBackendDictionary)

Depends on #18685
Depends on #18732

CC: @nathanncohen @yuan-zhou @uduse @novoselt @dimpase @videlec

Component: numerical

Author: Aedi Wang, Matthias Koeppe

Branch/Commit: e8ffa20

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/18734

[uduse]

Branch: u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram

[mkoeppe]

Author: Aedi Wang

[mkoeppe]

New commits:

018c584	new function construct_interactiveLPProblem() in mip.pyx
de7de74	new function get_variables() in mip.pyx

[mkoeppe]

Commit: de7de74

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2b8e0b4	add function get_variables() to mip.pyx
c14b07d	add function construct_interactive_lp() to mip.pyx

[sagetrac-git]

Changed commit from de7de74 to c14b07d

[nathanncohen]

comment:9

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.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from c14b07d to 76a9d51

[sagetrac-git]

Changed commit from 76a9d51 to 0ea963e

[sagetrac-git]

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

[mkoeppe]

comment:12

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.

[nathanncohen]

comment:13

Hello !

new_variable has been dropped for this ticket, and the method has been renamed to interactive_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

[videlec]

comment:14

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

[sagetrac-git]

Changed commit from 0ea963e to 11c72ac

[mkoeppe]

Changed commit from dece241 to 643ad40

[mkoeppe]

comment:41

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

[dimpase]

comment:42

form == None should be form is None.

And there should be test(s) for non-default value(s) of the parameter form.

[dimpase]

comment:43

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.

[sagetrac-git]

Changed commit from 643ad40 to b17dd3a

[sagetrac-git]

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

[mkoeppe]

Changed author from Aedi Wang to Aedi Wang, Matthias Koeppe

[dimpase]

comment:46

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

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cb64327

interactive_lp_problem: Construct slack names only for standard form

[sagetrac-git]

Changed commit from b17dd3a to cb64327

[dimpase]

comment:48

ok, good :)

[dimpase]

comment:49

sorry, please have a look at the patchbots' output:

 OUTPUT::

in mip.pyx should be

 OUTPUT:

[dimpase]

comment:50

after you fix this little typo, please feel free to set the ticket to positive review.

[sagetrac-git]

Changed commit from cb64327 to e8ffa20

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e8ffa20

MixedIntegerLinearProgram.gen: Fix documentation markup

[mkoeppe]

comment:52

Fixed, it should have been "EXAMPLE::" actually.

Thanks for reviewing, Dima.

[mkoeppe]

Reviewer: Dima Pasechnik

[vbraun]

Changed branch from u/mkoeppe/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram to e8ffa20