【整数规划算法】列⽣成(理论分析+Python 代码实现)
0 介绍
前⾯介绍的割平⾯法和分⽀定界法都是求解整数规划的常⽤⽅法,但是⾯对⼤规模整数规划/混合整数规划,往往直接采⽤割平⾯法和分⽀定界法求解是不现实的,这时候就需要对⼤规模整数规划/混合整数规划问题先进⾏分解和松弛,然后再进⼀步采⽤割平⾯法和分⽀定界法来帮助求解。⽬前我个⼈总结整数规划问题的分解/松弛的主流的⽅法有如下三种:1 Benders decomposition (主要思想是⾏⽣成+割平⾯⽅法)2 Dantzig-Wolfe decomposition (主要思想其实就是列⽣成)3 Lagrangian decomposition (主要思想是 Lagrangian relaxation)
我们今天主要介绍的是 列⽣成 (Column Generation) ⽅法,前两种⽅法我们会在后续笔记中进⾏更新。
列⽣成 (Column Generation) 实际上就是Dantzig-Wolfe decomposition ⾥边最重要的⼀个环节,因此列⽣成经常是和DW分解联合在⼀起使⽤。本⽂分为三部分,第⼀部分是从cutting stock问题出发介绍列⽣成算法的基本思想,第⼆部分是在python环境下基于Gurobi对列⽣成算法进⾏实现,第三部分是从对偶的⾓度来分析列⽣成算法的好坏。
1 从 cutting stock 问题出发介绍列⽣成算法
1.1 直接建模
cutting stock 中⽂可翻译为⼀维下料问题。假设钢材⼚有若⼲根长度为 的钢卷,假设现在有 个客户需要 个长度为 的零件。现在问怎么样切割钢卷能够在满⾜所有客户的基础上,让所使⽤的钢卷数量最少?
举个例⼦来说就是钢材长⽣产的都是统⼀的标准的钢卷长度为 ,现在有3个客户需要10个长度为6的零件,20个长度为8的零件,12个长度为12的零件。对以上描述直接采⽤数学优化模型建模可得:
⽬标函数(极⼩化钢卷被使⽤的数量):约束1(满⾜所有客户的需求):约束2 (切割不能超过钢卷长度): 为可⽤的钢卷集合。
以上模型就是⾮常直观的⼀个建模,该模型也被成为 Kantorovich(苏联应⽤数学家康托洛维奇) 模型。该模型从求解的⾓度来说是⼀个⾮常不好的模型。原因是它的线性松弛的界很差,如果我们把决策变量 都松弛为连续变量,则模型(1.1-1.3)会变成⼀个线性规划。
易知该线性规划(1.1-1.3)的最优解 必然会在约束(1.2)和约束(1.3)等式成⽴的地⽅。即最优解满⾜:
W M n i w i W =20y =k {1, 第k 个钢卷被切
0, 第k 个钢卷不被切
x =i ,k {1, 第i 个零件在第k 个钢卷切割
0, 否则
min y (1.1)
∑k ∈K k
x ≥∑k ∈K i ,k n , i =i 1,...,M (1.2)w x ≤∑i =1M
i i ,k Wy ,k ∈k K
1.3()
K x ,y i ,k k x ,y ∗∗x =k ∈K ∑
i ,k
∗n , i =i 1,...,M (1.4)
w x =i =1
∑
M
i i ,k Wy , k ∈i ∗
K
(1.5)
最优的⽬标函数为
也就是说原模型(1.1-1.3)的线性松弛问题的最优解是⼀个naive的解,由这样得到的线性松弛问题模型的界是⾮常送的,那么直接调⽤求解器去求解原模型(1.1-1.3)的效率就会⾮常低。
1.2 基于列⽣成的建模
上⾯我们谈到直接建模得到的(1.1-1.3)整数规划模型不是⼀个好的模型。那么接下来我们尝试从另外⼀个⾓度对 cutting stock 进⾏建模。⾸先我们需要定义切割模式,还是从之前的例⼦来看,⼀根长
度为20的钢卷切成若⼲长度6,8,12的零件有哪些切法?例如 切1个长度为6的,切1个长度为8的这是⼀种切法,切2个长度为6的,切1个长度为8的这也是⼀种切法,切1个长度为6的切⼀个长度为12 的这也是⼀种切法。我们把⼀种切法就叫做⼀种 切割模式,当然不⽌我这⾥列的三种切割模式。那么我们只需要决策出每种切割模型需要多少次就可以得到整个切割⽅案了。主问题(Master Problem)
我们将上述采⽤切割模型的⽅式⽤数学模型描述出来就可以得到决策变量:⽬标函数:
约束:
其中 是参数 表⽰ 在切割模式 中 切割零件的数量。
在约束(1.8)中 每⼀列就表⽰⼀种切割模式。我们发现切割模式⼀般是指数级别的(对应到模型中就是 n 的数值),也就是说想要把所有切割模式都列举出来是不现实的。因此我们就会⾃然想到是不是能只加⼊⼀部分切割模式,先得到⼀个可⾏解(虽然这个可⾏解可能不太好),接着再加⼊⼀些列来逐渐改进切割模式。从这个想法出发,我们在原始的主问题的基础上只列出⼀部分切割模式,得到受限的主问题:
受限的主问题(Restricted Master Problem)
其中集合 为切割模式的索引集合。
y =
k ∈K ∑
k
∗=W
w x ∑k ∈K ∑i =1M i i ,k ∗
(1.6)
W
w n ∑i =1M
i i x = j 第j 个切割模式被使⽤的次数min x (1.7)
j =1∑
N
j
a x ≥j =1∑
n
ij j n , i =i 1,...,m (1.8)
x ∈j Z , j =+1,...,n (1.9)
a ij j i min x (1.10)
j ∈P ∑
j
s .t .a x ≥j ∈P
∑
ij j n , i =i 1,...,m
(1.11)
x ∈j R , j ∈+P
(1.12)
P ⊆{,n }
上述受限的主问题的对偶问题为:
⼦问题(Subproblem)
我们希望在受限的主问题的对偶问题上添加⼀列来改进受限的主问题的最优解。从线性规划的reduced cost的公式可以知道,添加第为
⼀种直观的添加列的⽅式就是选取能够让受限的主问题⽬标函数最⼩的列:
进⼀步将上式等价改写为如下⼦问题:
其中 表⽰第列 ,约束(1.19)表⽰切割模式要满⾜钢卷长度的约束。可以知道该⼦问题(1.18-1.20)是⼀个背包问题。
2 列⽣成 cutting stock 算法流程与代码实现
max n π(1.13)
i =1∑
n
i i s .t . a π≤i =1∑
m
ij i 1, j ∈P
(1.14)
x ∈j R , j ∈+P
(1.15)
j ∈
{1,..,n }1−a π(1.16)
i =1∑
m
ij i min{1−
a π∣j ∈i =1
∑
m
ij i {1,..,n }}(1.17)
max πy (1.18)
i =1∑
m
i i s .t . w y ≤i =1∑
m
i i W (1.19)y ∈i Z ,i =+1,..,m
(1.20)
y =y ,...,y (1m )j a ,...,a (1j mj )T
列⽣成算法的基本流程如下所⽰:
从上图中可以看出,⼀开始是初始化⼀个最简单的切割模式(pattern)。之后就是⼀个循环迭代过程,先求解受限的主问题获得对偶变量,然后求解背包问题获得可以新添加的列,最后把这个列加⼊到受限的主问题。如此往复循环直到收敛为⽌。
整个列⽣成算法的代码分为三部分:1受限的主问题;2⼦问题;3主⼲代码。本代码借助Gurobi来构建优化模型和求解优化模型,所以如果想读懂代码需要先掌握Gurobi的使⽤⽅法。
受限的主问题代码:
class Master:
def__init__(self, lengths, demands, W)->None:
self.M, self.lengths, self.demands, self.W =len(lengths), lengths, demands, W
self.n_col, self.n_dim =0,0
def create_model(self):
self.x =[]
self.__set_vars()
self.__set_contrs()
def solve(self, flag =0):
def get_dual_vars(self):
strs[i].getAttr(GRB.Attr.Pi)for i in range(strs))]
def__set_contrs(self)->None:
def__set_vars(self)->None:
for i in range(self.M):
self.n_dim = self.M
def update_contrs(self, column_coeff):
self.n_dim +=1
self.n_col +=1
⼦问题代码
class SubProblem:
def__init__(self, lengths, W)->None:
self.lengths, self.M, self.W = lengths,len(lengths), W
def create_model(self):
self.y = del.addVars(self.M, lb =0, ub = GRB.INFINITY, vtype = GRB.INTEGER, name ='y')
def set_objective(self, pi):
def solve(self, flag =0):
def get_solution(self):
Vars()[i].x for i in range(self.M)]
def get_reduced_cost(self):快速排序python实现
del.ObjVal
主⼲代码:
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论