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:  sage6.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
comment:2 Changed 4 years ago by
 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
 Branch set to u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method
comment:4 Changed 4 years ago by
 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:
e127372  Add abstract methods to LPAbstractDictionary

cd8d38f  Refactor entering_coefficients in terms of method row_coefficients

412019d  move ELLUL to LPAbstractDictionary

b345b85  New: run_dual_simplex_method

79c75d5  Prepare the names of slack variables in InteractiveLPProblem; new method all_variables

5d0c983  Add support for integer variables to InteractiveLPProblem, LPDictionary, etc.

92f47ec  Plotting for integer and mixed integer programs

50811b4  Add plot methods to LPDictionary, LPAbstractDictionary

fa6c699  Add add_row methods to LPDictionary, LPAbstractDictionary

933fb3d  Implement Gomory fractional and Gomory mixed integer cutting plane methods

comment:5 Changed 4 years ago by
 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#documentationstrings 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 oneline 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
 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
 Commit changed from 933fb3dae2ddc08760f67d98fe21435d3a66364c to 54cc5d123338bed43b1c97930c15ed1b9407c218
 Status changed from needs_work to needs_review
comment:8 Changed 4 years ago by
 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 twoelement 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 oneline 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
+ 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
+ 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 hardcoded 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
+ 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 followup: ↓ 25 Changed 4 years ago by
As a possibility to consider  derive new classes like
class InteractiveMILPProblem(InteractiveLPProblem): ...
that will concentrate just on Gomory's cuts.
comment:13 followup: ↓ 15 Changed 4 years ago by
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?)
comment:14 Changed 4 years ago by
 Commit changed from 54cc5d123338bed43b1c97930c15ed1b9407c218 to 43b3e4e4bf660765d7108d92eee60797dd88e903
Branch pushed to git repo; I updated commit sha1. New commits:
43b3e4e  revise form_thin_long_triangle

comment:15 in reply to: ↑ 13 Changed 4 years ago by
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
 Dependencies changed from #18742 to #18742, #19097
comment:17 Changed 4 years ago by
 Commit changed from 43b3e4e4bf660765d7108d92eee60797dd88e903 to e74a79ac89843f08e7d5c057929730be91daa044
comment:18 Changed 4 years ago by
 Commit changed from e74a79ac89843f08e7d5c057929730be91daa044 to af86d5704f137f54f5eee8a2d0d7be32a772626b
Branch pushed to git repo; I updated commit sha1. New commits:
af86d57  fix issue with assigning integer slack variables

comment:19 Changed 4 years ago by
 Commit changed from af86d5704f137f54f5eee8a2d0d7be32a772626b to c35454aa788652aacfba3d447f0a6832eaa85ada
Branch pushed to git repo; I updated commit sha1. New commits:
c35454a  remove slack variables in InteractiveLPProblem

comment:20 Changed 4 years ago by
 Commit changed from c35454aa788652aacfba3d447f0a6832eaa85ada to 63d32e4c49919c63e2914f8615741e80024b54a4
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
355401d  Add add_row methods to LPDictionary, LPAbstractDictionary

3ba9706  Implement Gomory fractional and Gomory mixed integer cutting plane methods

774c55c  revise docstrings according to formatting styles

4d75662  solve doctrines issues

89479ea  revise form_thin_long_triangle

eaf252d  raise errors for dual or standard form methods if variables are integer

181720b  use Vanderbei style patch to name slack variables

2a4e2c5  implement ELLUL for LPRevisedDictionary, revise run_revised_simplex_method

1ab0591  fix issue with assigning integer slack variables

63d32e4  remove slack variables in InteractiveLPProblem

comment:21 Changed 4 years ago by
 Commit changed from 63d32e4c49919c63e2914f8615741e80024b54a4 to d48010d6c3268981b61ce80ce6a3db937b70874e
comment:22 Changed 4 years ago by
 Commit changed from d48010d6c3268981b61ce80ce6a3db937b70874e to 271a16ef256fd89ffccb430747df68adcc613e6c
comment:23 Changed 4 years ago by
 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
 Commit changed from 271a16ef256fd89ffccb430747df68adcc613e6c to 9e079d4bf46cad3d9d60bf1fed8864200b361f4d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7383d67  Refactor run_simplex_method to dictionaries and LP problems.

dc70260  Add run_dual_simplex_method to dictionaries.

63fa385  Fix handling of unbounded/infeasible problems and add tests.

9e079d4  Cutting planes

comment:25 in reply to: ↑ 12 ; followup: ↓ 26 Changed 4 years ago by
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
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
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
 Commit changed from 9e079d4bf46cad3d9d60bf1fed8864200b361f4d to 4fb12b99e8f1f38a96f85105420ab23ff2d37fa6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4fb12b9  Cutting planes

comment:29 Changed 4 years ago by
 Commit changed from 4fb12b99e8f1f38a96f85105420ab23ff2d37fa6 to c20992eca84bbb1569246d32157a313a2c4bbd19
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c20992e  Cutting planes

comment:30 Changed 4 years ago by
rebased on top of 7.2.beta3
comment:31 Changed 4 years ago by
 Commit changed from c20992eca84bbb1569246d32157a313a2c4bbd19 to 54341de4d37ef6e1c0def5dfaf6d3e1f527d30b7
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
54341de  Cutting planes

comment:32 Changed 4 years ago by
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
Nothing much going on. The main author is busy with classes. I'm rebasing occasionally to keep it uptodate 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
 Dependencies changed from #18742, #19097 to #18742, #19097, #20500
comment:35 Changed 4 years ago by
 Commit changed from 54341de4d37ef6e1c0def5dfaf6d3e1f527d30b7 to 3e61a4915c7219b42732c6545d4fff9e6d575971
comment:36 Changed 4 years ago by
Rebased on top of #20500; it seems to work again.
comment:37 Changed 4 years ago by
 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:
2f96807  Add add_constraint to LPProblemStandardForm

comment:38 Changed 4 years ago by
 Commit changed from 2f968072f4353789e7627bc4c19e3464de679d03 to 8740578f6e0dd6483bd42a19ec7730fb53e80bcb
Branch pushed to git repo; I updated commit sha1. New commits:
76be7c7  Add doc tests to add_constrait to InteractiveLPProblemStardardForm

575906e  Implement add_constraint to InteractiveLPProblem

ffd9f89  Revise add_row in LPDictionary to return a dictionary without changing the original dictionary

ee5e230  Revise add_row in LPRevisedDictionary without changing the original problem

8740578  Clean up the file after making changes to add_row

comment:39 Changed 4 years ago by
 Commit changed from 8740578f6e0dd6483bd42a19ec7730fb53e80bcb to e7765c223feb791331c71bc12ead07d42cbaef2b
Branch pushed to git repo; I updated commit sha1. New commits:
da15f84  In dictionary(), add integer_variables as parameter in LPDictionary constructor

3318caa  Fix integer_slack default value in add_row()

bb306c2  Revise add_row in LPRevisedDictionary so it works with dictionaries in any status (optimal or not)

e7765c2  Revise add_row in LPDictionary, so it works with dictionaries with continuous, integer or mixed integer variables

comment:40 Changed 4 years ago by
A part of this is now split out as #20559. Will rebase on top of that later.
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.