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.DODECAHEDRON_3D_LP = <gilp.simplex.LP object>¶: A 3D LP with feasible region in the shape of a regular dodecahedron.

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.Infeasible¶

Bases: Exception

Raised when an LP is found to have no feasible solution.

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, equality: bool = False)¶

Bases: object

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

The LP class maintains the coefficents of a linear program in either standard equality or inequality form. A is an m*n matrix describing the linear combination of variables making up the LHS of each constraint. b is a 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. The n decision variables are all nonnegative.

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

n¶

number of decision variables.

Type:	int

m¶

number of constraints (excluding nonnegativity constraints).

Type:	int

A¶

An m*n matrix of coefficients.

Type:	np.ndarray

b¶

A vector of coefficients of length m.

Type:	np.ndarray

c¶

A vector of coefficients of length n.

Type:	np.ndarray

equality¶

True iff the LP is in standard equality form.

Type:	bool

get_basic_feasible_sol(B: List[int], feas_tol: float = 1e-07) → 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. These constraints must be satisfied to a tolerance of feas_tol (which is set to 1e-7 by default).

Parameters:	B (List[int]) – A list of indices in {0..n+m-1} forming a basis. feas_tol (float) – Primal feasibility tolerance (1e-7 by default).
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]: 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_coefficients()¶: Returns n,m,A,b,c describing this LP.

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.branch_and_bound(lp: gilp.simplex.LP, feas_tol: float = 1e-07, int_feas_tol: float = 1e-07) → Tuple[numpy.ndarray, float]¶

Execute branch and bound on the given LP.

Execute branch and bound on the given LP assuming that all decision variables must be integer. Use a primal feasibility tolerance of feas_tol (with default vlaue of 1e-7) and an integer feasibility tolerance of int_feas_tol (with default vlaue of 1e-7).

Parameters:

lp (LP) – LP on which to run simplex
feas_tol (float) – Primal feasibility tolerance (1e-7 default).
int_feas_tol (float) – Integer feasibility tolerance (1e-7 default).

Returns:

np.ndarray: An optimal all integer solution.
float: The optimal value subject to integrality constraints.

Return type:

Tuple

gilp.simplex.equality_form(lp: gilp.simplex.LP) → gilp.simplex.LP¶

Return the LP in standard equality form.

Transform the LP (if needed) into an equivalent LP in standard equality form. Furthermore, ensure that every element of b is nonnegative. The transformation can be summariazed as follows.

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

Parameters:	lp (LP) – An LP in either standard inequality or equality form.
Returns:	The corresponding standard equality form LP
Return type:	LP

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.phase_one(lp: gilp.simplex.LP, feas_tol: float = 1e-07) → Tuple[numpy.ndarray, List[int]]¶

Execute Phase I of the simplex method.

Execute Phase I of the simplex method to find an inital basic feasible solution to the given LP. Return a basic feasible solution if one exists. Otherwise, raise the Infeasible exception.

Parameters:	lp (LP) – LP on which phase I of the simplex method will be done. feas_tol (float) – Primal feasibility tolerance (1e-7 default).
Returns:	np.ndarray: An initial basic feasible solution. List[int]: Corresponding basis to the initial BFS.
Return type:	Tuple
Raises:	`Infeasible` – The LP is found to not have a feasible solution.

gilp.simplex.simplex(lp: gilp.simplex.LP, pivot_rule: str = 'bland', initial_solution: numpy.ndarray = None, iteration_limit: int = None, feas_tol: float = 1e-07) → 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. Use a primal feasibility tolerance of feas_tol (with default vlaue of 1e-7).

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. feas_tol (float) – Primal feasibility tolerance (1e-7 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` – 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', feas_tol: float = 1e-07) → 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. Use a primal feasibility tolerance of feas_tol (with default vlaue of 1e-7). 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. feas_tol (float) – Primal feasibility tolerance (1e-7 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(A: numpy.ndarray, b: float, domain: List[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.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.polygon(x_list: List[numpy.ndarray], style: str, ordered: bool = False, lb: str = None) → Union[plotly.graph_objs._scatter.Scatter, plotly.graph_objs._scatter3d.Scatter3d]¶: 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
Raises:	`ValueError` – The LP must be in standard inequality form.

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

Raises:	`ValueError` – The LP must be in standard inequality form.

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. `ValueError` – The LP must be in standard inequality form.

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
Raises:	`ValueError` – The LP must be in standard inequality form.