linprog(method=’simplex’)

scipy.optimize.linprog(c, method='simplex', callback=None, options={'c0': None, 'A': None, 'b': None, 'maxiter': 1000, 'disp': False, 'tol': 1e-12, 'bland': False, '_T_o': None})

Minimize a linear objective function subject to linear equality and non-negativity constraints using the two phase simplex method. Linear programming is intended to solve problems of the following form:

Minimize:

c @ x

Subject to:

A @ x == b
    x >= 0

Parameters

c1D array

Coefficients of the linear objective function to be minimized.

c0float

Constant term in objective function due to fixed (and eliminated) variables. (Purely for display.)

A2D array

2D array such that A @ x, gives the values of the equality constraints at x.

b1D array

1D array of values representing the right hand side of each equality constraint (row) in A.

callbackcallable, optional (simplex only)

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

x1D array

The independent variable vector which optimizes the linear programming problem.

funfloat

Value of the objective function.

successbool

True if the algorithm succeeded in finding an optimal solution.

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 optimization being executed. In phase 1 a basic feasible solution is sought and the T has an additional row representing an alternate objective function.

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 : Serious numerical difficulties encountered

nitint

The number of iterations performed.

messagestr

A string descriptor of the exit status of the optimization.

Other Parameters

—————-

maxiterint

The maximum number of iterations to perform.

dispbool

If True, print exit status message to sys.stdout

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.

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.

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 : Serious numerical difficulties encountered

messagestr

A string descriptor of the exit status of the optimization.

iterationint

The number of iterations taken to solve the problem.

Notes

The expected problem formulation differs between the top level linprog module and the method specific solvers. The method specific solvers expect a problem in standard form:

Minimize:

c @ x

Subject to:

A @ x == b
    x >= 0

Whereas the top level linprog module expects a problem of form:

Minimize:

c @ x

Subject to:

A_ub @ x <= b_ub
A_eq @ x == b_eq
 lb <= x <= ub

where lb = 0 and ub = None unless set in bounds.

The original problem contains equality, upper-bound and variable constraints whereas the method specific solver requires equality constraints and variable non-negativity.

linprog module converts the original problem to standard form by converting the simple bounds to upper bound constraints, introducing non-negative slack variables for inequality constraints, and expressing unbounded variables as the difference between two non-negative variables.

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.