Skip to main content
`Ctrl`+`K`

# linprog(method=’simplex’)

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

  Linear programming: minimize a linear objective function subject to linear equality and inequality constraints using the tableau-based simplex method.

  Deprecated since version 1.9.0: method=’simplex’ will be removed in SciPy 1.11.0. It is replaced by method=’highs’ because the latter is faster and more robust.

  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` and `ub = None` unless specified with `bounds`.

  Parameters:
    c 1-D array

      The coefficients of the linear objective function to be minimized.

    A_ub 2-D array, optional

      The inequality constraint matrix. Each row of `A_ub` specifies the coefficients of a linear inequality constraint on `x`.

    b_ub 1-D array, optional

      The inequality constraint vector. Each element represents an upper bound on the corresponding value of `A_ub @ x`.

    A_eq 2-D array, optional

      The equality constraint matrix. Each row of `A_eq` specifies the coefficients of a linear equality constraint on `x`.

    b_eq 1-D array, optional

      The equality constraint vector. Each element of `A_eq @ x` must equal the corresponding element of `b_eq`.

    bounds sequence, optional

      A sequence of `(min, max)` pairs for each element in `x`, defining the minimum and maximum values of that decision variable. Use `None` 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, then `min` and `max` will serve as bounds for all decision variables.

    method str

      This is the method-specific documentation for ‘simplex’. ‘highs’, ‘highs-ds’, ‘highs-ipm’, ‘interior-point’ (default), and ‘revised simplex’ are also available.

    callback callable, optional

      Callback function to be executed once per iteration.

  Returns:
    res OptimizeResult

      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:
    ——-
    maxiter int (default: 5000)

      The maximum number of iterations to perform in either phase.

    disp bool (default: False)

      Set to `True` if indicators of optimization status are to be printed to the console each iteration.

    presolve bool (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 to `False` if presolve is to be disabled.

    tol float (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.

    autoscale bool (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.

    rr bool (default: True)

      Set to `False` to disable automatic redundancy removal.

    bland bool

      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_options dict

      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.