engri-1101/gilp

A Python package for visualizing the geometry of linear programs.

gilp's Issues

ENH: Max-out-in pivot rule

There are several Simplex pivot rules, and GILP only implements a select few. One pivot rule that is yet to be implemented is max-in-out. I recommend reading the paper to learn more. The majority of pivot rule logic currently lives within the _simplex_iteration function here. You will need to add max-out-in to the list of available pivot rules here. It could also be helpful to refactor the code to decouple pivot rule logic and/or add an example using this pivot rule to the documentation.

branch and bound visualization

Hi,
the visualization of branch and bound is not work.
In my case, gilp.bnb_visual(lp) returns list, such as
[Figure({
'data': [{'type': 'scatter', 'visible': False, 'x': [9.1], 'y': [20.8]},
{'hoverinfo': 'none',
'line': {'color': 'black', 'width': 1},
'mode': 'lines',
'showlegend': False,
'type': 'scatter',
'x': [],...
...
]
Is there a solution?

ENH: Generalizing the branch and bound implementation

Hi, I wanted to visualize LPs and the simplex algorithm and discovered this package. It has been great so far so thanks for that.

I'd like to use it for MILPs as well, but I noticed that the provided branch and bound implementation assumes all decision variables are integers. It seems to me that the branch_and_bound_iteration and branch_and_bound functions could naively be extended, by having a mask to indicate which indices are integers. I hacked an implementation quickly and with very limited testing it seems to work fine, but I have two questions:

1. What is happening in this if statement? I only have a high-level understanding of the algorithm so this may be silly/simple, but it is not clear to me why a new variable is added.
2. The visualization code seems somewhat separate than the code in simplex.py and I wasn't immediately sure if a similar hack is feasible there. Do you have any thoughts?

ENH: Interior-point method visualization

It would be great to include visualizations of interior-point methods. I am not aware of any previous groundwork. This would involve both implementing the algorithm and building off of the existing graphic module to create the visualization function. I expect the vector function will be particularly useful.

ENH: Cutting plane visualization

The example below was manually created using an older version of gilp to visualize cutting planes for ENGRI-1101 (see here). It would be great to implement Gomory Cuts to automatically generate cutting planes and an associated visualization function!

Note: the implementation to visualize feasible points is already implemented here.

ENH: Shiny app

The Shiny platform was recommended to me as a potential way to allow others to create custom visualizations on a website. If anyone is interested in trying to set this up, I'd be curious to hear what is involved!

ENH: Support showing "dictionaries" for higher dimensions

Hello, I appreciate that it is not possible to visualise LP problems in more than three dimensions. However, as your program is capable of solving LP problems in higher dimensions, I was wondering, for completeness, whether it is possible to show the "dictionaries", along with the slider for "Iteration" for higher dimensions (without, of course, the plots!), instead of just giving an error message. Even without the plots, it will then be possible to view the evolution of the dictionaries over the iterations. It seems like a small adjustment to the program, but I do not know it well enough to attempt it! Thanks.

ENH: Visualize dual LPs

Currently, GILP functionality only focuses on the primal LP. However, GILP could be used to visualize both the primal and dual LP, to demonstrate complementary slackness. The primal and dual LPs have the following forms:

(primal) max c^Tx          (dual) min b^Ty
         s.t A x <= b             s.t A^T y >= c
               x >= 0                     y >= 0

Since GILP can only visualize 2- and 3-dimensional LPs, dual LP visualizations will be limited to LPs in 2 or 3 variables with 2 or 3 constraints.

This is a non-trivial change requiring an understanding of LP duality and multiple design decisions. Learn more about duality here.

ENH: More textbook examples

LP examples from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (commonly referred to as CLRS) have been built in to gilp (see here). It would be great to add more LP examples from common textbooks.