linprog_simplex
Contain linprog_simplex, a Numba-jitted linear programming solver based on the Simplex Method.
The formulation of linear program linprog_simplex assumes is:
maximize:
c @ x
subject to:
A_ub @ x <= b_ub
A_eq @ x == b_eq
x >= 0
Examples
A problem inequality constraints:
\[\begin{split}\max_{x_0, x_1, x_2, x_3}\ \ & 2x_0 + 4x_1 + x_2 + x_3 \\ \mbox{such that}\ \ & 2x_0 + x_1 \leq 3, \\ & x_1 + 4x_2 + x_3 \leq 3, \\ & x_0 + 3x_1 + x_3 \leq 4, \\ & x_0, x_1, x_2, x_3 \geq 0.\end{split}\]Solve this problem with linprog_simplex:
>>> c = np.array([2, 4, 1, 1]) >>> A_ub = np.array([[2, 1, 0, 0], [0, 1, 4, 1], [1, 3, 0, 1]]) >>> b_ub = np.array([3, 3, 4]) >>> res = linprog_simplex(c, A_ub=A_ub, b_ub=b_ub)
The solution found:
>>> res.x array([1. , 1. , 0.5, 0. ])
The optimal value:
>>> res.fun 6.5
linprog_simplex solves the dual problem, too. The dual solution found:
>>> res.lambd array([0.45, 0.25, 1.1 ])
A problem equality constraints:
\[\begin{split}\max_{x_0, x_1, x_2, x_3}\ \ & 2x_0 - 3x_1 + x_2 + x_3 \\ \mbox{such that}\ \ & x_0 + 2x_1 + x_2 + x_3 = 3, \\ & x_0 - 2x_1 + 2x_2 + x_3 = -2, \\ & 3x_0 - x_1 - x_3 = -1, \\ & x_0, x_1, x_2, x_3 \geq 0.\end{split}\]Solve this problem with linprog_simplex:
>>> c = np.array([2, -3, 1, 1]) >>> A_eq = np.array([[1, 2, 1, 1], [1, -2, 2, 1], [3, -1, 0, -1]]) >>> b_eq = np.array([3, -2, -1]) >>> res = linprog_simplex(c, A_eq=A_eq, b_eq=b_eq)
The solution found:
>>> res.x array([0.1875, 1.25 , 0. , 0.3125])
The optimal value:
>>> res.fun -3.0625
The dual solution:
>>> res.lambd array([-0.0625, 1.3125, 0.25 ])
Consider the following minimization problem (an example from the documentation for scipy.optimize.linprog):
\[\begin{split}\min_{x_0, x_1}\ \ & -x_0 + 4x_1 \\ \mbox{such that}\ \ & -3x_0 + x_1 \leq 6, \\ & -x_0 - 2x_1 \geq -4, \\ & x_1 \geq -3.\end{split}\]The problem is not represented in the form accepted by linprog_simplex. Transforming the variables by \(x_0 = z_0 - z_1\) and \(x_1 + 3 = z_2\), and multiply the objective function by \(-1\), we thus solve the following equivalent maximization problem:
\[\begin{split}\max_{z_0, z_1, z_2}\ \ & z_0 + z_1 - 4z_2 \\ \mbox{such that}\ \ & -3z_0 -3z_1 + z_2 \leq 9, \\ & z_0 + z_1 + 2z_2 \leq -2, \\ & z_0, z_1, z_2 \geq 0.\end{split}\]Solve the latter problem with linprog_simplex:
>>> c = np.array([1, 1, -4]) >>> A = np.array([[-3, -3, 1], [1, 1, 2]]) >>> b = np.array([9, 10]) >>> res = linprog_simplex(c, A_ub=A, b_ub=b)
The optimal value of the original problem:
>>> -(res.fun + 12) # -(z_0 + z_1 - 4 (z_2 - 3)) -22.0
And the solution found:
>>> res.x[0] - res.x[1], res.x[2] - 3 # (z_0 - z_1, z_2 - 3) (10.0, -3.0)
- class quantecon.optimize.linprog_simplex.PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13)
Bases:
tuplenamedtuple 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:
tuplenamedtuple 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)[source]
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)[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:
- 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 appears to be unbounded
- num_iterint
The number of iterations performed.
References
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))[source]
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))[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:
- 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.