gilp package

gilp.simplex module

Linear and integer program solver.

This module defines an LP class. LPs can be solved through an implementation of phase I and the revised simplex method. Furthermore, integer solutions can be obtained through an implementation of the branch and bound algorithm.

gilp.simplex.BFS: alias of bfs

class gilp.simplex.LP(A: Union[ndarray, List, Tuple], b: Union[ndarray, List, Tuple], c: Union[ndarray, List, Tuple], equality: bool = False)[source]

Bases: object

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

The LP class maintains the coefficents of a linear program. If initialized in standard inequality form, both standard equality and inequality form are maintained. Otherwise, only standard equality form is maintained. Hence, if equality is True, the attributes A, b, and c are None.

inequality        equality
max c^Tx          max c_eq^Tx
s.t A x <= b      s.t A_eq x == b_eq
      x >= 0               x >= 0

n

Number of decision variables (excluding slack variables).

Type: int

m

Number of constraints (excluding nonnegativity constraints).

Type: int

A

LHS coefficients of LP in standard inequality form.

Type: np.ndarray

A_eq

LHS coefficients of LP in standard equality form.

Type: np.ndarray

b

RHS coefficients of LP in standard inequality form.

Type: np.ndarray

b_eq

RHS coefficients of LP in standard equality form.

Type: np.ndarray

c

Objective function coefficents for inequality form.

Type: np.ndarray

c_eq

Objective function coefficents for equality form.

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) → bfs[source]

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

BFS

Raises

InvalidBasis – B
InfeasibleBasicSolution – x_B

get_basic_feasible_solns() → List[bfs][source]

Return all the basic feasible solutions.

Returns: List of basic feasible solutions.
Return type: List[BFS]

get_coefficients(equality: bool = True)[source]

Returns the coefficents describing this LP.

If equality is True (defaults to True), then return standard equality coefficents. Otherwise, return standard inequality coefficents. Also returns the dimensions of m*n matrix A.

get_tableau(B: List[int]) → ndarray[source]

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.

get_vertices() → ndarray[source]

Return the vertices of this inequality LP’s feasible region.

Returns: Vertices of the LP’s feasible region.
Return type: np.ndarray
Raises: ValueError – The LP must be in standard inequality form.

gilp.simplex.branch_and_bound(lp: LP, manual: bool = False, feas_tol: float = 1e-07, int_feas_tol: float = 1e-07) → Tuple[ndarray, float][source]

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 the branch and bound algorithm.
manual (bool) – True if the user can choose the variable to branch on.
feas_tol (float) – Primal feasibility tolerance (1e-7 default).
int_feas_tol (float) – Integer feasibility tolerance (1e-7 default).

Returns

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

Return type

Tuple

gilp.simplex.simplex(lp: LP, pivot_rule: str = 'bland', initial_solution: Optional[Union[ndarray, List, Tuple]] = None, iteration_limit: Optional[int] = None, feas_tol: float = 1e-07) → Tuple[ndarray, List[int], float, bool, List[bfs]][source]

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’ or ‘manual_select’: user selects possible entering index

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 (Union[np.ndarray, List, Tuple]) – Initial bfs.
iteration_limit (int) – Simplex iteration limit. None by default.
feas_tol (float) – Primal feasibility tolerance (1e-7 default).

Returns

x (np.ndarray): Current basic feasible solution.
B (List[int]): Corresponding bases of the current best BFS.
obj_val (float): The current objective value.
optimal (bool): True if x is optimal. False otherwise.
path (List[BFS]): Path of simplex.

Return type

Tuple

Raises

ValueError – Iteration limit must be strictly positive.
ValueError – initial_solution should have shape (n,1) but was ().

gilp.visualize module

Functions to visualize the simplex and branch and bound algorithms.

This moodule uses a custom implementation of the resvised simplex method and the branch and bound algorithm (simplex module) to create and solve LPs. Using the graphic module (which provides a high-level interface with the plotly visualization package) and computational geometry functions from the geometry module, visualizations of these algorithms are then created to be viewed inline on a Jupyter Notebook or written to a static HTML file.

gilp.visualize.bnb_visual(lp: LP, manual: bool = False, feas_tol: float = 1e-07, int_feas_tol: float = 1e-07) → List[Figure][source]

Render figures visualizing the geometry of branch and bound.

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 the branch and bound algorithm.
manual (bool) – True if the user can choose the variable to branch on.
feas_tol (float) – Primal feasibility tolerance (1e-7 default).
int_feas_tol (float) – Integer feasibility tolerance (1e-7 default).

Returns

A list of figures visualizing the branch and bound.

Return type

List[Figure]

gilp.visualize.lp_visual(lp: LP, basic_sol: bool = True, show_basis: bool = True) → Figure[source]

Render a figure visualizing the geometry of an LP’s feasible region.

Parameters

lp (LP) – LP whose feasible region is visualized.
basic_sol (bool) – True if the entire BFS is shown. Default to True.
show_basis (bool) – True if the basis is shown within the BFS label.

Returns

A plotly figure showing the geometry of feasible region.

Return type

plt.Figure

Raises

ValueError – The LP must be in standard inequality form.

gilp.visualize.simplex_visual(lp: LP, basic_sol: bool = True, show_basis: bool = True, lp_form: str = 'dictionary', rule: str = 'bland', initial_solution: Optional[ndarray] = None, iteration_limit: Optional[int] = None, feas_tol: float = 1e-07) → Figure[source]

Render a figure visualizing the geometry of simplex on the given LP.

Uses the given simplex parameters: rule, initial_solution, iteration_limit, and feas_tol. See more about these parameters using help(simplex).

Parameters

lp (LP) – LP on which to run simplex.
basic_sol (bool) – True if the entire BFS is shown. Default to True.
show_basis (bool) – True if the basis is shown within the BFS label.
lp_form (str) – Displayed lp form: {“dictionary”, “tableau”}
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.
feas_tol (float) – Primal feasibility tolerance (1e-7 default).

Returns

A plotly figure which shows the geometry of simplex.

Return type

plt.Figure

Raises

ValueError – The LP must be in standard inequality form.

gilp.examples module

Linear program examples.

This module contains a handful of linear program examples that have various properties ranging from all integer basic feasible solutions to degeneracy.

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.CLRS_DEGENERATE_3D_LP = <gilp.simplex.LP object>: A 3D LP used to explain the phenomenon of degeneracy in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. See “Termination” in Section 29.3.

gilp.examples.CLRS_INTEGER_2D_LP = <gilp.simplex.LP object>: A 2D LP to motivate fundamental LP concepts and introduce the graphical method for solving 2-dimensional LPs. See Equations (29.11-29.15) in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.

gilp.examples.CLRS_SIMPLEX_EX_3D_LP = <gilp.simplex.LP object>: A 3D LP used as an extended example of the Simplex algorithm in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. See Equations (29.53-29.57).

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.EVERY_FATHOM_2D_IP = <gilp.simplex.LP object>: A 2D IP that encounters every possible fathom in branch and bound.

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.examples.STANDARD_2D_IP = <gilp.simplex.LP object>: The standard 2D IP example used in the ENGRI 1101 course notes.

gilp.examples.VARIED_BRANCHING_3D_IP = <gilp.simplex.LP object>: A 3D IP where the number of branch and bound nodes depends heavily on which index is chosen to branch on at every iteration.