Add didactical implementation of tableau cutting planes to interactive_simplex_method

[mkoeppe]

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?

Depends on #18742
Depends on #19097
Depends on #20500

CC: @novoselt @yuan-zhou @uduse @pgxiao

Component: numerical

Work Issues: doc format

Author: Peijun Xiao

Branch/Commit: u/pjxiao/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method @ e7765c2

Reviewer: Andrey Novoseltsev

Issue created by migration from https://trac.sagemath.org/ticket/18805

[novoselt]

comment:1

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.

[mkoeppe]

comment:2

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

[mkoeppe]

Author: Peijun Xiao

[mkoeppe]

Dependencies: #18742

[mkoeppe]

Branch: u/mkoeppe/add_didactical_implementation_of_tableau_cutting_planes_to_interactive_simplex_method

[mkoeppe]

Commit: 933fb3d

[mkoeppe]

comment:4

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

[novoselt]

Work Issues: doc format

[novoselt]

comment:5

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.

[novoselt]

Reviewer: Andrey Novoseltsev

[pgxiao]

Changed branch 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

[pgxiao]

Changed commit from 933fb3d to 54cc5d1

[pgxiao]

comment:7

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 |

[novoselt]

comment:8

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.

[novoselt]

comment:9

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

[novoselt]

comment:10

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

[novoselt]

comment:11

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

[novoselt]

comment:12

As a possibility to consider - derive new classes like

class InteractiveMILPProblem(InteractiveLPProblem):
   ...

that will concentrate just on Gomory's cuts.

[mkoeppe]

comment:13

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?)

[novoselt]

comment:27

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.

[sagetrac-git]

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

4fb12b9

Cutting planes

[sagetrac-git]

Changed commit from 9e079d4 to 4fb12b9

[sagetrac-git]

Changed commit from 4fb12b9 to c20992e

[sagetrac-git]

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

c20992e

Cutting planes

[mkoeppe]

comment:30

rebased on top of 7.2.beta3

[sagetrac-git]

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

54341de

Cutting planes

[sagetrac-git]

Changed commit from c20992e to 54341de

[novoselt]

comment:32

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.

[mkoeppe]

comment:33

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.

[mkoeppe]

Changed dependencies from #18742, #19097 to #18742, #19097, #20500

[sagetrac-git]

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

d6ee048	Refactor leaving_coefficients in terms of new method row_coefficients
3e61a49	Cutting planes

[sagetrac-git]

Changed commit from 54341de to 3e61a49

[mkoeppe]

comment:36

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

[pgxiao]

Changed commit from 3e61a49 to 2f96807

[pgxiao]

New commits:

2f96807

Add add_constraint to LPProblemStandardForm

[pgxiao]

Changed branch 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

[sagetrac-git]

Changed commit from 2f96807 to 8740578

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 8740578 to e7765c2

[sagetrac-git]

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

[mkoeppe]

comment:40

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

[mkoeppe]

comment:41

Development of this, based on pjxiao's Aug 24, 2016 version from https://github.com/pgxiao/sage.git, is now taking place at https://github.com/mkoeppe/sage-numerical-interactive-mip

The present ticket should be closed.