Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram

[Matthias Köppe]

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)

[Matthias Köppe]

New commits:

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

[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

[Nathann Cohen]

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.

[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

[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

[Matthias Köppe]

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.

[Nathann Cohen]

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

[Vincent Delecroix]

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

[git]

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

​11c72ac

doc string style fix

[Frédéric Chapoton]

branch does not apply, needs rebase

[git]

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

[Matthias Köppe]

It's rebased.

[Frédéric Chapoton]

+        TESTS::
+            sage: b = p.get_backend()

There should be a blank line in between these two lines.

[git]

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

[Matthias Köppe]

Needs review.

[git]

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

[git]

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

[Matthias Köppe]

This supports two backends now: GLPK, COIN. Needs review.

[git]

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

[Dima Pasechnik]

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:
 

[Dima Pasechnik]

doctest errors with Sage 6.10 beta3.

[Dima Pasechnik]

please see doctest errors in the attachment. Looks like there should be more dependencies, no?

[git]

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

[Zeyi Wang]

fixed.

[Dima Pasechnik]

$ 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

[Dima Pasechnik]

what I get as 'view(d2)' in the latest test error

[Dima Pasechnik]

this is on Ubuntu 14.04, x86_64

[Frédéric Chapoton]

tests do not pass, see patchbot reports

[Dima Pasechnik]

ping?

[Andrey Novoseltsev]

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".

[Matthias Köppe]

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

[Dima Pasechnik]

form == None should be form is None.

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

[Dima Pasechnik]

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.

[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

[Dima Pasechnik]

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

[git]

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

​cb64327

interactive_lp_problem: Construct slack names only for standard form

[Dima Pasechnik]

ok, good :)

[Dima Pasechnik]

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

 OUTPUT::

in mip.pyx should be

 OUTPUT:

[Dima Pasechnik]

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

[git]

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

​e8ffa20

MixedIntegerLinearProgram.gen: Fix documentation markup

[Matthias Köppe]

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

Thanks for reviewing, Dima.