©2020-2024 ioDraw All rights reserved
abstract
： Currently, it is mostly used Matlab Solving the integer programming problem in operations research , Rarely used Python Solve similar problems . This article uses Python in cvxpy Library for solving integer programming problems , The problem solving process is summarized and explained .
key word ：python; integer programming ;cvxpy
<>0. Examples
objective function ： M a x z = 3 x 1 + x 2 + 3 x 3 \ Max \ z= 3x_1+x_2+3x_3 Max z=3x1+x
2+3x3
constraint condition ： { − x 1 + 2 x 2 + x 3 ≤ 4 4 x 2 − 3 x 3 ≤ 2 x 1 − 3 x 2 + 2 x 3 ≤ 3 x
1 , x 2 , x 3 ≥ 0 x 1 , x 2 , x 3 all by whole number \left\{\begin{aligned}
-x_1+2x_2+x_3 \leq 4 \\ 4x_2-3x_3 \leq 2 \\ x_1-3x_2+2x_3 \leq 3\\ x_1,x_2,x_3
\geq 0\\ x_1,x_2,x_3\ All are integers \end{aligned}\right.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−x1+2x2+x3≤44x
2−3x3≤2x1−3x2+2x3≤3x1,x2,x3≥0x1,x2,x3 All are integers
<>1.Python code
# Import numpy import numpy as np # Import numpy import cvxpy as cp # Set the number of variables in the objective function n=3
# Enter the coefficients of the objective function c=np.array([3,1,3]) # Coefficient matrix of input constraints （3×3） a=np.array([[-1,2,1],[0,4,-3],[
1,-3,2]]) # input b value （3×1） b=np.array([4,2,3]) # establish x, The number is 3 x=cp.Variable(n,integer=True)
# Explicit objective function （ here c yes 3×1,x yes 3×1, but python It can be multiplied ） objective=cp.Maximize(cp.sum(c*x))
# Explicit constraints , among a yes 3×3,x yes 3×1,a*x=b(b by 3×1 Matrix of ) constriants=[0<=x,a*x<=b] # Solving problems prob=cp.
Problem(objective,constriants) # here solver Must use cp.CPLEX, Otherwise, it can't be calculated , and CPLEX need pip intall
CPLEX( Tsinghua image is recommended ) resluts=prob.solve(solver=cp.CPLEX) # Input results print(prob.value)
# Value of objective function print(x.value)# various x Value of
<>2. result
<>3. summary
（1） This article only introduces python Solving the most basic problem in integer programming , I hope it can be helpful for beginners .
（2）CPLEX need pip intall CPLEX, And in pip install cvxpy after . and pip install
cvxpy You'll find out again cmd report errors , You need to install Visual Studio XX. Install as required Visual Studio
XX after , Installation can continue cvxpy, install cvxpy Install after CPLEX.
（3）Python Of course, it can solve ordinary linear programming problems , use optimize.linprog() that will do , No more cumbersome .
Technology