README.md

GILP (Geometric Interpretation of Linear Programs) is a Python package for visualizing the geometry of:

• Linear Programs (LPs)
• The Simplex Algorithm
• The Branch and Bound Algorithm

LPs can be constructed from NumPy arrays and many examples (such as the Klee-Minty cube) are included. The revised simplex method is implemented along with phase I for finding an initial feasible solution. The package relies on Plotly to generate standalone HTML files which can be viewed in a Jupyter Notebook inline or in a web browser.

GILP was developed at Cornell University alongside a course with roughly 100 students. GILP: An Interactive Tool for Visualizing the Simplex Algorithm describes the development and usage of the tool, and reports feedback from its use in the course.

Examples

Installation

The quickest way to get started is with a pip install.

pip install gilp

Development

To develop and run tests on gilp, first download the source code in the desired directory.

git clone https://github.com/engri-1101/gilp.git

Next, cd into the gilp directory and create a Python virtual enviroment.

cd gilp
python -m venv env_name

Activate the virtual enviroment.

source env_name/bin/activate

Run the following in the virtual enviroment. The -e flag lets you make adjustments to the source code and see changes without re-installing. The [dev] installs necessary dependencies for developing and testing.

pip install -e .[dev]

To run tests and see coverage, run the following in the virtual enviroment.

coverage run -m pytest
coverage report --include=gilp/*

Usage

The LP class creates linear programs from (3) NumPy arrays: A, b, and c which define the LP in standard inequality form.

For example, consider the following LP:

The LP instance is created as follows.

import gilp
import numpy as np
from gilp.simplex import LP
A = np.array([[2, 1],
              [1, 1],
              [1, 0]])
b = np.array([[20],
              [16],
              [7]])
c = np.array([[5],
              [3]])
lp = LP(A,b,c)

After creating an LP, one can run simplex and generate a visualization with

from gilp.visualize import simplex_visual
simplex_visual(lp)

where simplex_visual() returns a plotly figure. The figure can then be viewed on a Jupyter Notebook inline using

simplex_visual(lp).show()

If .show() is run outside a Jupyter Notebook enviroment, the visualization will open up in the browser. Alternatively, the HTML file can be written and then opened.

simplex_visual(lp).write_html('name.html')

Below is the visualization for the example LP. The plot on the left shows the feasible region and constraints of the LP. Hovering over an extreme point shows the basic feasible solution, basis, and objective value. The iteration slider allows one to toggle through the iterations of simplex and see the updating tableaus. The objective slider lets one see the objective line or plane for some range of objective values.

Cite

If you find this tool useful, please cite our conference paper!

@inproceedings{robbins2023gilp,
  title = {GILP: An Interactive Tool for Visualizing the Simplex Algorithm},
  booktitle = {Proceedings of the 54th ACM Technical Symposium on Computer Science Education V. 1},
  author = {Robbins, Henry W. and Gutekunst, Samuel C. and Shmoys, David B. and Williamson, David P.},
  year = {2023},
  series = {SIGCSE 2023},
  pages = {108--114},
  publisher = {Association for Computing Machinery},
  doi = {10.1145/3545945.3569815},
}

License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License