gilp package¶

gilp.examples module¶

gilp.examples.ALL_INTEGER_2D_LP = <gilp.simplex.LP object>¶: A 2D LP where all basic feasible solutions are integral and have integral tableaus.

gilp.examples.ALL_INTEGER_3D_LP = <gilp.simplex.LP object>¶: A 3D LP where all basic feasible solutions are integral and have integral tableaus.

gilp.examples.DEGENERATE_FIN_2D_LP = <gilp.simplex.LP object>¶: A 2D LP where the (default) intial feasible solution is degenerate.

gilp.examples.KLEE_MINTY_2D_LP = <gilp.simplex.LP object>¶: A 2D LP where the ‘dantzig’ pivot rule results in a simplex path through every bfs. Klee, Victor; Minty, George J. (1972). “How good is the simplex algorithm?”

gilp.examples.KLEE_MINTY_3D_LP = <gilp.simplex.LP object>¶: A 3D LP where the ‘dantzig’ pivot rule results in a simplex path through every bfs. Klee, Victor; Minty, George J. (1972). “How good is the simplex algorithm?”

gilp.examples.LIMITING_CONSTRAINT_2D_LP = <gilp.simplex.LP object>¶: A 2D LP demonstrating how the most limiting constraint determines the leaving variable.

gilp.examples.MULTIPLE_OPTIMAL_3D_LP = <gilp.simplex.LP object>¶: A 3D LP demonstrating the geometry of multiple optimal solutions.

gilp.examples.SQUARE_PYRAMID_3D_LP = <gilp.simplex.LP object>¶: A 3D LP which is highly degenerate. It demonstrates that degeneracy can not be solved by removing a seemingly redundant constraint–doing so can alter the feasible region.

gilp.simplex module¶

exception gilp.simplex.InfeasibleBasicSolution¶

Bases: Exception

Raised when a list of indices forms a valid basis but the corresponding basic solution is infeasible.

exception gilp.simplex.InvalidBasis¶

Bases: Exception

Raised when a list of indices does not form a valid basis and prevents further correct execution of the function.

class gilp.simplex.LP(A: numpy.ndarray, b: numpy.ndarray, c: numpy.ndarray)¶

Bases: object

Maintains the coefficents and size of a linear program (LP).

The LP class maintains the coefficents of a linear program in both standard inequality and equality form. A is an m*n matrix describing the linear combination of variables making up the LHS of each constraint. b is a nonnegative vector of length m making up the RHS of each constraint. Lastly, c is a vector of length n describing the objective function to be maximized. Both the n decision variables and m slack variables must be nonnegative. Under these assumptions, the LP must be feasible.

inequality        equality
max c^Tx          max c^Tx
s.t Ax <= b       s.t Ax + Is == b
    x >= 0               x,s >= 0

n¶

number of decision variables (excluding slack variables).

Type:	int

m¶

number of constraints (excluding nonnegativity constraints).

Type:	int

A¶

An m*n matrix of coefficients.

Type:	np.ndarray

A_I¶

An m*(n+m) matrix of coefficients: [A I].

Type:	np.ndarray

b¶

A nonnegative vector of coefficients of length m.

Type:	np.ndarray

c¶

A vector of coefficients of length n.

Type:	np.ndarray

c_0¶

A vector of coefficients of length n+m: [c^T 0^T]^T.

Type:	np.ndarray

get_basic_feasible_sol(B: List[int]) → numpy.ndarray¶

Return the basic feasible solution corresponding to this basis.

By definition, B is a basis iff A_B is invertible (where A is the matrix of coefficents in standard equality form). The corresponding basic solution x satisfies A_Bx = b. By definition, x is a basic feasible solution iff x satisfies both A_Bx = b and x > 0.

Parameters:	B (List[int]) – A list of indices in {0..n+m-1} forming a basis.
Returns:	Basic feasible solution corresponding to the basis B.
Return type:	np.ndarray
Raises:	`InvalidBasis` – B `InfeasibleBasicSolution` – x_B

get_basic_feasible_solns() → Tuple[List[numpy.ndarray], List[List[int]], List[float]]¶

Return all basic feasible solutions, their basis, and objective value.

Returns:	List[np.ndarray]: The list of basic feasible solutions for this LP. List[List[int]]: The corresponding list of bases. List[float]: The corresponding list of objective values.
Return type:	Tuple

get_equality_form()¶: Returns n,m,A_I,b,c_0 describing this LP in standard equality form

get_inequality_form()¶: Returns n,m,A,b,c describing this LP in standard inequality form.

get_tableau(B: List[int]) → numpy.ndarray¶

Return the tableau corresponding to the basis B for this LP.

The returned tableau has the following form:

z - (c_N^T - y^TA_N)x_N = y^Tb  where   y^T = c_B^TA_B^(-1)
x_B + A_B^(-1)A_Nx_N = x_B^*    where   x_B^* = A_B^(-1)b

Parameters:	B (List[int]) – A valid basis for this LP
Returns:	A numpy array representing the tableau
Return type:	np.ndarray
Raises:	`InvalidBasis` – Invalid basis. A_B is not invertible.

exception gilp.simplex.UnboundedLinearProgram¶

Bases: Exception

Raised when an LP is found to be unbounded during an execution of the revised simplex method

gilp.simplex.invertible(A: numpy.ndarray) → bool¶

Return true if the matrix A is invertible.

By definition, a matrix A is invertible iff n = m and A has rank n

Parameters:	A (np.ndarray) – An m*n matrix
Returns:	True if the matrix A is invertible. False otherwise.
Return type:	bool

gilp.simplex.simplex(lp: gilp.simplex.LP, pivot_rule: str = 'bland', initial_solution: numpy.ndarray = None, iteration_limit: int = None) → Tuple[List[numpy.ndarray], List[List[int]], float, bool]¶

Execute the revised simplex method on the given LP.

Execute the revised simplex method on the given LP using the specified pivot rule. If a valid initial basic feasible solution is given, use it as the initial bfs. Otherwise, ignore it. If an iteration limit is given, terminate if the specified limit is reached. Output the current solution and indicate the solution may not be optimal.

PIVOT RULES

Entering variable:

‘bland’ or ‘min_index’: minimum index

‘dantzig’ or ‘max_reduced_cost’: most positive reduced cost

‘greatest_ascent’: most positive (minimum ratio) x (reduced cost)

‘manual_select’: user selects among possible entering indices

Leaving variable:

(All): minimum (positive) ratio (minimum index to tie break)

Parameters:	lp (LP) – LP on which to run simplex pivot_rule (str) – Pivot rule to be used. ‘bland’ by default. initial_solution (np.ndarray) – Initial bfs. None by default. iteration_limit (int) – Simplex iteration limit. None by default.
Returns:	List[np.ndarray]: Basic feasible solutions at each simplex iteration. List[List[int]]: Corresponding bases at each simplex iteration. float: The current objective value. bool: True if the current objective value is known to be optimal.
Return type:	Tuple
Raises:	`ValueError` – Invalid pivot rule. Select from (list). `ValueError` – Iteration limit must be strictly positive. `ValueError` – initial_solution should have shape (n,1) but was ().

gilp.simplex.simplex_iteration(lp: gilp.simplex.LP, x: numpy.ndarray, B: List[int], pivot_rule: str = 'bland') → Tuple[numpy.ndarray, List[int], float, bool]¶

Execute a single iteration of the revised simplex method.

Let x be the initial basic feasible solution with corresponding basis B. Do one iteration of the revised simplex method using the given pivot rule. Implemented pivot rules include:

Entering variable:

‘bland’ or ‘min_index’: minimum index

‘dantzig’ or ‘max_reduced_cost’: most positive reduced cost

‘greatest_ascent’: most positive (minimum ratio) x (reduced cost)

‘manual_select’: user selects among possible entering indices

Leaving variable:

(All): minimum (positive) ratio (minimum index to tie break)

Parameters:	lp (LP) – LP on which the simplex iteration is being done. x (np.ndarray) – Initial basic feasible solution. B (List(int)) – Basis corresponding to basic feasible solution x. pivot_rule (str) – Pivot rule to be used. ‘bland’ by default.
Returns:	np.ndarray: New basic feasible solution. List[int]: Basis corresponding to the new basic feasible solution. float: Objective value of the new basic feasible solution. bool: An idication of optimality. True if optimal. False otherwise.
Return type:	Tuple
Raises:	`ValueError` – Invalid pivot rule. Select from (list). `ValueError` – x should have shape (n+m,1) but was ().

gilp.style module¶

gilp.style.BACKGROUND_COLOR = 'white'¶: The background color of the figure

gilp.style.FIG_HEIGHT = 500¶: The height of the entire visualization figure.

gilp.style.FIG_WIDTH = 950¶: The width of the entire visualization figure.

gilp.style.LEGEND_NORMALIZED_X_COORD = 0.39473684210526316¶: The normalized x coordinate of the legend (relative to right side).

gilp.style.LEGEND_WIDTH = 200¶: The width of the legend section of the figure.

gilp.style.TABLEAU_NORMALIZED_X_COORD = 0.6052631578947368¶: The normalized x coordinate of the tableau (relative to right side).

gilp.style.equation(fig: plotly.graph_objs._figure.Figure, A: numpy.ndarray, b: float, style: str, lb: str = None) → Union[plotly.graph_objs._scatter.Scatter, plotly.graph_objs._scatter3d.Scatter3d]¶: Return a styled 2d or 3d trace representing the given equation.

gilp.style.equation_string(A: numpy.ndarray, b: float, comp: str = ' ≤ ') → str¶

Return the string representation of an equation.

The equation is assumed to be in standard form: Ax ‘comp’ b.

gilp.style.format(num: Union[int, float], precision: int = 3) → str¶: Return a properly formated string for a number at some precision.

gilp.style.get_axis_limits(fig: plotly.graph_objs._figure.Figure, n: int) → List[float]¶: Return the axis limits for the given figure.

gilp.style.intersection(A: numpy.ndarray, b: float, D: numpy.ndarray, e: float) → List[numpy.ndarray]¶: Return the points where Ax = b intersects Dx <= e.

gilp.style.label(dic: Dict[str, Union[float, list]]) → str¶: Return a styled string representation of the given dictionary.

gilp.style.line(x_list: List[numpy.ndarray], style: str, lb: str = None, i=[0]) → plotly.graph_objs._scatter.Scatter¶: Return a 2d line trace in the desired style.

gilp.style.linear_string(A: numpy.ndarray, indices: List[int], constant: float = None) → str¶: Return the string representation of a linear combination.

gilp.style.order(x_list: List[numpy.ndarray]) → List[List[float]]¶: Return an ordered list of points for drawing a 2d or 3d polygon.

gilp.style.polygon(x_list: List[numpy.ndarray], style: str, lb: str = None) → plotly.graph_objs._scatter.Scatter¶: Return a styled 2d or 3d polygon trace defined by some points.

gilp.style.scatter(x_list: List[numpy.ndarray], style: str, lbs: List[str] = None) → plotly.graph_objs._scatter.Scatter¶: Return a styled 2d or 3d scatter trace for given points and labels.

gilp.style.set_axis_limits(fig: plotly.graph_objs._figure.Figure, x_list: List[numpy.ndarray])¶

Set the axes limits of fig such that all points in x are visible.

Given a set of nonnegative 2 or 3 dimensional points, set the axes limits such all points are visible within the plot window.

gilp.style.table(header: List[str], content: List[str], style: str) → plotly.graph_objs._table.Table¶: Return a styled table trace with given headers and content.

gilp.style.vector(tail: numpy.ndarray, head: numpy.ndarray) → Union[plotly.graph_objs._scatter.Scatter, plotly.graph_objs._scatter3d.Scatter3d]¶: Return a styled 2d or 3d vector trace from tail to head.

gilp.visualize module¶

gilp.visualize.ISOPROFIT_STEPS = 25¶: The number of isoprofit lines or plane to render.

gilp.visualize.ITERATION_STEPS = 2¶: The number of steps each iteration is divided in to.

exception gilp.visualize.InfiniteFeasibleRegion¶

Bases: Exception

Raised when an LP is found to have an infinite feasible region and can not be accurately displayed.

gilp.visualize.add_isoprofits(fig: plotly.graph_objs._figure.Figure, lp: gilp.simplex.LP) → Tuple[List[int], List[float]]¶

Add the set of isoprofit lines/planes which can be toggled over.

Parameters:

fig (plt.Figure) – Figure to which isoprofits lines/planes are added
lp (LP) – LP for which the isoprofit lines are being generated

Returns:

List[int]: Indices of all isoprofit lines/planes
List[float]): The corresponding objective values

Return type:

Tuple

gilp.visualize.add_path(fig: plotly.graph_objs._figure.Figure, path: List[numpy.ndarray]) → List[int]¶: Add vectors for visualizing the simplex path. Return vector indices.

gilp.visualize.add_tableaus(fig: plotly.graph_objs._figure.Figure, lp: gilp.simplex.LP, bases: List[int], tableau_form: str = 'dictionary') → List[int]¶: Add the set of tableaus. Return the indices of each table trace.

gilp.visualize.get_tableau_strings(lp: gilp.simplex.LP, B: List[int], iteration: int, form: str) → Tuple[List[str], List[str]]¶

Get the string representation of the tableau for the LP and basis B.

The tableau can be in canonical or dictionary form:

Canonical:                                 Dictionary:
---------------------------------------    (i)
| (i) z | x_1 | x_2 | ... | x_n | RHS |
=======================================    max          ... + x_N
|   1   |  -  |  -  | ... |  -  |  -  |    s.t.   x_i = ... + x_N
|   0   |  -  |  -  | ... |  -  |  -  |           x_j = ... + x_N
              ...                                      ...
|   0   |  -  |  -  | ... |  -  |  -  |           x_k = ... + x_N
---------------------------------------

gilp.visualize.isoprofit_slider(isoprofit_IDs: List[int], objectives: List[float], fig: plotly.graph_objs._figure.Figure, n: int) → plotly.graph_objs.layout._slider.Slider¶

Create a plotly slider to toggle between isoprofit lines / planes.

Parameters:	isoprofit_IDs (List[int]) – IDs of every isoprofit trace. objectives (List[float]) – Objective values for every isoprofit trace. fig (plt.Figure) – The figure containing the isoprofit traces. n (int) – The dimension of the LP the figure visualizes.
Returns:	A plotly slider that can be added to a figure.
Return type:	plt.layout.SLider

gilp.visualize.iteration_slider(path_IDs: List[int], table_IDs: List[int], fig: plotly.graph_objs._figure.Figure, n: int) → plotly.graph_objs.layout._slider.Slider¶

Create a plotly slider to toggle between iterations of simplex

Parameters:	path_IDs (List[int]) – IDs of every simplex path trace. table_IDs (List[int]) – IDs of every table trace. fig (plt.Figure) – The figure containing the traces. n (int) – The dimension of the LP the figure visualizes.
Returns:	A plotly slider that can be added to a figure.
Return type:	plt.layout.Slider

gilp.visualize.lp_visual(lp: gilp.simplex.LP) → plotly.graph_objs._figure.Figure¶: Render a plotly figure visualizing the geometry of an LP.

gilp.visualize.plot_lp(lp: gilp.simplex.LP) → plotly.graph_objs._figure.Figure¶

Return a figure visualizing the feasible region of the given LP.

Assumes the LP has 2 or 3 decision variables. Each axis corresponds to a single decision variable. The visualization plots each basic feasible solution (with their basis and objective value), the feasible region, and each of the constraints.

Parameters:	lp (LP) – An LP to visualize.
Returns:	A figure containing the visualization.
Return type:	fig (plt.Figure)
Raises:	`InfiniteFeasibleRegion` – Can not visualize. `ValueError` – Can only visualize 2 or 3 dimensional LPs.

gilp.visualize.set_up_figure(n: int) → plotly.graph_objs._figure.Figure¶: Return a figure for an n dimensional LP visualization.

gilp.visualize.simplex_visual(lp: gilp.simplex.LP, tableau_form: str = 'dictionary', rule: str = 'bland', initial_solution: numpy.ndarray = None, iteration_limit: int = None) → plotly.graph_objs._figure.Figure¶

Render a figure showing the geometry of simplex.

Parameters:	lp (LP) – LP on which to run simplex tableau_form (str) – Displayed tableau form. Default is ‘dictionary’ rule (str) – Pivot rule to be used. Default is ‘bland’ initial_solution (np.ndarray) – An initial solution. Default is None. iteration_limit (int) – A limit on simplex iterations. Default is None.
Returns:	A plotly figure which shows the geometry of simplex.
Return type:	plt.Figure