Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
scipy

What is optimize.linprog() in SciPy?

Adnan Abbas

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

SciPy is an open-source Python library dedicated to scientific computation. The optimize package in SciPy provides several common optimization algorithms such as least squares, minimization, curve fitting, etc.

The optimize.linprog() function

The optimize.linprog() function is from the domain of linear programmingA component of mathematical programming to solve systems of linear equations and inequalities using some maximizing or minimizing linear objective function., which minimizes a linear objective function subject to linear equality and inequality constraints.

Example

Linear programming in two variables

Image source: Brilliant


Syntax

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

Parameters

The function optimize.linprog() accepts the following parameters:

  • c: This is a one-dimensional array representing the coefficients of the linear objective function.

  • A_ub: This is a two-dimensional array representing the inequality constraint matrix. Each row of the matrix represents the coefficients of a linear inequality.

  • b_ub: This is a one-dimensional array representing the inequality constraint vector.

  • A_eq: This is a two-dimensional array representing the equality constraint matrix. Each row of the matrix represents the coefficients of a linear equality.

  • b_eq: This is a one-dimensional array representing the equality constraint vector.

  • bounds: This is a sequence of the (min,max) pair defining the minimum and maximum value of the decision variable.

  • callback: This is an optional function argument. It is invoked on every iteration.

  • method: This is the algorithm used to solve the standard form problem.

  • options: This is a dictionary of solver options.

  • x0: This is a one-dimensional array that represents the guess values of the decision variables.

Return value

This function returns a solution represented by the OptimizeResult object. As part of the object, the following components are returned.

  • x: This contains the values of the decision variables that minimize the objective function while meeting the defined constraints.

  • fun: This tells the optimal value of the objective function.

  • slack: This tells the (nominally positive) values of the slack variables. Slack variables are the differences between the values of the left and right sides of the constraints.

  • con: This represents the equality constraints residuals.

  • status: This is a value between 0-4 that represents the exit status of the algorithm.

  • success: This tells us that the algorithm has found an optimal solution.

  • nit: This tells us the total number of iterations in all phases.

  • message: This displays the message produced on the algorithm’s termination.

Code

Let’s see how we can use the optimize.linprog() function to solve the following minimization problem.

min z=10x1+15x2+25x3min \ z = 10x_1 + 15x_2 + 25x_3

such that,

1x1+1x2+1x3>=10001x_1 + 1x_2 + 1x_3 >= 1000

1x12x2+0x3>=01x_1 - 2x_2 + 0x_3 >= 0

0x1+0x2+1x3>=3400x_1 + 0x_2 + 1x_3 >= 340

x1, x2, x3>=0x_1, \ x_2, \ x_3 >= 0

import numpy as np
from scipy.optimize import linprog
# Setting the inequality constraints matrix
A = np.array([[-1, -1, -1],
[-1, 2, 0],
[0, 0, -1],
[-1, 0, 0],
[0, -1, 0],
[0, 0, -1]])
# Setting the inequality constraints vector
b = np.array([-1000, 0, -340, 0, 0, 0])
# Setting the coefficients of the linear objective function vector
c = np.array([10, 15, 25])
# Solving linear programming problem
res = linprog(c, A_ub=A, b_ub=b)
print('Optimal value:', round(res.fun, ndigits=2),
'\nx values:', res.x,
'\nNumber of iterations performed:', res.nit,
'\nStatus:', res.message)

Explanation

  • Lines 5 to 10: We set the inequality constraints as A. Since the function requires the constraints to be in the form of <=, we multiply the inequalities by -.

  • Line 13: We initialize the inequality constraints vector as b.

  • Line 16: We set the coefficients of the objective function as c.

  • Lines 19 to 24: Finally, we store the result of the linprog() function in res and print the various components of the res object.

RELATED TAGS

python
scipy

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring