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
- Border, “The Gauss–Jordan and Simplex Algorithms” 2004.
-
quantecon.optimize.linprog_simplex.
nt
¶
-
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.