linprog(method=’simplex’)¶
- scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='simplex', callback=None, options={'maxiter': 5000, 'disp': False, 'presolve': True, 'tol': 1e-12, 'autoscale': False, 'rr': True, 'bland': False}, x0=None)
Linear programming: minimize a linear objective function subject to linear equality and inequality constraints using the tableau-based simplex method.
Linear programming solves problems of the following form:
\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]where \(x\) is a vector of decision variables; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\), and \(u\) are vectors; and \(A_{ub}\) and \(A_{eq}\) are matrices.
Alternatively, that’s:
minimize:
c @ x
such that:
A_ub @ x <= b_ub A_eq @ x == b_eq lb <= x <= ub
Note that by default
lb = 0
andub = None
unless specified withbounds
.- Parameters
- c1-D array
The coefficients of the linear objective function to be minimized.
- A_ub2-D array, optional
The inequality constraint matrix. Each row of
A_ub
specifies the coefficients of a linear inequality constraint onx
.- b_ub1-D array, optional
The inequality constraint vector. Each element represents an upper bound on the corresponding value of
A_ub @ x
.- A_eq2-D array, optional
The equality constraint matrix. Each row of
A_eq
specifies the coefficients of a linear equality constraint onx
.- b_eq1-D array, optional
The equality constraint vector. Each element of
A_eq @ x
must equal the corresponding element ofb_eq
.- boundssequence, optional
A sequence of
(min, max)
pairs for each element inx
, defining the minimum and maximum values of that decision variable. UseNone
to indicate that there is no bound. By default, bounds are(0, None)
(all decision variables are non-negative). If a single tuple(min, max)
is provided, thenmin
andmax
will serve as bounds for all decision variables.- methodstr
This is the method-specific documentation for ‘simplex’. ‘highs’, ‘highs-ds’, ‘highs-ipm’, ‘interior-point’ (default), and ‘revised simplex’ are also available.
- callbackcallable, optional
Callback function to be executed once per iteration.
- Returns
- resOptimizeResult
A
scipy.optimize.OptimizeResult
consisting of the fields:- x1-D array
The values of the decision variables that minimizes the objective function while satisfying the constraints.
- funfloat
The optimal value of the objective function
c @ x
.- slack1-D array
The (nominally positive) values of the slack variables,
b_ub - A_ub @ x
.- con1-D array
The (nominally zero) residuals of the equality constraints,
b_eq - A_eq @ x
.- successbool
True
when the algorithm succeeds in finding an optimal solution.- statusint
An integer representing the exit status of the algorithm.
0
: Optimization terminated successfully.1
: Iteration limit reached.2
: Problem appears to be infeasible.3
: Problem appears to be unbounded.4
: Numerical difficulties encountered.- messagestr
A string descriptor of the exit status of the algorithm.
- nitint
The total number of iterations performed in all phases.
See also
For documentation for the rest of the parameters, see
scipy.optimize.linprog
- Options
- maxiterint (default: 5000)
The maximum number of iterations to perform in either phase.
- dispbool (default: False)
Set to
True
if indicators of optimization status are to be printed to the console each iteration.- presolvebool (default: True)
Presolve attempts to identify trivial infeasibilities, identify trivial unboundedness, and simplify the problem before sending it to the main solver. It is generally recommended to keep the default setting
True
; set toFalse
if presolve is to be disabled.- tolfloat (default: 1e-12)
The tolerance which determines when a solution is “close enough” to zero in Phase 1 to be considered a basic feasible solution or close enough to positive to serve as an optimal solution.
- autoscalebool (default: False)
Set to
True
to automatically perform equilibration. Consider using this option if the numerical values in the constraints are separated by several orders of magnitude.- rrbool (default: True)
Set to
False
to disable automatic redundancy removal.- blandbool
If True, use Bland’s anti-cycling rule [3] to choose pivots to prevent cycling. If False, choose pivots which should lead to a converged solution more quickly. The latter method is subject to cycling (non-convergence) in rare instances.
- unknown_optionsdict
Optional arguments not used by this particular solver. If unknown_options is non-empty a warning is issued listing all unused options.
References
- 1
Dantzig, George B., Linear programming and extensions. Rand Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963
- 2
Hillier, S.H. and Lieberman, G.J. (1995), “Introduction to Mathematical Programming”, McGraw-Hill, Chapter 4.
- 3
Bland, Robert G. New finite pivoting rules for the simplex method. Mathematics of Operations Research (2), 1977: pp. 103-107.