How to use Python Scipy Linprog

Through this tutorial, we’ll learn about “Python Scipy Linprog” and how to maximize or minimize a numerical value as an objective, as well as how to utilize various techniques like simplex, etc., to determine the optimal value. We will also go through the following subjects.

• What is Linear Programming?
• How to compute the optimal value of inequalities or equalities using Scipy Linprog.
• How to use the Scipy Linprog with the highs method.
• How to specify the bounds for the inequalities or equalities with help of bounds parameter in the method Linporg
• How to use the Scipy Linprog with the simplex method
• Can we use the sparse matrix with the method Linprog?
• How does Scipy Linprog deal with the infeasible solutions?

What is Linear Programming?

Linear programming is a technique used in mathematics to optimize operations under certain constraints. In linear programming, the primary goal is to maximize or minimize the numerical value. It is made up of linear functions that must adhere to constraints that can take the form of inequalities or linear equations.

To determine the best resource use, linear programming is regarded as a crucial technique. Two terms, linear and programming, make up the phrase “linear programming.” The link between several variables with degree one is defined by the word “linear”. The act of choosing the optimal solution from a range of choices is referred to as “programming.”

To put it another way, linear programming is viewed as a way to maximize or reduce the objective function of a given mathematical model while meeting a set of conditions that are represented by a linear relationship. The linear programming problem’s primary goal is to identify the optimal answer.

In this tutorial, we will utilize the Python Scipy method linprog of module scipy.optimize to solve linear programming problems.

Read: Python Scipy Curve Fit

Python Scipy Linprog

The Python Scipy has a method linprog() in a module scipy.optimize use linear objective function is minimised while observing equality and inequality constraints.

The syntax is given below.

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

Where parameters are:

• c(1d_array): The linear objective function’s coefficients must be minimized.
• A_ub(2d_array): The matrix of inequality constraints. Each row of A ub contains the coefficients of a constraint on x based on a linear inequality.
• b_ub(1d_array): The constraint vector for inequality. An upper limit on each element’s corresponding value of A_ub @ x is represented by that element.
• A_eq(2d_array): The matrix of equality constraints. Each row of A eq contains the coefficients of a constraint on x based on linear equality.
• b_eq(1d_array): The equality constraint’s vector. Every element of A eq @ x must coincide with an element of b eq.
• bounds(sequence): The lower and higher values of each component of the decision variable for x are represented by a series of (min, max) pairs. Use None to demonstrate the absence of a bound. Boundaries are by default set to 0 and 0. If only a single tuple (min, max) is given, the boundaries for all choice variables will be set to lower and higher values.
• method(string): The algorithm used to resolve the problem in standard form. The following are supported: “highs” (default), “highs-ds,” “highs-ipm,” “interior-point,” “updated simplex,” and “simplex.”
• callback(callable): If a callback function is specified, the algorithm will call it at least once for each iteration. The callback function can only take one argument.
• options(dict): A dictionary of possible solvers.
• x0(1d_array): Decision variable guesses that will be improved by the optimization technique. This option is currently only used by the “revised simplex” approach, and can only be used if x0 represents a straightforward, plausible answer.
• integrality(1d_array): Specifies the type of integrality restriction that each decision variable is subject to.

1. 0: Continuous variable; no requirement for integrality.
2. 1: An integer variable that must fall within certain limitations is the decision variable.
3. 2: The decision variable must fall inside its range or have a value of 0. Semi-continuous variable
4. 3: Semi-integer variable; the outcome variable must either take the value of 0 or, within limitations, be an integer.
5. All variables are continuous by default. This argument is currently only taken into consideration by the “highs” method.

The “scipy.optimize.OptimizeResult” is made up of the fields below and is returned by the method linprog(). It should be noted that the return types of the fields may change depending on whether the optimization was successful, so it is recommended to verify “OptimizeResult.status” before relying on the other fields.

• x:(1d_array): The decision variables’ values that satisfy the requirements while minimizing the objective function.
• fun(float): The objective function’s optimal value, c @ x.
• slack(1d_array): The slack variables’ (nominally positive) values, “b ub – A ub @ x.”
• con(1d_array): The equality constraints’ (nominally zero) residuals, “b eq – A eq @ x.”
• success(boolean): If the algorithm finds the best solution, then the statement is true.
• status(int): An integer indicating the algorithm’s exit status. 0: The optimization was successfully finished. 1: Iteration cap achieved. 2: The issue seems unsolvable. 3: The issue seems to have no boundaries. 4: There were issues with the numbers.
• nit(int): The overall number of repetition carried out across all phases.

Let’s take an objective function and find its optimal value by following the below steps:

Import the required method libraries using the below code.

from scipy import optimize

Define the inequality and its bounds using the below code.

c_ = [-1, 3]
A_ = [[-2, 1], [1, 3]]
b_ = [5, 3]
x0_bounds_ = (None, None)
x1_bounds_ = (-2, None)

Now solve the above define inequation by passing it to the method linprog() using the below code.

res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_])
print(res_.fun)
print(res_.x)
print(res_.message)

This is how to use the linprog() method of Python Scipy.

Read: Python Scipy Stats Norm

Python Scipy Linprog Simplex

To solve a linear programming problem there is a simplex method, generally, inequalities are a function with many constraints. The polygon is the inequalities and the vertices are the solution to the inequalities.

The simplex method is a methodical process for evaluating the vertices as potential solutions.
By outlining the constraints on a graph, some straightforward optimization issues can be resolved. However, only two-variable systems of inequalities may be solved using this method. In real-world situations, problems frequently involve hundreds of equations and thousands of variables, which can lead to an astronomical number of extreme points.

The Python Scipy method linprog() accepts a parameter method to specify which method to use for solving the linear problems. So here we will use the method simplex to solve the LP.

The syntax is given below.

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)

Let’s take an example and find the optimal value of the objective function using the simplex method by following the below steps:

Import the required libraries or methods using the below python code.

from scipy import optimize

Defines the inequality or equalities problem that is shown below.

c_ = [-40, 30]
A_ = [[1, 1], [2, 1]]
b_ = [8, 12]
x0_bounds_ = (0, None)
x1_bounds_ = (0, None)

Now find the solution using the method simplex within the linprog().

res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='simplex')
print(res_.fun)
print(res_.x)
print(res_.message)

This is how to use the method simplex to compute the optimal value of the objective function.

Read: Python Scipy Stats Poisson

Python Scipy Linprog Highs

Method=’simplex’ has been deprecated since version 1.9.0 and will be removed in SciPy 1.11.0. Method=’highs’ is used in its place because it is faster and more reliable.

Let’s take the same example that we have used in the above subsection to find the optimal solution for the objective function by following the below steps:

Import the required libraries or methods using the below python code.

from scipy import optimize

Defines the inequality or equalities problem that is shown below.

c_ = [-40, 30]
A_ = [[1, 1], [2, 1]]
b_ = [8, 12]
x0_bounds_ = (0, None)
x1_bounds_ = (0, None)

Now find the solution using the method simplex within the linprog().

res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='highs')
print(res_.fun)
print(res_.x)

This is how to use the method highs to compute the optimal value of the objective function.

Read: Python Scipy Freqz

Python Scipy Linprog Bounds

The method linprog() accepts a parameter bounds which is the lowest and maximum values of each element in x are specified by a series of (min, max) pairs. If there is no bound, use None to indicate that. Bounds are normally set to (0, None) (all decision variables are non-negative).

The bounds for all decision variables will be set by the single tuple (min, max) that is provided.

Let’s take an example of an objective function and tune the bounds of the function to see the optimal values of the function by following the below steps:

A USA firm creates two different kinds of TVs, one of which is coloured and the other in black and white. The company can produce no more than 150 sets every week. Rs. 2500 is needed to construct a black and white set, while Rs. 3000 is needed to build a coloured set. Producing TV sets shouldn’t cost the company more than Rs 640000 each week.

How many black-and-white and coloured sets should be produced if it makes Rs. 500 per set and Rs. 600 for each set of colours to make the most money? Create this utilizing LPP.

from scipy.optimize import linprog

Define the problems using the below code.

• Subject to constraints:
• x, y ≥ 0 (Non-negative constraint)
• x + y ≤ 150 (Quantity constraints)
• 2500x+3000y ≤ 640000 (Cost constraints)
• Objective function: Z = 500x + 600y

c_ = [500, 600]
A_ = [[1, 1], [2500, 3000]]
b_ = [150, 640000]
x0_bounds_ = (0, None)
x1_bounds_ = (0, None)

Now find the optimal value for the above-defined objective function using the below code.

res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_])
print(res_.x)
print(res_.slack)
print(res_.fun)
print(res_.message)

Again change the x0_bounds_ = (0, None) and x1_bounds_ = (0, None) to x0_bounds_ = (3, None), x1_bounds_ = (3, None).

c_ = [500, 600]
A_ = [[1, 1], [2500, 3000]]
b_ = [150, 640000]
x0_bounds_ = (3, None)
x1_bounds_ = (3, None)

This is how to use the parameter bounds of the method linprog() of Python Scipy to specify the desired bounds for the objective function.

Read: Python Scipy Minimize

Python Scipy Linprog Sparse Matrix

We believe it is probably not a good idea to create a dense matrix (or two) to solve a significant sparse LP. It is crucial to employ a solver equipped to handle huge sparse LPs while solving them, as well as to produce the model without deliberately creating any of these zero elements.

It is not an easy task to create a robust, quick, sparse Simplex LP solver in Python to replace the SciPy dense solver. Additionally, a pure Python-based solver might not function as well.
Although not very, very huge (the maybe large, medium-sized model would be a reasonable description), the size of the model we wish to employ may warrant the use of a commercial solver like Cplex, Gurobi, or Mosek.

These issue solvers work quickly and consistently (they solve any LP problem you throw at them). Each of them has Python APIs. The academic solvers are free or quite affordable.

So at last we want to say that the sparse matrices are incompatible with linprog.

Read: Python Scipy Exponential

Python Scipy Linprog Infeasible

If there is no possible solution that satisfies all of the restrictions, or if no feasible solution can be created, then a linear program is infeasible. Infeasibility typically denotes a mistake of some kind because whatever real operation we are modelling must adhere to the limitations of reality.

It can be the result of incorrect data values or an error in the specification of some constraints.

If there isn’t an optimal solution for any linear program in standard form, the issue is either unsolvable or unbounded. A simple viable solution also exists if a feasible solution does. There is a fundamentally workable solution that is also an optimal solution when there is an optimal solution.

Let’s take the same example that we have used in the subsections “Python Scipy Linprog Highs” with the change in bound values by following the below steps:

Import the required libraries or methods using the below python code.

from scipy import optimize

Defines the inequality or equalities problem with the wrong bounds that are shown below.

c_ = [-40, 30]
A_ = [[1, 1], [2, 1]]
b_ = [8, 12]
x0_bounds_ = (0, -1)
x1_bounds_ = (0, None)

Now find the solution using the method simplex within the linprog().

res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='highs')
print(res_.fun)
print(res_.x)

The status of the above solution is 2, which says the problem appears to be infeasible.

You may also like to read the following Python Scipy tutorials.

• Python Scipy Matrix
• Python Scipy Convolve 2d
• Python Scipy Interpolate
• Scipy Ndimage Imread
• Python Scipy Softmax
• Scipy Normal Distribution
• Scipy Ndimage Rotate
• Scipy Misc + Examples

We covered how to compute the optimal value of the objective function, with different bounds, and also known about how linprog deals with the wrong or invalid values in objective function with the following topics.

• What is Linear Programming?
• How to compute the optimal value of inequalities or equalities using Scipy Linprog
• How to use the Scipy Linprog with the highs method.
• How to specify the bounds for the inequalities or equalities with help of bounds parameter in the method Linporg
• How to use the Scipy Linprog with the simplex method
• Can we use the sparse matrix with the method Linprog?
• How does Scipy Linprog deal with the infeasible solutions?