Opened 4 years ago

Closed 3 years ago

#19097 closed enhancement (fixed)

Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method

Reported by: mkoeppe Owned by: pjxiao
Priority: major Milestone: sage-7.0
Component: numerical Keywords: lp
Cc: novoselt, yzh, zwang, pjxiao Merged in:
Authors: Andrey Novoseltsev Reviewers: Peijun Xiao
Report Upstream: N/A Work issues:
Branch: 586d0fa (Commits) Commit: 586d0fa61bc4dcb946558a16358d90e737d4960f
Dependencies: #19616 Stopgaps:

Description

This patch refactors the InteractiveLPProblemStandardForm methods run_simplex_method and run_revised_simplex_method by moving the bulk of their implementations to dictionary methods.

It also implements the dual simplex method, adding methods run_dual_simplex_method to both InteractiveLPProblemStandardForm and dictionary classes.

Attachments (1)

19097.pdf (58.6 KB) - added by novoselt 4 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/dual_simplex_method

comment:2 follow-up: Changed 4 years ago by novoselt

  • Commit set to 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5

I would very much appreciate more discussion and planning before charging in with changes to the existing code.

As I have said before - ELLUL is not necessarily the best name in the first place and for revised dictionaries it just does not make sense. For regular dictionaries where one can see for simple problems entering/leaving pairs right away, it is a convenient shortcut for entering

D.enter(1)
D.leave(2)
show(D)
D.update()
show(D)

and even here the necessity of first show is questionable since all if does is repeating the old output with different colours that convey no new information - it is just visually pleasing to some extent.

With revised dictionaries, however, a student CANNOT determine the leaving variable before setting the entering one and either displaying the dictionary (which will have new information allowing picking leaving) or at least asking for ratios. A typical sequence of commands for a single step is then

D.enter(1)
show(D)
D.leave(2)
show(D)
D.update()
show(D)

where the intermediate show may be dropped since it does not add anything but colours.

Of course, that's what one does when working "by hand" and for an automated solution one may want to show ONLY that "unnecessary" intermediate dictionary with all the information and colours.

So how about:

  • do not add new stupidly named methods (I am allowed to call ELLUL stupid since I've invented it ;-))
  • add run_simplex_method and run_dual_simplex_method to abstract dictionaries with implementation relying on abstract methods only and something like _preupdate_output (empty string or None by default) to allow stuff like inversion of matrices in the revised case, we'll get something like
    if not self.is_feasible():
        ValueError("simplex method is applicable to feasible dictionaries only")
    while not self.is_optimal():
        entering = min(self.possible_entering())
        self.enter(entering)
        leaving = min(self.possible_leaving())
        if leaving is not None:
            self.leave(leaving)
        add_to_output(latex(self))
        if leaving is None:
            add_to_output("The problem is unbounded in ${}$ direction.".format(latex(entering)))
            break
        add_to_output("Entering: ${}$. Leaving: ${}$.".format(latex(entering), latex(leaving))))
        add_to_output(self._preupdate_output)
        self.update()
    if self.is_optimal():
        add_to_output(latex(self))
    return output_as_HTMLFragment
    
  • simplify run_simplex_method etc in the problems that will now build a bigger HTMLFragment based on the stuff returned from dictionaries.

In 6.9 it is possible to create HTMLFragments and my thinking here is

\begin{array} %dictionary
...
\end{array}
Entering $x_1$. Leaving $x_2$.
\begin{array}
...
\end{array}
...

which will work both as HTML code (with MathJax? drawing only small formulas rather than everything as a single nested array) and as LaTeX code (with automatic pagination since again formulas are as small as actual formulas rather than the current situation). It is not going to display nicely yet in the notebook or cloud but hopefully we can work on it during 6.10 release cycle. I've made necessary adjustments to the notebook: https://github.com/sagemath/sagenb/pull/350 and work is under way to fit rich output system into cloud.

How does this sound? I am happy to implement the above for current dictionaries and leave you the dual ones.


New commits:

528c8d3New: run_dual_simplex_method

comment:3 in reply to: ↑ 2 ; follow-up: Changed 4 years ago by mkoeppe

Thanks for taking a look.

Replying to novoselt:

As I have said before - ELLUL is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.

Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.

So how about:

  • do not add new stupidly named methods (I am allowed to call ELLUL stupid since I've invented it ;-))
  • add run_simplex_method and run_dual_simplex_method to abstract dictionaries with implementation relying on abstract methods only [...]

Yes.

  • simplify run_simplex_method etc in the problems that will now build a bigger HTMLFragment based on the stuff returned from dictionaries.

Agreed.

In 6.9 it is possible to create HTMLFragments [....]

This sounds like a good direction.

How does this sound? I am happy to implement the above for current dictionaries and leave you the dual ones.

Sounds good.

comment:4 Changed 4 years ago by novoselt

  • Branch changed from u/mkoeppe/dual_simplex_method to u/novoselt/dual_simplex_method

Changed 4 years ago by novoselt

comment:5 Changed 4 years ago by novoselt

  • Commit changed from 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5 to 671e58947e62a0fe1812e2b61fa26b5071c1da1c

OK, here is my first take (not ready for final review, not sufficiently tested yet, and almost certainly not working well with floats). For testing in SageNB you need my fix to it - I am attaching a printout for a getting some sense of how things look like.

Note nice pagination for P.run_simplex_method2() due to the fact that each dictionary is a separate formula and compare it to P.run_simplex_method() (old version, single formula) which occupies a separate page but gets truncated.

In SMC and perhaps Jupiter notebook you can try it right away, I guess.

The float problem is demonstrated here: https://sage373.math.ualberta.ca/home/pub/21/ where optimality of the auxiliary dictionary is detected because x0 is non-basic. Of course, we can just say that automatic methods are guaranteed to work only for exact rings and otherwise users should decide for themselves where small numbers are actually zeros and treat them appropriately. My worksheet will get broken, but can be recreated with manual steps.


New commits:

671e589Add run_simplex_method to dictionaries.

comment:6 Changed 4 years ago by mkoeppe

Thanks a lot, we'll take a look.

For working with floating point (which is unavoidable for our "backend dictionaries" in #18804), we are working on a solution that should work without any changes to the interactive_simplex_method code. Take a look at "LPCleanDictionary" in the (preliminary) patch for #18804 at http://git.sagemath.org/sage.git/commit/?h=u/zwang/temp&id=440ed874635c88940bc0f06c6ed1e913c29d9042 Discussion very welcome.

comment:7 Changed 4 years ago by git

  • Commit changed from 671e58947e62a0fe1812e2b61fa26b5071c1da1c to 7383d6793332774248e9934b6aad7110c0a99ad5

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

7383d67Refactor run_simplex_method to dictionaries and LP problems.

comment:8 Changed 4 years ago by novoselt

OK, let's just drop floating workarounds here. I've made some more changes, but still didn't test it extensively.

By the way - which frontend are you working with? Ideally it should not matter, of course. In this version I got rid of "notruncate" in HTML comments (necessary for SageNB) - it is still present as LaTeX comment inside of environments for dictionaries.

comment:9 Changed 3 years ago by git

  • Commit changed from 7383d6793332774248e9934b6aad7110c0a99ad5 to 63fa3857f40d5944786ec69840c34eccc24a0e44

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

dc70260Add run_dual_simplex_method to dictionaries.
63fa385Fix handling of unbounded/infeasible problems and add tests.

comment:10 Changed 3 years ago by novoselt

After refactoring adding dual method was almost trivial, so I've done it, ran some tests, and fixed a mistake in handling unbounded/infeasible problems in dictionaries. Ready for review apart from the fact that SageNB support is not there yet.

comment:11 in reply to: ↑ 3 ; follow-up: Changed 3 years ago by novoselt

Replying to mkoeppe:

Replying to novoselt:

As I have said before - ELLUL is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.

Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.

What value? In what concrete situation? In the code it does not simplify your work much since it is not a problem to do enter-leave-update with a snapshot at necessary places. For interactive work, as I have pointed out, it does not make sense for revised dictionaries, because it is impossible to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current ELLUL even for regular dictionaries to cease discussions about it once and for all.

Note also that the new implementation of run_simplex_method does not rely on it. This makes it possible to use generic method for dictionaries, cuts length of formulas in half (useful both for not wasting paper and for speedy response in browsers), and contains just as much information as before.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 3 years ago by mkoeppe

Replying to novoselt:

Replying to mkoeppe:

Replying to novoselt:

As I have said before - ELLUL is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.

Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.

What value? In what concrete situation? In the code it does not simplify your work much since it is not a problem to do enter-leave-update with a snapshot at necessary places. For interactive work, as I have pointed out, it does not make sense for revised dictionaries, because it is impossible to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current ELLUL even for regular dictionaries to cease discussions about it once and for all.

Note also that the new implementation of run_simplex_method does not rely on it. This makes it possible to use generic method for dictionaries, cuts length of formulas in half (useful both for not wasting paper and for speedy response in browsers), and contains just as much information as before.

I retract my comment. I think your current design is very nice. We can work with it for the cutting plane method. 'll rebase our cutting plane work on top of this branch.

I agree that deprecating ELLUL would be a good idea, as it is specific to the primal tableau simplex.

Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.

comment:13 Changed 3 years ago by git

  • Commit changed from 63fa3857f40d5944786ec69840c34eccc24a0e44 to 586d0fa61bc4dcb946558a16358d90e737d4960f

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

586d0faNo guess in _preupdate_output, deprecate ELLUL, infeasibility message.

comment:14 in reply to: ↑ 12 Changed 3 years ago by novoselt

Replying to mkoeppe:

Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.

I thought about it, but for some reason didn't want to. As I can no longer remember the reason, I've changed it to an argument.

Deprecated ELLUL.

Changed the message for infeasible problems to indicate the problematic constraint/variable, mirroring "unbounded in x5 direction".

comment:15 Changed 3 years ago by pjxiao

  • Authors changed from Peijun Xiao to Andrey Novoseltsev
  • Owner changed from (none) to pjxiao
  • Reviewers set to pjxiao

comment:16 Changed 3 years ago by pjxiao

  • Status changed from new to needs_review

comment:17 Changed 3 years ago by pjxiao

  • Status changed from needs_review to positive_review

comment:18 Changed 3 years ago by novoselt

  • Status changed from positive_review to needs_work
  • Work issues set to PR350 to SageNB

Do not merge this until SageNB shipped with Sage supports it!

comment:19 Changed 3 years ago by novoselt

  • Dependencies set to #19616
  • Status changed from needs_work to positive_review
  • Work issues PR350 to SageNB deleted

comment:20 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-6.9 to sage-6.11
  • Status changed from positive_review to needs_info

Reviewer name please...

comment:21 Changed 3 years ago by mkoeppe

  • Reviewers changed from pjxiao to Peijun Xiao
  • Status changed from needs_info to positive_review

comment:22 Changed 3 years ago by vbraun

  • Branch changed from u/novoselt/dual_simplex_method to 586d0fa61bc4dcb946558a16358d90e737d4960f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.