Engineering optimization platforms in Python are an important tool for engineers in the modern world. They allow engineers to quickly and easily optimize complex engineering problems and tasks, such as design optimization, resource allocation, and route planning. This notebook has examples for solving LP, QP, NLP, MILP, and MINLP problems in Python.
1️⃣ Linear Programming (LP)
2️⃣ Quadratic Programming (QP)
3️⃣ Nonlinear Programming (NLP)
4️⃣ Mixed Integer Linear Programming (MILP)
5️⃣ Mixed Integer Nonlinear Programming (MINLP)
Install gekko Library
First, install the necessary gekko library for this notebook. The solutions to the examples are with scipy and gekko. Installing packages only needs to occur once and then it is always available in that Python distribution. Jupyter notebook may require a restart of the kernel to make the library accessible for import.
A company manufactures two products (G and H) and has two resources (X and Y) available.
Each unit of product G requires 3 units of resource X and 8 units of resource Y
Each unit of product H requires 6 units of resource X and 4 units of resource Y
The company has a maximum of 30 units of resource X and 44 units of resource Y available.
The company wants to maximize profits:
$100 per unit of product G
$125 per unit of product H
Linear programming is an optimization method for solving systems of linear constraints and objectives. This problem is mathematically expressed as:
Maximize `100 G + 125 H`
Subject to:
$$3 G + 6 H <= 30$$
$$8 G + 4 H <= 44$$
$$G,H >= 0$$
where G and H are the number of units of products to be produced, respectively.
Scipy Linear Programming
The following code shows how to use linear programming to solve this problem in scipy.optimize with the linprog function. The linear programming problem is placed into the following matrix form:
from scipy.optimizeimport linprog
c =[-100, -125]
A =[[3,6],[8,4]]
b =[30,44]
bound =(0,None)
res = linprog(c, A_ub=A, b_ub=b, bounds=[bound, bound], method='highs')
#print solution print(f'Optimal solution: G = {res.x[0]:.2f}, H = {res.x[1]:.2f}') print(f'Maximum profit = $ {-res.fun:.2f}')
Use either gekko or scipy to solve the LP and report the results for x, y, and the objective function value. Find the solution on the contour plot to graphically verify the results.
A car manufacturer wants to minimize the weight of a car while maintaining a minimum strength requirement. The weight of the car is modeled as a quadratic function of the thickness of the car frame components. The strength of the car is modeled as a linear function of the thickness of the car frame components. The manufacturer wants to minimize the weight of the car while maintaining a minimum strength requirement. This problem is formulated as:
Minimize `\frac{1}{2} x^T Q x + p x`
Subject to:
$$G \, x >= h$$
where x is the thickness of the car frame components, Q is the quadratic weight coefficient matrix, p is the linear weight coefficient vector, G is the strength coefficient matrix, and h is the strength constraint vector.
#Problem data #Quadratic weight coefficients
Q = np.array([[1,0],[0,2]]) #Linear weight coefficients
p = np.array([1,2]) #Strength coefficients
G = np.array([[1,1],[1,2],[2,1]]) #Strength constraints
h = np.array([3,4,5]) #Initial guess
x0 = np.array([0,0])
The minimize function in the scipy.optimize module is a general-purpose nonlinear optimization routine that can be used to find the minimum of a scalar function of one or more variables. To use it, you need to provide the following inputs:
res = minimize(objective_function, x0,
constraints=con,bounds=bnds,
method='SLSQP',options=opt)
The following code shows how to use quadratic programming in gekko. Change to remote=False to solve locally instead of using the public compute server. The public server has additional solver options.
m = GEKKO(remote=False)
x = m.Array(m.Var,2,lb=0,ub=10)
m.Minimize(0.5 * x@Q@x + p@x)
gx = G@x
m.Equations([gx[i]>=h[i]for i inrange(len(h))])
m.solve(disp=False)
This problem has a nonlinear objective that must be minimized. The variable values at the optimal solution are subject to (s.t.) both equality (=40) and inequality (>=25) constraints. The product of the four variables must be greater than 25 while the sum of squares of the variables must also equal 40. In addition, all variables are constrained between 1 and 5 and the initial guess is x=[1,5,5,1].
Mixed integer linear programming (MILP) is a type of optimization problem that involves both continuous and discrete (integer) variables. In contrast, regular linear programming (LP) only involves continuous variables. The presence of integer variables in MIP makes the problem more difficult to solve, as the solution space is now discrete rather than continuous. This means that many of the techniques used for solving LP problems are not applicable to MIP. Specialized algorithms and solvers, such as branch-and-bound and branch-and-cut, are typically used to solve MIP problems.
Scipy Mixed Integer Linear Programming
Use the integrality option in the linprog function to specify:
0: continuous
1: integer
from scipy.optimizeimport linprog
#Define the objective function
c =[-1,4]# minimize -x + 4y
#Define the constraints
A_u = np.array([[3,2],[1,5]])
b_u = np.array([10,10])
#Define the bounds
b =(0,10)# 0 <= x <= 10
#Solve
res = linprog(c, A_ub=A_u, b_ub=b_u, bounds=(b,b),
integrality=[1,1])
The following code shows how to solve mixed integer linear programming problems. Use integer=True to specify an integer variable. The solver APOPT is a mixed integer solver in gekko that is selected with m.options.SOLVER=1.
m = GEKKO(remote=False)
x = m.Array(m.Var,2,lb=0,ub=10,integer=True)
m.Minimize(c@x)
Ax = A_u@x
m.Equations([Ax[i]<=b_u[i]for i inrange(len(b_u))])
m.options.SOLVER=1
m.solve(disp=False)
where x and y are integer values. Use either gekko or scipy to solve the MILP and report the results for x, y, and the objective function value. There are 3 potential solutions. Find the integer solutions on the contour plot to graphically verify the results.
Mixed integer nonlinear programming (MINLP) is like MILP but may have a nonlinear objective and constraints. It also requires specialized solvers such as the APOPT solver in gekko. There is no current MINLP solver for scipy, but that is likely changing in a future release.
In addition to binary (0,1) and integer variables, Special Ordered Sets are also possible to define from a selection of discrete options such as [0.5, 1.15, 2.6, 5.2].
from gekko import GEKKO
m = GEKKO()# create GEKKO model #integer variable
x1 = m.Var(integer=True,lb=-5,ub=10) #create Special Ordered Set variable
x2 = m.sos1([0.5,1.15,2.6,5.2]) #continuous variable
x3 = m.Var(lb=0)
m.Minimize(4*x1**2-4*x2*x1**2+x2**2+x1**2-x1+x3**2)
m.Equation(x3*x2>=1)
m.options.SOLVER=1# APOPT solver
m.solve(disp=False) print('x1: ' + str(x1.value[0])) print('x2: ' + str(x2.value[0])) print('x3: ' + str(x3.value[0]))
A piece of letter paper 8.5x11 inches is made into an open-top box by first removing the corners and then by folding the sides up to the adjacent side. The starting sheet has height and width. The objective is to maximize the volume of the box (no lid) by choosing an appropriate value of x (the height of the box).