Opened 4 years ago

Closed 3 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) Commit: e8ffa20d8dfabc07f3a8b59936835731a925e2d4
Dependencies: #18685, #18732 Stopgaps:

Description (last modified by 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)

Attachments (2)

err-doctests (11.6 KB) - added by dimpase 3 years ago.
doctest errors with Sage 6.10 beta3.
sage.pdf (48.9 KB) - added by dimpase 3 years ago.
what I get as 'view(d2)' in the latest test error

Download all attachments as: .zip

Change History (55)

comment:1 Changed 4 years ago by mkoeppe

  • Component changed from PLEASE CHANGE to numerical
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:3 Changed 4 years ago by mkoeppe

  • Cc zwang added

comment:4 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:5 Changed 4 years ago by mkoeppe

  • Cc novoselt dimpase added
  • Description modified (diff)

comment:6 Changed 4 years ago by zwang

  • Branch set to u/zwang/construct_an_interactive_simplex_method_lpdictionary_from_a_mixedintegerlinearprogram

comment:7 Changed 4 years ago by mkoeppe

  • Authors set to Aedi Wang
  • Commit set to de7de749e507ccfe284033629fa51580825784a1
  • Status changed from new to needs_review

New commits:

018c584new function construct_interactiveLPProblem() in mip.pyx
de7de74new function get_variables() in mip.pyx

comment:8 Changed 4 years ago by git

  • Commit changed from de7de749e507ccfe284033629fa51580825784a1 to c14b07d296e806f080711366dc1d720cc871abd9

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

2b8e0b4add function get_variables() to mip.pyx
c14b07dadd function construct_interactive_lp() to mip.pyx

comment:9 Changed 4 years ago by ncohen

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

Last edited 4 years ago by ncohen (previous) (diff)

comment:10 Changed 4 years ago by git

  • Commit changed from c14b07d296e806f080711366dc1d720cc871abd9 to 76a9d51fe5fbb85d231ade23e88c89468b7a59db

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

76a9d51add functoin interactive_linear_program() to mip.pyx

comment:11 Changed 4 years ago by git

  • Commit changed from 76a9d51fe5fbb85d231ade23e88c89468b7a59db to 0ea963ebe950e2b3cd7218364b76f5a38d486fd5

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

0ea963eadd function interactive_linear_program() to mip.pyx

comment:12 follow-up: Changed 4 years ago by mkoeppe

  • 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 4 years ago by ncohen

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

comment:14 Changed 4 years ago by vdelecroix

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

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:15 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:16 Changed 3 years ago by git

  • Commit changed from 0ea963ebe950e2b3cd7218364b76f5a38d486fd5 to 11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa

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

11c72acdoc string style fix

comment:17 Changed 3 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:18 Changed 3 years ago by mkoeppe

  • Cc vdelecroix added

comment:19 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

branch does not apply, needs rebase

comment:20 Changed 3 years ago by git

  • Commit changed from 11c72ac6b2e1d8bc8ab5fa0515b2d330b2085dfa to a53762e046c8ed12335efa6694fe34dd4a4e127a

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

a53762eadd function interactive_linear_program() to mip.pyx

comment:21 Changed 3 years ago by mkoeppe

  • Status changed from needs_work to needs_review

It's rebased.

comment:22 Changed 3 years ago by chapoton

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

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

comment:23 Changed 3 years ago by git

  • Commit changed from a53762e046c8ed12335efa6694fe34dd4a4e127a to 68860aa153c178a886324c9aad53f112b972b7c2

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

68860aaadd function interactive_linear_program() to mip.pyx

comment:24 Changed 3 years ago by mkoeppe

Needs review.

comment:25 Changed 3 years ago by git

  • Commit changed from 68860aa153c178a886324c9aad53f112b972b7c2 to 2dbbd096e09efcc227e19e3c8dd743fb0ac07943

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

2dbbd09add function interactive_linear_program() to mip.pyx

comment:26 Changed 3 years ago by git

  • Commit changed from 2dbbd096e09efcc227e19e3c8dd743fb0ac07943 to 3a0b173e971a008c0f219410eaa25c5e258e69e2

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

3a0b173add function interactive_linear_program() to mip.pyx

comment:27 Changed 3 years ago by mkoeppe

  • 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 3 years ago by dimpase

  • Milestone changed from sage-6.8 to sage-6.10

comment:29 Changed 3 years ago by git

  • Commit changed from 3a0b173e971a008c0f219410eaa25c5e258e69e2 to b073b6ec696cddd3b3d2dfef3b04569577a780e4

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

b073b6eadd function interactive_linear_program() to mip.pyx

comment:30 Changed 3 years ago by dimpase

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:
 

Changed 3 years ago by dimpase

doctest errors with Sage 6.10 beta3.

comment:31 Changed 3 years ago by dimpase

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

comment:32 Changed 3 years ago by dimpase

  • Status changed from needs_review to needs_info

comment:33 Changed 3 years ago by git

  • Commit changed from b073b6ec696cddd3b3d2dfef3b04569577a780e4 to dece241d788c1d57fb9fa89ae377286140095c84

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

dece241Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram

comment:34 Changed 3 years ago by zwang

  • Status changed from needs_info to needs_review

fixed.

comment:35 Changed 3 years ago by dimpase

$ 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

Changed 3 years ago by dimpase

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

comment:36 Changed 3 years ago by dimpase

this is on Ubuntu 14.04, x86_64

comment:37 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

tests do not pass, see patchbot reports

comment:38 Changed 3 years ago by dimpase

ping?

comment:39 Changed 3 years ago by novoselt

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 3 years ago by mkoeppe

  • 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 3 years ago by mkoeppe

  • 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:

eba0fc7add function construct_interactive_lp() to mip.pyx
f9c9d2aFix docstring markup error
f07a942Change construct_interactive_lp doctest so it is not dual degenerate.
643ad40Improve doc markup

comment:42 Changed 3 years ago by dimpase

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 3 years ago by dimpase

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 3 years ago by git

  • Commit changed from 643ad4043715ce495095567201edf1fa99797d47 to b17dd3a6524557b668870c60820c49443bdf44e6

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

2cf02f1Rename construct_interactive_lp to interactive_lp_problem
4fba316Add solver backend methods is_variable_basic etc.
38bce15interactive_lp_problem: Use new backend methods instead of GLPK-specific functions
138d4edinteractive_lp_problem: Add doctests for form=None
acb2ae1interactive_lp_problem: In tests, request GLPK solver explicitly
b17dd3aUse "is None" instead of "== None", fix error messages

comment:45 Changed 3 years ago by mkoeppe

  • Authors changed from Aedi Wang to Aedi Wang, Matthias Koeppe
  • Milestone changed from sage-6.10 to sage-7.2

comment:46 Changed 3 years ago by dimpase

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 3 years ago by git

  • Commit changed from b17dd3a6524557b668870c60820c49443bdf44e6 to cb64327b597b39784adae750cc04808670445c38

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

cb64327interactive_lp_problem: Construct slack names only for standard form

comment:48 Changed 3 years ago by dimpase

  • Status changed from needs_review to positive_review

ok, good :)

comment:49 Changed 3 years ago by dimpase

  • 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 3 years ago by dimpase

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

comment:51 Changed 3 years ago by git

  • Commit changed from cb64327b597b39784adae750cc04808670445c38 to e8ffa20d8dfabc07f3a8b59936835731a925e2d4

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

e8ffa20MixedIntegerLinearProgram.gen: Fix documentation markup

comment:52 Changed 3 years ago by mkoeppe

  • 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 3 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.