Opened 4 years ago

Last modified 4 years ago

#18805 needs_work enhancement

Add didactical implementation of tableau cutting planes to interactive_simplex_method

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-6.8
Component: numerical Keywords:
Cc: novoselt, yzh, zwang, pjxiao Merged in:
Authors: Peijun Xiao Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues: doc format
Branch: u/pjxiao/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method (Commits) Commit: e7765c223feb791331c71bc12ead07d42cbaef2b
Dependencies: #18742, #19097, #20500 Stopgaps:

Description

We are working on a didactical implementation of the cutting plane method using tableau cutting planes, such as Gomory's fractional cut and Gomory's mixed integer cut.

This would work with InteractiveLP, LPAbstractDictionary, etc. (Via #18804, one could run the cutting plane method also on a backend tableau.)

To work correctly with mixed integer problems, one would need to remember which variables are real and which are integer.

Would it be acceptable to add a slot such as ._integer_variables (a set), and a corresponding accessor .integer_variables() to the various classes of interactive_simplex_method?

Change History (40)

comment:1 Changed 4 years ago by novoselt

I think this would be great, but the interface should be very clean not to scare students ;-) Various checks and methods like optimal_solution should of course then be modified to take integrality into consideration.

comment:2 Changed 4 years ago by mkoeppe

  • Authors set to Peijun Xiao
  • Dependencies set to #18742

We now have an implementation of the Gomory fractional and Gomory mixed integer cutting plane methods.

This is on top of an old version of #18742, and we'll later of course rebase it on top of the final version of it. But comments on the general design would already be very welcome at this point:

https://github.com/pgxiao/sage/blob/Peggy/src/sage/numerical/interactive_simplex_method.py

comment:3 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method

comment:4 Changed 4 years ago by mkoeppe

  • Commit set to 933fb3dae2ddc08760f67d98fe21435d3a66364c
  • Status changed from new to needs_review

It is now rebased on top of current 'develop'.

Needs review.


Last 10 new commits:

e127372Add abstract methods to LPAbstractDictionary
cd8d38fRefactor entering_coefficients in terms of method row_coefficients
412019dmove ELLUL to LPAbstractDictionary
b345b85New: run_dual_simplex_method
79c75d5Prepare the names of slack variables in InteractiveLPProblem; new method all_variables
5d0c983Add support for integer variables to InteractiveLPProblem, LPDictionary, etc.
92f47ecPlotting for integer and mixed integer programs
50811b4Add plot methods to LPDictionary, LPAbstractDictionary
fa6c699Add add_row methods to LPDictionary, LPAbstractDictionary
933fb3dImplement Gomory fractional and Gomory mixed integer cutting plane methods

comment:5 Changed 4 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to needs_work
  • Work issues set to doc format

I hope to take a closer look during upcoming Sage Days, but some picks at formatting for now, http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings has a long example docsctring:

  • there should be empty lines between arguments
  • there should be no empty lines (especially multiple ones) in the very beginning and the very end
  • references to other methods should be marked with :meth:, :func:, :class: as appropriate
  • the very first line should be a one-line description and if at all possible it should take only one line
  • mathematics should be in single back quotes and use of LaTeX is encouraged
  • there should be empty lines after :: and before the test blocks
  • there should be :: before EVERY test block

While some of these things are convention/taste/style, others are just plain necessary for documentation and testing frameworks to work. As you can see from the patchbot result, the current version does not build.

comment:6 Changed 4 years ago by pjxiao

  • Branch changed from u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method to u/pjxiao/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method

comment:7 Changed 4 years ago by pjxiao

  • Commit changed from 933fb3dae2ddc08760f67d98fe21435d3a66364c to 54cc5d123338bed43b1c97930c15ed1b9407c218
  • Status changed from needs_work to needs_review

Thanks a lot for taking a look and for your comments. 

I have revised the docstrings. The current version is supposed to build successfully. New commits:

54cc5d1 solve doctrines issues
2e16304 revise docstrings according to formatting styles

comment:8 Changed 4 years ago by novoselt

  • Status changed from needs_review to needs_work

The very first change with all the commits::

+def form_thin_long_triangle(k):
+    r"""
+
+    Generate a thin long triangle with vertices (0, 0), (1, 0), and (1/2, k)
+    for some given integer K, and return the triangle in Ax<=b form.
+    This thin long triangle is an example of a system with large Chvatal rank.
+
+    INPUT:
+    -``k``-- an integer indicating the y coordinate of the top vertex for the triangle
+
+    OUTPUT:
+    -``A`` -- a two by two matrix
+    -``b`` -- a two-element vector
+
+    EXAMPLES::
+        sage: from sage.numerical.interactive_simplex_method \
+        ....:     import form_thin_long_triangle
+        sage: A, b, = form_thin_long_triangle(4)
+        sage: A, b
+        (([-8, 1], [8, 1]), (0, 8))
+
+    """
+    A = ([Integer(-2 * k), Integer(1)], [Integer(2 * k), Integer(1)])
+    b = (Integer(0), Integer(2 * k))
+    type(b[0])
+    return A, b
  • empty line in the beginning of the docstring
  • no one-line description in the beginning
  • math should be written as LaTeX
  • INPUT/OUTPUT/EXAMPLES blocks lack empty lines
  • I do not understand the documentation - what does it mean to generate a triangle in the form Ax<=b?
  • the output does not match the documentation, A is not a matrix and b is not a vector
  • there is no need in Integer conversion (and its import)
  • type(...) does nothing useful
  • why would a user need such a function??? If it is for internal use, perhaps start with underscore.

comment:9 Changed 4 years ago by novoselt

+        Examples for the sufficient conditions for integer slack variables::
+
+            sage: P = InteractiveLPProblem(A, b, c)
+            sage: P.integer_variables()
+            set()
+            sage: P = InteractiveLPProblem(A, b, c, integer_variables=True)
+            sage: P.integer_variables()
+            {x1, x2, x3, x4}
+            sage: b1 = (11/10, 5)
+            sage: P = InteractiveLPProblem(A, b1, c, integer_variables=True)
+            sage: P.integer_variables()
+            {x1, x2, x4}
+            sage: A1 = ([1, 1], [3/10, 1])
+            sage: P = InteractiveLPProblem(A1, b1, c, integer_variables=True)
+            sage: P.integer_variables()
+            {x1, x2}
+
+        Allow the user to choose integer slack variables which may violate the sufficient conditions::
+
+            sage: P = InteractiveLPProblem(A, b, c, integer_variables={'x1', 'x2', 'x3'})
+            sage: P.integer_variables()
+            {x1, x2, x3}

I do not understand the comments here. These examples should demonstrate creation of problems and use of parameters, there was no talk about slack variables, sufficient conditions, and their violation.

comment:10 Changed 4 years ago by novoselt

+        slack_variables = ["{}{:d}".format("x", i)
+                               for i in range(n + 1, n + m + 1)]

After all the work for supporting different styles there are now slack variables hard-coded to be x in generic problems that did not use to even have slack variables?!

This is not going to work for such a huge patch. Can you please provide a detailed text overview of what exactly should be achieved by this ticket and the plan of how this will be done?

It would be great also to have an incremental set of tickets that add new functionality without affecting much existing code. Looking at the commit messages, I am quite puzzled by the move of ELLUL method to abstract dictionaries: I think it does not make sense for revised dictionaries and for the regular ones its implementation relies on knowledge of the latex representation of these regular dictionaries - so it does belong to the place where it originally was...

comment:11 Changed 4 years ago by novoselt

+            integer_variables=self.integer_variables())

Most definitely wrong while constructing either a dual problem or converting to standard form!!!

The current code was used by several hundred students for working on individual assignments (i.e. applied to quite different problems some of which exposed corner cases), so it is relatively bug free and easy to use/consistent. With major changes it may be a good idea to use it for your course, make tweaks that surface during the term, and then work on a patch for changing the standard module.

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

As a possibility to consider - derive new classes like

class InteractiveMILPProblem(InteractiveLPProblem):
   ...

that will concentrate just on Gomory's cuts.

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

Thanks for your initial comments.

The individual commits on this branch, if you read them in the right order (from oldest to newest -- the commit with the triangle testcase is the last commit before the commits that clean up docstrings), add features gradually and should be easy to review.

Making ELLUL available for both LPDictionary and LPRevisedDictionary is motivated by implementing run_dual_simplex_method as a dictionary method. I think this makes a lot of sense because each of the individual methods that ELLUL stands for are available for both dictionary types.

We need this as a subroutine for the cutting plane method. (Perhaps run_simplex_method and run_revised_simplex_method can and should be refactored as well and pushed down to become dictionary methods?)

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

comment:14 Changed 4 years ago by git

  • Commit changed from 54cc5d123338bed43b1c97930c15ed1b9407c218 to 43b3e4e4bf660765d7108d92eee60797dd88e903

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

43b3e4erevise form_thin_long_triangle

comment:15 in reply to: ↑ 13 Changed 4 years ago by mkoeppe

Replying to mkoeppe:

(Perhaps run_simplex_method and run_revised_simplex_method can and should be refactored as well and pushed down to become dictionary methods?)

We'll redo this ticket on top of #19097 that does the above and implements the dual simplex method. This is to make the present ticket smaller.

comment:16 Changed 4 years ago by mkoeppe

  • Dependencies changed from #18742 to #18742, #19097

comment:17 Changed 4 years ago by git

  • Commit changed from 43b3e4e4bf660765d7108d92eee60797dd88e903 to e74a79ac89843f08e7d5c057929730be91daa044

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

d6772a9raise errors for dual or standard form methods if variables are integer
fab7a39use Vanderbei style patch to name slack variables
e74a79aimplement ELLUL for LPRevisedDictionary, revise run_revised_simplex_method

comment:18 Changed 4 years ago by git

  • Commit changed from e74a79ac89843f08e7d5c057929730be91daa044 to af86d5704f137f54f5eee8a2d0d7be32a772626b

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

af86d57fix issue with assigning integer slack variables

comment:19 Changed 4 years ago by git

  • Commit changed from af86d5704f137f54f5eee8a2d0d7be32a772626b to c35454aa788652aacfba3d447f0a6832eaa85ada

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

c35454aremove slack variables in InteractiveLPProblem

comment:20 Changed 4 years ago by git

  • Commit changed from c35454aa788652aacfba3d447f0a6832eaa85ada to 63d32e4c49919c63e2914f8615741e80024b54a4

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

355401dAdd add_row methods to LPDictionary, LPAbstractDictionary
3ba9706Implement Gomory fractional and Gomory mixed integer cutting plane methods
774c55crevise docstrings according to formatting styles
4d75662solve doctrines issues
89479earevise form_thin_long_triangle
eaf252draise errors for dual or standard form methods if variables are integer
181720buse Vanderbei style patch to name slack variables
2a4e2c5implement ELLUL for LPRevisedDictionary, revise run_revised_simplex_method
1ab0591fix issue with assigning integer slack variables
63d32e4remove slack variables in InteractiveLPProblem

comment:21 Changed 4 years ago by git

  • Commit changed from 63d32e4c49919c63e2914f8615741e80024b54a4 to d48010d6c3268981b61ce80ce6a3db937b70874e

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

1d03448Revise methods related to integer variables
5d7203dRemove useless lines, add necessary comments, correct typo
d48010dWrap too long lines, correct style issues

comment:22 Changed 4 years ago by git

  • Commit changed from d48010d6c3268981b61ce80ce6a3db937b70874e to 271a16ef256fd89ffccb430747df68adcc613e6c

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

6cfe8caWrap too long lines, fix style issues
271a16ewrap too long times, fix style issues

comment:23 Changed 4 years ago by mkoeppe

  • Branch changed from u/pjxiao/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method to u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method

comment:24 Changed 4 years ago by git

  • Commit changed from 271a16ef256fd89ffccb430747df68adcc613e6c to 9e079d4bf46cad3d9d60bf1fed8864200b361f4d

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.
dc70260Add run_dual_simplex_method to dictionaries.
63fa385Fix handling of unbounded/infeasible problems and add tests.
9e079d4Cutting planes

comment:25 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by novoselt

I still think that this would be the ideal solution:

Replying to novoselt:

As a possibility to consider - derive new classes like

class InteractiveMILPProblem(InteractiveLPProblem):
   ...

that will concentrate just on Gomory's cuts.

It may even make sense to start a new file for that given that current simplex method implementation is almost 4.5k lines. And I am not an expert in terminology, but my understanding is that "simplex method" is for real variables while Gomory cuts is a way to use it repeatedly adjusting constraints to solve integer optimization problems, i.e. "it builds on simplex method". Apart from ease of reviewing, it may make sense didactically as those who study simplex method may want to look at the code as well, so it is good to keep it simpler/cleaner.

comment:26 in reply to: ↑ 25 Changed 4 years ago by mkoeppe

Replying to novoselt:

I still think that this would be the ideal solution:

Replying to novoselt:

As a possibility to consider - derive new classes like

class InteractiveMILPProblem(InteractiveLPProblem):
   ...

that will concentrate just on Gomory's cuts.

It may even make sense to start a new file for that given that current simplex method implementation is almost 4.5k lines. And I am not an expert in terminology, but my understanding is that "simplex method" is for real variables while Gomory cuts is a way to use it repeatedly adjusting constraints to solve integer optimization problems, i.e. "it builds on simplex method".

Yes.

Apart from ease of reviewing, it may make sense didactically as those who study simplex method may want to look at the code as well, so it is good to keep it simpler/cleaner.

Yes, we'll look into this. But a few things from this patch would still make sense to add to the existing classes:

1) Refactoring of the plot method 2) Refactoring leaving_coefficients through row_coefficients etc. 3) The add_row methods

We can make separate tickets for all of these -- let me know.

comment:27 Changed 4 years ago by novoselt

Separate tickets for separate problems are always better ;-)

The sensitivity analysis methods require some careful thinking for fitting in into existing framework where:

  • problems are thought to be immutable (and I think it is a good decision in line with how other stuff in Sage works), so adding/removing constraints to them should return a new problem with augmented matrices etc;
  • dictionaries are mutable, but are supposed to always represent the same problem;
  • regular dictionaries are standalone entities that are not aware of "the original problem", which makes sense since they carry all the information, while revised dictionaries do remember the problem, which also makes sense since they rely on its data for computing necessary stuff.

It probably makes sense to have something like problem.add_stuff(stuff_to_add, dictionary=None) which returns the new problem and, optionally given a dictionary for the old problem, also a related dictionary for the new problem.

comment:28 Changed 4 years ago by git

  • Commit changed from 9e079d4bf46cad3d9d60bf1fed8864200b361f4d to 4fb12b99e8f1f38a96f85105420ab23ff2d37fa6

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

4fb12b9Cutting planes

comment:29 Changed 4 years ago by git

  • Commit changed from 4fb12b99e8f1f38a96f85105420ab23ff2d37fa6 to c20992eca84bbb1569246d32157a313a2c4bbd19

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

c20992eCutting planes

comment:30 Changed 4 years ago by mkoeppe

rebased on top of 7.2.beta3

comment:31 Changed 4 years ago by git

  • Commit changed from c20992eca84bbb1569246d32157a313a2c4bbd19 to 54341de4d37ef6e1c0def5dfaf6d3e1f527d30b7

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

54341deCutting planes

comment:32 Changed 4 years ago by novoselt

So what exactly is going on here? I thought we have reached an agreement that it would be better to keep the simplex method stuff as is and have a separate class/module for dealing with integer variables via Gomory's cuts, changing problems and running simplex method repeatedly. As it stands now, this is a single huge commit changing a lot of code and injecting integer variables directly into InteractiveLPProblem.

comment:33 Changed 4 years ago by mkoeppe

Nothing much going on. The main author is busy with classes. I'm rebasing occasionally to keep it up-to-date with sage. The plan is to follow your suggestion and make it a separate set of classes.

But please take a look at #20500, split out (and cleaned up) from this huge patch.

comment:34 Changed 4 years ago by mkoeppe

  • Dependencies changed from #18742, #19097 to #18742, #19097, #20500

comment:35 Changed 4 years ago by git

  • Commit changed from 54341de4d37ef6e1c0def5dfaf6d3e1f527d30b7 to 3e61a4915c7219b42732c6545d4fff9e6d575971

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

d6ee048Refactor leaving_coefficients in terms of new method row_coefficients
3e61a49Cutting planes

comment:36 Changed 4 years ago by mkoeppe

Rebased on top of #20500; it seems to work again.

comment:37 Changed 4 years ago by pjxiao

  • Branch changed from u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method to u/pjxiao/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method
  • Commit changed from 3e61a4915c7219b42732c6545d4fff9e6d575971 to 2f968072f4353789e7627bc4c19e3464de679d03

New commits:

2f96807Add add_constraint to LPProblemStandardForm

comment:38 Changed 4 years ago by git

  • Commit changed from 2f968072f4353789e7627bc4c19e3464de679d03 to 8740578f6e0dd6483bd42a19ec7730fb53e80bcb

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

76be7c7Add doc tests to add_constrait to InteractiveLPProblemStardardForm
575906eImplement add_constraint to InteractiveLPProblem
ffd9f89Revise add_row in LPDictionary to return a dictionary without changing the original dictionary
ee5e230Revise add_row in LPRevisedDictionary without changing the original problem
8740578Clean up the file after making changes to add_row

comment:39 Changed 4 years ago by git

  • Commit changed from 8740578f6e0dd6483bd42a19ec7730fb53e80bcb to e7765c223feb791331c71bc12ead07d42cbaef2b

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

da15f84In dictionary(), add integer_variables as parameter in LPDictionary constructor
3318caaFix integer_slack default value in add_row()
bb306c2Revise add_row in LPRevisedDictionary so it works with dictionaries in any status (optimal or not)
e7765c2Revise add_row in LPDictionary, so it works with dictionaries with continuous, integer or mixed integer variables

comment:40 Changed 4 years ago by mkoeppe

A part of this is now split out as #20559. Will rebase on top of that later.

Note: See TracTickets for help on using tickets.