linprog_simplex¶

Contain a Numba-jitted linear programming solver based on the Simplex Method.

class quantecon.optimize.linprog_simplex.PivOptions¶

Bases: tuple

namedtuple to hold tolerance values for pivoting

Attributes:	fea_tol tol_piv tol_ratio_diff

Methods

`count`(value, /)	Return number of occurrences of value.
`index`(value[, start, stop])	Return first index of value.

fea_tol¶

tol_piv¶

tol_ratio_diff¶

class quantecon.optimize.linprog_simplex.SimplexResult¶

Bases: tuple

namedtuple containing the result from linprog_simplex.

Attributes:	fun lambd num_iter status success x

Methods

`count`(value, /)	Return number of occurrences of value.
`index`(value[, start, stop])	Return first index of value.

fun¶

lambd¶

num_iter¶

status¶

success¶

x¶

quantecon.optimize.linprog_simplex.get_solution[source]¶

Fetch the optimal solution and value from an optimal tableau.

Parameters:

tableau : ndarray(float, ndim=2): ndarray of shape (L+1, n+m+L+1) containing the optimal tableau, where L=m+k.
basis : ndarray(int, ndim=1): ndarray of shape (L,) containing the optimal basis.
x : ndarray(float, ndim=1): Empty ndarray of shape (n,) to store the primal solution. Modified in place.
lambd : ndarray(float, ndim=1): Empty ndarray of shape (L,) to store the dual solution. Modified in place.
b_signs : ndarray(bool, ndim=1): ndarray of shape (L,) whose i-th element is True iff the i-th element of the vector (b_ub, b_eq) is positive.

Returns:

fun : float: The optimal value.

quantecon.optimize.linprog_simplex.linprog_simplex[source]¶

Solve a linear program in the following form by the simplex algorithm (with the lexicographic pivoting rule):

maximize:

c @ x

subject to:

A_ub @ x <= b_ub
A_eq @ x == b_eq
       x >= 0

Parameters:

c : ndarray(float, ndim=1)

ndarray of shape (n,).

A_ub : ndarray(float, ndim=2), optional

ndarray of shape (m, n).

b_ub : ndarray(float, ndim=1), optional

ndarray of shape (m,).

A_eq : ndarray(float, ndim=2), optional

ndarray of shape (k, n).

b_eq : ndarray(float, ndim=1), optional

ndarray of shape (k,).

max_iter : int, optional(default=10**6)

Maximum number of iteration to perform.

piv_options : PivOptions, optional

PivOptions namedtuple to set the following tolerance values:

fea_tol : float

Feasibility tolerance (default=1e-06).

tol_piv : float

Pivot tolerance (default=1e-07).

tol_ratio_diff : float

Tolerance used in the the lexicographic pivoting (default=1e-13).

tableau : ndarray(float, ndim=2), optional

Temporary ndarray of shape (L+1, n+m+L+1) to store the tableau, where L=m+k. Modified in place.

basis : ndarray(int, ndim=1), optional

Temporary ndarray of shape (L,) to store the basic variables. Modified in place.

x : ndarray(float, ndim=1), optional

Output ndarray of shape (n,) to store the primal solution.

lambd : ndarray(float, ndim=1), optional

Output ndarray of shape (L,) to store the dual solution.

Returns:

res : SimplexResult

namedtuple consisting of the fields:

x : ndarray(float, ndim=1)

ndarray of shape (n,) containing the primal solution.

lambd : ndarray(float, ndim=1)

ndarray of shape (L,) containing the dual solution.

fun : float

Value of the objective function.

success : bool

True if the algorithm succeeded in finding an optimal solution.

status : int
An integer representing the exit status of the optimization:
0 : Optimization terminated successfully
1 : Iteration limit reached
2 : Problem appears to be infeasible
3 : Problem apperas to be unbounded
num_iter : int

The number of iterations performed.

References

1. 1. Border, “The Gauss–Jordan and Simplex Algorithms” 2004.

quantecon.optimize.linprog_simplex.nt¶: alias of quantecon.optimize.linprog_simplex.PivOptions

quantecon.optimize.linprog_simplex.solve_tableau[source]¶

Perform the simplex algorithm on a given tableau in canonical form.

Used to solve a linear program in the following form:

maximize:

c @ x

subject to:

A_ub @ x <= b_ub
A_eq @ x == b_eq
       x >= 0

where A_ub is of shape (m, n) and A_eq is of shape (k, n). Thus, tableau is of shape (L+1, n+m+L+1), where L=m+k, and

tableau[np.arange(L), :][:, basis] must be an identity matrix, and
the elements of tableau[:-1, -1] must be nonnegative.

Parameters:

tableau : ndarray(float, ndim=2): ndarray of shape (L+1, n+m+L+1) containing the tableau. Modified in place.
basis : ndarray(int, ndim=1): ndarray of shape (L,) containing the basic variables. Modified in place.
max_iter : int, optional(default=10**6): Maximum number of pivoting steps.
skip_aux : bool, optional(default=True): Whether to skip the coefficients of the auxiliary (or artificial) variables in pivot column selection.
piv_options : PivOptions, optional: PivOptions namedtuple to set the tolerance values.

Returns:

success : bool: True if the algorithm succeeded in finding an optimal solution.
status : int: An integer representing the exit status of the optimization.
num_iter : int: The number of iterations performed.