SciPy

linprog(method=’revised simplex’)

scipy.optimize.linprog(c, method='revised_simplex', callback=None, options={'c0': None, 'A': None, 'b': None, 'maxiter': 5000, 'tol': 1e-12, 'maxupdate': 10, 'mast': False, 'pivot': 'mrc', '_T_o': [], 'disp': False}, x0=None)

Solve the following linear programming problem via a two-phase revised simplex algorithm.:

minimize:     c @ x

subject to:  A @ x == b
             0 <= x < oo
Parameters
c1D array

Coefficients of the linear objective function to be minimized.

c0float

Constant term in objective function due to fixed (and eliminated) variables. (Currently unused.)

A2D array

2D array which, when matrix-multiplied by x, gives the values of the equality constraints at x.

b1D array

1D array of values representing the RHS of each equality constraint (row) in A_eq.

x01D array, optional

Starting values of the independent variables, which will be refined by the optimization algorithm. For the revised simplex method, these must correspond with a basic feasible solution.

callbackcallable, optional

If a callback function is provided, it will be called within each iteration of the algorithm. The callback function must accept a single scipy.optimize.OptimizeResult consisting of the following fields:

x1D array

Current solution vector.

funfloat

Current value of the objective function c @ x.

successbool

True only when an algorithm has completed successfully, so this is always False as the callback function is called only while the algorithm is still iterating.

slack1D array

The values of the slack variables. Each slack variable corresponds to an inequality constraint. If the slack is zero, the corresponding constraint is active.

con1D array

The (nominally zero) residuals of the equality constraints, that is, b - A_eq @ x.

phaseint

The phase of the algorithm being executed.

statusint

For revised simplex, this is always 0 because if a different status is detected, the algorithm terminates.

nitint

The number of iterations performed.

messagestr

A string descriptor of the exit status of the optimization.

Returns
x1D array

Solution vector.

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
4 : Numerical difficulties encountered
5 : No constraints; turn presolve on
6 : Guess x0 cannot be converted to a basic feasible solution
messagestr

A string descriptor of the exit status of the optimization.

iterationint

The number of iterations taken to solve the problem.

See also

For documentation for the rest of the parameters, see scipy.optimize.linprog

Options
maxiterint

The maximum number of iterations to perform in either phase.

tolfloat

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.

maxupdateint

The maximum number of updates performed on the LU factorization. After this many updates is reached, the basis matrix is factorized from scratch.

mastbool

Minimize Amortized Solve Time. If enabled, the average time to solve a linear system using the basis factorization is measured. Typically, the average solve time will decrease with each successive solve after initial factorization, as factorization takes much more time than the solve operation (and updates). Eventually, however, the updated factorization becomes sufficiently complex that the average solve time begins to increase. When this is detected, the basis is refactorized from scratch. Enable this option to maximize speed at the risk of nondeterministic behavior. Ignored if maxupdate is 0.

pivot“mrc” or “bland”

Pivot rule: Minimum Reduced Cost (default) or Bland’s rule. Choose Bland’s rule if iteration limit is reached and cycling is suspected.

dispbool

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

Previous topic

linprog(method=’interior-point’)

Next topic

scipy.optimize.linprog_verbose_callback