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