Will Yuan's Blog

scipy.optimize

SciPy provides functions for minimizing (or maximizing) objective functions, possibly subject to constraints. It includes solvers for nonlinear problems (with support for both local and global optimization algorithms), linear programming, constrained and nonlinear least-squares, root finding, and curve fitting.

This is the official manual of scipy.optimize: Optimization and root finding (scipy.optimize) — SciPy v1.13.0 Manual

scipy.optimize.linprog is used here to solve the linear programming problem. More information about scipy.optimize.linprog: scipy.optimize.linprog — SciPy v1.13.0 Manual

Note:

For obtaining the minimum spanning tree, the Prim algorithm has been introduced before, and here is another algorithm: Kruskal algorithm.

Kruskal Algorithm steps

• Step 1: Sorts all edges in the graph by weight from smallest to largest.

• Step 2: Try adding edges to the tree from smallest to largest, and if the newly added edge forms a loop with other edges in the tree, discard the edge and continue trying the other edges.

• Step 3: If $n-1$ edges are added to the tree, the minimum spanning tree is built, where $n$ is the number of vertices of the graph.

Note that in the process of adding edges to the tree, Disjoint Set Union (DSU) is used to determine if a loop is formed.

Minimum Spanning Tree

For an undirected graph, the Minimum Spanning Tree is a connected subgraph of the original graph, which contains all the vertices of the original graph, and the sum of its edge weights is the smallest. We can use Prim algorithm to get the minimum spanning tree.

Prim Algorithm steps

The algorithm usually includes the following steps:

How to calculate the distance between two coordinate points (knowing longitude and latitude) in Python? Three methods are given here:

Implement the Haversine formula

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import math
from math import radians, sin, cos, asin

def haversine(lat1, lon1, lat2, lon2):
    # The average radius of the earth is approximately 6371.393km
    EARTH_RADIUS = 6371

    # Convert to radians
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    # Calculate the difference between converted latitude and longitude
    delta_lat = lat2 - lat1
    delta_lon = lon2 - lon1

    # Haversine formula
    temp = math.pow(sin(delta_lat / 2), 2) + cos(lat1) * cos(lat2) * math.pow(sin(delta_lon / 2), 2)
    distance = 2 * asin(math.sqrt(temp)) * EARTH_RADIUS

    return distance

new_dist = haversine(36.1628, 114.2581, 36.5935, 114.6296)
print("The distance calculated using the Haversine formula is:", new_dist, "km")

The output is as follows:

Install GitHub Copilot for PyCharm plugin

Click Settings and search Copilot in the plug-in market:

Install the plugin and restart the IDE:

Primal Problem

$$Max:2x_1+x_2+6x_3-x_4\\ s.t.\begin{cases} x_1+2x_2+x_3-x_4<=10\\ x_1+2x_3+x_4>=5\\ x_2+x_3+2x_4=20\\ x_1>=0,x_2<=0,x_3<=0 \end{cases}$$

The general vector form of the primal problem can be expressed as:

$$Max:z=CX\\ s.t.\begin{cases}AX<=B\\ X>=0 \end{cases}$$

We can represent the coefficients of the original problem as matrices:

Install the Gurobi library

This package only allows solving problems on a limited scale.

1

pip install gurobipy

Then, import it as follows:

1

import gurobipy as grb

• This is an introduction to Google OR-Tools:

  https://developers.google.com/optimization/introduction.

• This is the official tutorial for solving optimization problems in Python:

  https://developers.google.com/optimization/introduction/python.

Now, let's use this tool to solve a simple mixed integer programming problem in Python.

Install the OR-Tools library

1

pip install ortools

Install the CPLEX Library

Install the CPLEX library in Python:

1

pip install cplex

Example

itertools.combinations

Generates all possible combinations of elements of a specified length:

$$C(5,2)$$

1
2
3
4
5
6

import itertools

str = ['A', 'B', 'C', 'D', 'E']
# Compute combinations of length 2 without replacement
combinations_result = list(itertools.combinations(str, 2))
print(combinations_result)

The output is as follows: