数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。
整数规划概要
定义
在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。
分类
整数规划又分为：
（1）变量全限制为整数时，称纯（完全）整数规划。
（2） 变量部分限制为整数的，称混合整数规划。
整数规划与线性规划不同之处只在于增加了整数约束。不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型。
特点
1.原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况
• （1）原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
• （2）整数规划无可行解。
• （3）有可行解（当然就存在最优解），但最优解值变差。
2.整数规划最优解不能按照实数最优解简单取整而获得
整数规划的数学模型
一般形式
整数规划模型的一般形式可以表示为：
\max(\min)z=\sum^n_{j=1}c_jx_j\\
s.t.\left\{
\begin{aligned}
&\sum^{n}_{j=1}a_{ij}x_j\le(=,\ge)b_i\quad i=1,2,...,m\\
&x_j\geq0\qquad x_j为整数,j=1,2,...,n\\
\end{aligned}\right.依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0-1整数规划。
分类
纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。
全整数规划：除了所有决策变量要求取非负整数外，系数a_{ij}和常数b_i也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。
混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。
0-1整数规划：所有决策变量只能取0或1两个整数
整数规划与线性规划的关系
整数规划
\max c^Tx\\
s.t.\left\{
\begin{aligned}
&Ax=b\\
&x\geq0,x为整数
\end{aligned}\right.松散的线性规划
\max c^Tx\\
s.t.\left\{
\begin{aligned}
&Ax=b\\
&x\geq0
\end{aligned}\right.整数规划可行解是松弛问题可行域中的整数格点
ILP最优值小于或等于松弛问题的最优值
松弛问题无可行解，则整数规划无可行解；
松弛问题最优解满足整数要求，则该最优解为整数规划最优解；
整数规划的求解方法
数学解法
从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，
通过舍入取整，寻求满足整数要求的解即可。
但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。
目前，常用的求解整数规划的方法有：分枝定界法和割平面法；对于特别的0-1规划问题采用隐枚举法和匈牙利法。
程序解法
设整数规划问题如下：
\max z=x_1+x_2\\
s.t.\left\{
\begin{aligned}
&14x_1+9x_2\le51\\
&-6x_1+3x_2\le1\\
&x_1,x_2\ge0
\end{aligned}\right.
我们可以构造出如下系数矩阵：
c^T=\left[
\begin{aligned}
&1\\
&1
\end{aligned}\right]\quad
A=\left[
\begin{aligned}
14&\quad&9\\
-6&\quad&3
\end{aligned}\right]\quad
b=\left[
\begin{aligned}
&51\\
&\ 1
\end{aligned}\right]\quad然后给出程序：
使用pulp库的解法
import pulp
import numpy as np
#目标函数的系数
z=[1,1,1]
#约束
A=np.array([[14,9],
[-6,3]]) #定义约束矩阵
b=np.array([51,1]) #定义约束向量
#确定最大化最小化问题，最小化只要把Max改成Min即可
m=pulp.LpProblem(sense=pulp.LpMaximize)
#定义两个变量放到列表中
x=[pulp.LpVariable(f'x{i}',lowBound=0,cat='Integer') for i in [1,2]]
#定义目标函数，lpDot可以将两个列表的对应位相乘再加和
m+=pulp.lpDot(z,x)
#设置约束条件
for i in range(len(A)):
m+=(pulp.lpDot(A[i],x)<=b[i])
#求解
m.solve()
#输出结果
print(f'优化结果：{pulp.value(m.objective)}')
print(f'参数取值：{[pulp.value(var) for var in x]}')优化结果：4.0 参数取值：[2.0, 2.0]
使用cvxpy库的解法
import cvxpy as cp
import numpy as np
x=cp.Variable(2,integer=True) #定义两个整数决策变量
c=np.array([1,1]) #定义目标向量
A=np.array([[14,9],
[-6,3]]) #定义约束矩阵
b=np.array([51,1]) #定义约束向量
obj=cp.Maximize(c@x) #构造目标函数
cons=[A@x<=b,x>=0] #构造约束条件
prob=cp.Problem(obj,cons) #构建问题模型
prob.solve() #求解问题
print(f"最优值为:{prob.value}")
print(f"最优解为:{x.value}")最优值为:4.0 最优解为:[2. 2.]
指派问题解决函数
用pulp库来实现
import pulp
import numpy as np
#先定义通用解决方法，其中的flatten是递归展开列表用的
def assignment_problem(efficiency_matrix):
row=len(efficiency_matrix)
col=len(efficiency_matrix[0])
flatten=lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x]
m=pulp.LpProblem('assignment', sense=pulp.LpMinimize)
var_x=[[pulp.LpVariable(f'x{i}{j}', cat=pulp.LpBinary) for j in range(col)] for i in range(row)]
m+=pulp.lpDot(efficiency_matrix.flatten(), flatten(var_x))
for i in range(row):
m+=(pulp.lpDot(var_x[i],[1]*col) == 1)
for j in range(col):
m+=(pulp.lpDot([var_x[i][j] for i in range(row)],[1]*row) == 1)
m.solve()
return {'objective':pulp.value(m.objective), 'var': np.array([[pulp.value(var_x[i][j]) for j in range(col)] for i in range(row)])}
#然后定义矩阵，输入求解
efficiency_matrix=np.array([
[ 2,15,13, 4],
[10, 4,14,15],
[ 9,14,16,13],
[ 7, 8,11, 9]])
res=assignment_problem(efficiency_matrix)
print(f'最小值{res["objective"]}')
print(res['var'])最小值28.0 [[0. 0. 0. 1.] [0. 1. 0. 0.] [1. 0. 0. 0.] [0. 0. 1. 0.]]
