Tutorial

First, open up a Jupyter Notebook or Google Colab enviroment. Reminder: if you are using a Google Colab enviroment, you will have to reinstall gilp every time by running the cell !pip install gilp.

Example LPs

GILP comes with many LP examples. Before we use them, we must import them.

from gilp import examples as ex

We can now access the LP examples using ex.NAME where NAME is the name of the example LP. For example, consider:

\[\begin{split}\begin{align*} \text{maximize} \quad & 5x_1 + 3x_2\\ \text{subject to} \quad & 2x_1 + 1x_2 \leq 20 \\ & 1x_1 + 1x_2 \leq 16 \\ & 1x_1 + 0x_2 \leq 7 \\ & x_1, x_2 \geq 0 \end{align*}\end{split}\]

This example LP is called ALL_INTEGER_2D_LP. Let us assign this LP to a variable called lp.

lp = ex.ALL_INTEGER_2D_LP

Now, we can begin visualizing LPs. We import the visualization function below.

from gilp.visualize import simplex_visual

The function simplex_visual() takes an LP and 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')

Here is the resulting visualization from running simplex_visual(lp).show()

The resulting visualization has the following components.

• Plot:

  On the left, a plot shows the feasible region of the LP shaded in blue. You can hover over the corner points to see the feasible solution, dictionary, and objective value asscociated with that point.

• Constraints:

  In the middle, there is a list of constraints (not including the nonnegativity constraints). You can click on a constraint to mute it and click again to bring it back.

• Dictionary Form LP:

  The dictionary form for the current iteration of simplex is shown in the top right. If the slider is between iterations, the dictionary form for both the previous and next iteration are shown.

• Sliders:

  The iteration slider allows you to toggle through iterations of simplex. You can see the path of simplex on the plot and the updating corresponding dictionary LPs. The objective slider allows you to see the isoprofit line or plane for various objective values.

Defining LPs

We can also create our own LPs! First, we must import the LP class.

from gilp.simplex import LP

The LP class creates linear programs from their standard inequality form. We can represent a standard inequality form LP in terms of three matrices.

\[\begin{split}\begin{align*} \text{maximize} \quad & c^Tx\\ \text{subject to} \quad & Ax \leq b \\ & x \geq 0 \end{align*}\end{split}\]

For example, consider the following LP in standard inequality form.

\[\begin{split}\begin{align*} \text{maximize} \quad & 1x_1 + 2x_2\\ \text{subject to} \quad & 0x_1 + 1x_2 \leq 4 \\ & 1x_1 - 1x_2 \leq 2 \\ & 1x_1 + 0x_2 \leq 3 \\ & -2x_1 + 1x_2 \leq 0 \\ & x \geq 0 \end{align*}\end{split}\]

In this example, we have \(A = \begin{bmatrix} 0 & 1 \\ 1 & -1 \\ 1 & 0 \\ -2 & 1\end{bmatrix}\), \(b = \begin{bmatrix} 4 \\ 2 \\ 3 \\ 0 \end{bmatrix}\), and \(c = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\). Note \(x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\)

We will use these three matrices to create an instance of LP. First, we will import NumPy to create the matrices.

import numpy as np

Now, using NumPy, we create the matrices and create the LP instance.

from gilp.simplex import LP

A = np.array([[0, 1],
              [1, -1],
              [1, 0],
              [-2, 1]])
b = np.array([[4],
              [2],
              [3],
              [0]])
c = np.array([[1],
              [2]])
# Alternatively
b = np.array([4,2,3,0])
c = np.array([1,2])

lp = LP(A,b,c)

Now, we can visualize it like before!

simplex_visual(lp).show()