linprog_simplex

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

class quantecon.optimize.linprog_simplex.PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13)

Bases: tuple

namedtuple to hold tolerance values for pivoting.

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(x, lambd, fun, success, status, num_iter)

Bases: tuple

namedtuple containing the result from linprog_simplex.

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(tableau, basis, x, lambd, b_signs)

Fetch the optimal solution and value from an optimal tableau.

Parameters:

tableaundarray(float, ndim=2)

ndarray of shape (L+1, n+m+L+1) containing the optimal tableau, where L=m+k.

basisndarray(int, ndim=1)

ndarray of shape (L,) containing the optimal basis.

xndarray(float, ndim=1)

Empty ndarray of shape (n,) to store the primal solution. Modified in place.

lambdndarray(float, ndim=1)

Empty ndarray of shape (L,) to store the dual solution. Modified in place.

b_signsndarray(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:

funfloat

The optimal value.

quantecon.optimize.linprog_simplex.linprog_simplex(c, A_ub=array([], shape=(0, 0), dtype=float64), b_ub=array([], dtype=float64), A_eq=array([], shape=(0, 0), dtype=float64), b_eq=array([], dtype=float64), max_iter=1000000, piv_options=PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13), tableau=None, basis=None, x=None, lambd=None)

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:

cndarray(float, ndim=1)

ndarray of shape (n,).

A_ubndarray(float, ndim=2), optional

ndarray of shape (m, n).

b_ubndarray(float, ndim=1), optional

ndarray of shape (m,).

A_eqndarray(float, ndim=2), optional

ndarray of shape (k, n).

b_eqndarray(float, ndim=1), optional

ndarray of shape (k,).

max_iterint, optional(default=10**6)

Maximum number of iteration to perform.

piv_optionsPivOptions, optional

PivOptions namedtuple to set the following tolerance values:

fea_tolfloat

Feasibility tolerance (default=1e-06).

tol_pivfloat

Pivot tolerance (default=1e-07).

tol_ratio_difffloat

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

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

basisndarray(int, ndim=1), optional

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

xndarray(float, ndim=1), optional

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

lambdndarray(float, ndim=1), optional

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

Returns:

resSimplexResult

namedtuple consisting of the fields:

xndarray(float, ndim=1)

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

lambdndarray(float, ndim=1)

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

funfloat

Value of the objective function.

successbool

True if the algorithm succeeded in finding an optimal solution.

statusint

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_iterint

The number of iterations performed.

References

• 11. 3. Border, “The Gauss–Jordan and Simplex Algorithms” 2004.

quantecon.optimize.linprog_simplex.solve_phase_1(tableau, basis, max_iter=1000000, piv_options=PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13))

Perform the simplex algorithm for Phase 1 on a given tableau in canonical form, by calling solve_tableau with skip_aux=False.

Parameters:

See `solve_tableau`.

Returns:

See solve_tableau.

quantecon.optimize.linprog_simplex.solve_tableau(tableau, basis, max_iter=1000000, skip_aux=True, piv_options=PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13))

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:

tableaundarray(float, ndim=2)

ndarray of shape (L+1, n+m+L+1) containing the tableau. Modified in place.

basisndarray(int, ndim=1)

ndarray of shape (L,) containing the basic variables. Modified in place.

max_iterint, optional(default=10**6)

Maximum number of pivoting steps.

skip_auxbool, optional(default=True)

Whether to skip the coefficients of the auxiliary (or artificial) variables in pivot column selection.

piv_optionsPivOptions, optional

PivOptions namedtuple to set the tolerance values.

Returns:

successbool

True if the algorithm succeeded in finding an optimal solution.

statusint

An integer representing the exit status of the optimization.

num_iterint

The number of iterations performed.