精华内容
下载资源
问答
  • 列生成算法解决什么
    千次阅读
    2020-10-22 18:15:55

    列生成column generation算法,是求解大规模线性规划问题的一种常用算法,在运筹优化领域有着非常广泛的应用。

    应用场景:因为整数规划更符合现实实际,因此它通常被应用于求解大规模整数规划问题的分支定价算法(branch-and-price algorithm)。当求解一个最小化问题时,列生成算法主要的作用是为每个搜索树节点找到一个较优的下界(lower bound)(默认为min问题,LP是IP的最好解,下界)。本质上而言,列生成算法就是单纯形法的一种形式,是用来求解线性规划问题的。

    线性规划的单纯形法需要计算所有非基变量的检验数;而列生成算法通过巧妙构造子问题,让这一步不需要遍历所有变量,甚至都不需要知道一共有多少变量,只要能在每次迭代的时候生成一个或者多个变量,提升优化效果就可以了,通过不断加入新变量直到没有小于0的非基变量的检验数,至此求得最优解。链接: 求解实例具体求解过程.

    注:子问题是选择入基变量的,它的求解效率也挺重要。选择最大的检验数放入进来,就把这个变量的相关系数列加入到限制主问题(RMP)系数矩阵中进行求解。不断迭代反复。

    本篇介绍它的最初形式,原理及应用。

    一、最初是为了解决下料问题

    即cutting-stock problem。有标准尺寸大卷20m,现顾客有3种需求,分别为3m、6m、9m的小卷,且分别需要25,60,90个。问怎么减少耗费的情况下满足顾客的需求?

    这个问题在cplex和gurobi的代码例子中都有。

    思路:
    P1——>P2(set covering formulation)——>LMP(松弛掉整数约束)——>Sub-problem

    得到线性规划问题的最优解后,向上取整,即得到整数规划的可行解。

    注:
    见下图1的LPM,xj向上取整,左边更大,约束仍然成立。

    具体如下:
    (1)常规建模P1,本质是指派问题
    即min{消耗的大卷数}
    但是:
    当大卷数特别多时,比如几千几万几十万时求解不易。
    第二,整数规划不易求解。

    (2)转换角度,由切割方案出发,转化为P2(set covering formulation)
    即min{切割各种方案消耗的大卷数}

    这里的问题在于“需要提前列出所有的切割方案”,然而随着大卷宽度增加,顾客需求组合越来越多,列举所有的切割方案很不容易,并且处理起来也不容易。
    第二,它也是个整数规划问题,所以求解也不易。
    整数规划转换为线性规划

    (3)所以我们松弛整数约束,将其转化为线性规划问题,这里叫做主问题(LPM)

    即Linear programming master problem,此处解决了P2中的整数规划求解之难的问题,但是,P2里的第一个问题,也就是需要提前列出所有的切割方案集,还是比较困难的。

    因此,列生成算法登场!也就是说列生成的精髓在于:不必求解大问题(线性规划原问题),而是一次次求解小问题(子问题)。

    (4)不必在一开始就给出所有的切割方案集,只用给出部分方案就可以。求解只含有部分列的线性规划问题即限制主问题RLMP(Restricted master problem)

    (5)求解限制主问题,即线性规划问题,可以用单纯形法求解其对偶问题的最优解。

    因为限制主问题是最小化问题,因此当所有的检验数全部非负时,才能达到最优;
    只要有一个检验数为负,即表示目标函数还有进一步降低的可能,也就是问题还可以继续优化。
    限制主问题和其对偶问题
    下料问题:因为一开始只有部分切割方案,我现在再找到一个切割方案加到原问题,进基出基后,判断检验数。
    假如添加之后,使得检验数为负,即求解结果得到改进,那说明这个切割方案加进去之后更好。若检验数非负,那问题没有得到改进,那就不要这个切割方案,即不加入这个切割方案。

    理论:
    要么找到一个<0的检验数,使其出基,那么就把这一列j(新的切割方案)加进去。
    如果找不到j使解得到改进,即证明不可能再有新一列了。那么就要证明不再有检验数<0,即证明所有的检验数>=0。

    (6)我们可以这么理解,与其找一个<0的检验数使解改进,不如找最小的检验数予以改进(改进更快),那么就转化为下面这个优化问题,即子问题Subproblem。
    子问题
    只要最小的检验数为非负,那么所有的检验数一定都大于0了。此时,就能达到最优。
    而如果最小的检验数为负数,那么将其添加到限制主问题中,继续求解。

    注:
    1.参数定义
    m:顾客需求的种类数;系数矩阵的行数,约束条件
    n:所有的方案集。系数矩阵的列数,变量数
    在实际问题中,我们在一开始通常给出的是m种方案,m列(m即客户的需求种类数m行),也就是给出m列m行,是满秩状态,因此保证一开始能求解。
    否则:
    m>n时,即约束条件>变量数,此时无解。
    m<n时,即约束条件<变量数,此时是优化问题嘛,初始问题就是这样,所以我们才转化令m=n的。

    二、延伸(并行机问题)

    还是一开始的下料问题。现在有3种大卷,还是要切割成小卷。如:有标准尺寸大卷15m、20m、25m,现顾客有3种需求,分别为3m、6m、9m的小卷,且分别需要25,60,90个。问怎么减少耗费的情况下满足顾客的需求?

    相当于3个标题一中的下料问题。此时为并行机问题,目前在调度、排班等领域经常用到。

    应用列生成解决时,与一中的区别在于:
    求解子问题的时候,每次要求解3类子问题;找到每类子问题的单纯形因子也就是检验数之后,再继续代入到原问题中,等等等等。

    三、总结

    1.将整数规划问题松弛为:线性规划 主问题LPM linear programming master problem,用列生成求解线性规划主问题LPM。

    2.列生成总结:
    在这里插入图片描述

    在这里插入图片描述

    D-W可以重写formulation,使其变为一个具有非常非常多变量和列的数学模型。那么就可以利用列生成了,这个放在篇2写。

    更多相关内容
  • 最清楚的-列生成算法简介

    千次阅读 2021-10-12 16:02:31
    什么需要了解列生成算法的原理 列生成算法无法简单地调用第三方库来使用,必须根据具体问题,构造不同的算法模型。 只有了解了原理,才能在踩到各种坑时,有所针对地去优化各种细节。不然只能抓瞎或者抓腮。 ...

    本文尽量避免数学公式,使用文字解释列生成算法的原理,争取让读者能形成直观上的理解。

    为什么需要了解列生成算法的原理

    1. 列生成算法无法简单地调用第三方库来使用,必须根据具体问题,构造不同的算法模型。
    2. 只有了解了原理,才能在踩到各种坑时,有所针对地去优化各种细节。不然只能抓瞎或者抓腮。

    列生成算法原理

    列生成算法可以从两个视角来理解:对偶角度和单纯形算法角度。

    对偶角度

    啥是对偶

    这里简单过一下对偶的概念。

    假设有个长得很标准的线性规划问题:

    那么,它的对偶问题为:

    下面我们都以这个问题来讨论,即说到原问题时,默认是一个最小化问题;说到对偶问题时,默认是一个最大化问题。

    怎么理解这个对偶关系呢?借用经济学方面的话来说,假设原问题的目标是让成本最小,那么对偶就是让收入最大。更确切地讲,是:

    • 原问题丶:保证收入不低于某个值的条件下,使成本最小化。
    • 对偶问题:保证成本不高于某个值的条件下,使收入最大化。

    那个丶纯粹是为了对齐,忽略之……

    可以看到,原问题和对偶问题其实就是一个问题:目标净收益最大。只是一个是约束收入优化成本,一个是约束成本优化收入。角度不同而已。体现在公式上,就是原问题的变量对应对偶问题的约束,目标系数对应约束边界,约束矩阵倒转过来

    另外,关于对偶,一个比较重要的特性是:原问题的最优值与对偶问题的最优值相等

    从对偶角度看列生成算法

    列生成算法主要用途在于求解变量多,但是大部分变量将会取值为0的线性规划问题。总体思路是先忽略大部分变量,构造一个只使用小部分变量的模型(其余变量相当于值为0),这样就能很快求出一个解。然后寻找模型外的变量,找到能够让目标值更优的变量,加入模型再次求解。重复这个过程直至找不到更好的变量。

    这个过程的关键问题在于,怎么评估模型外的变量是否能让目标值更优。

    我们从对偶的角度来研究这个问题。

    原问题的变量对应对偶问题的约束。所以原问题新增变量,相当于对偶问题新增约束。

    原问题新增变量 -> 对偶问题新增约束

    由于对偶问题是个最大化问题,所以对偶问题新增约束后,显然最优值不变或变差,也就是不变或变小。从常理上看,约束越多,最优值越差嘛。

    而前面提到的,原问题的最优值等于对偶问题的最优值。也就是说,如果对偶问题最优值不变,那么原问题最优值也不变;如果对偶问题最优值变小,那么原问题最优值也变小。而我们需要的正是让原问题的最优值变小。

    所以问题变为如何尽量避免新增的约束没有改变最优值。设想一下,当加入新约束时,如果当前对偶的最优解没有违反新的约束,那么这个解仍然会是新增约束后的对偶问题的最优解,最优值将不变。

    因此,我们要找的新增的约束,要和当前最优解冲突

    整条逻辑链为:

    新增变量后原问题最优解变小 -> 新增约束后对偶问题最优解变小 -> 新增约束前的最优解不在新增约束后的可行域 -> 新增约束前的最优解不满足新增的约束

    一行对偶问题的约束的公式为:

    假设最优解为w*,那么违反约束的条件为:

    变换一下,变成:

    左侧的式子,叫做的reduced cost,也叫做检验数

    通过分析,我们知道,只要加入reduced cost小于0的对偶约束(从而加入了原问题对应的变量)即可

    很自然的想法是,我们更倾向于找到reduced cost最小的一个或几个变量加入,也就是最好能找到最小化reduced cost的新约束:

    这里就出现了一个新的最优化问题。这个问题叫做列生成的子问题(sub problem)。其中w*是已知的,未知量是c和a。c和a是和问题的应用场景有关的,需要根据实际场景来构造c和a的约束条件。所以子问题无法通用地求解,只能根据具体问题选择不同的方法求解。

    当所有未加入模型的变量的reduced cost都大于等于0时,目标值无法再优化,说明我们已得到最优解。

    另外,熟悉对偶问题经济学含义的同学会知道,reduced cost是指产品的差额成本。那么显然要新增的是差额成本为负的产品了。这是另一种理解列生成的思路。

    单纯形算法角度

    对偶角度给出了一个偏感性的方式来理解列生成算法。换个视角,从单纯形算法角度上看,则是单纯形算法本身,为了更高效地求解包含大量变量的问题,自然地扩展为列生成算法。

    相信有不少人被单纯形算法虐得有心理阴影——公式复杂,手工计算量也巨大……

    其实,如果我们先不看细节,单纯形的核心原理并没有那么难以理解。下面讲解时不会很严谨,理解算法框架就够了。严谨的过程请参阅运筹学相关书籍。

    单纯形算法

    众所周知,单纯形算法有一个几何上的解释:

    • 线性规划是一个凸优化问题,局部最优解就是全局最优解。
    • 线性规划的解空间是一个n维的凸多面体。最优解在这个凸多面体的某个顶点上。
    • 单纯形算法从一个初始顶点开始,不断沿着邻边找更好的顶点。
    • 当一个顶点四周没有更好的顶点时,这个顶点就是最优解。

    整个过程就像水沿着一条蜿蜒的沟渠流下,最终汇聚到最低点一样。

    问题是,这里面的几何概念和代数公式怎么对应?

    这里用不严谨(但更容易理解)的语言说明一下:

    • 边界:解空间是由不等式约束(包括变量非负这些约束)围起来的一块空间区域。当点p使得若干个不等式取等号时,那么点p就在约束边界的超平面上。这个边界可能是一个面、边、顶点。
    • 顶点:顶点会让尽量多的约束取等号。也就是说,顶点是由若干个改为等号的约束组成的方程组的解。我们叫这个方程组为约束边界方程组
    • 沿着边:约束边界方程组去掉一个方程,其解集就变成与顶点邻接的一条边。再取一条原方程组外的约束条件加入,所得到的解就是相邻的顶点。简单说,就是约束边界方程组中替换掉一个方程,形成的新方程组解出来就是相邻的顶点。

    这里涉及到通过让约束取等号来求边界的操作,而不等式乱糟糟地混在方程型的约束和变量非负约束里,会使这里的分析比较困难。所以使用单纯形算法之前,都会通过引入松弛变量、剩余变量和人工变量等方法(这一步在这里不重要,不详细展开了),将线性规划转换成如下标准形式:

    标准形式中只有变量非负约束包含不等式,其他约束都是等式。这样我们就可以很容易地做边界相关的计算了。假设变量数量为n,等式约束数量为m。通过转换而来的标准形式都会有n > m。那么,我们知道,只要让n-m个变量等于0,剩下的m个变量就可以通过这m个等式联立方程组(约束边界方程组)求出一个解(简单起见,不考虑无解,无数解这些边缘条件)。这个解就是一个顶点。

    这里约束边界方程组中的m个变量叫作基变量,固定值为0的n-m个变量叫作非基变量

    沿着边找相邻顶点,就是取一个被固定为0的非负约束,也就是一个非基变量(这个操作叫入基),替换掉一个基变量(这个操作叫出基,这个变量出基后就固定值为0),然后重新求解一个顶点。

    入基操作需要选择入基变量,选择的依据是这个变量在目标函数中的下降速度,也就是这个变量增加1时,目标值减少多少。经过推导可知,下降速度的计算公式刚好是检验数(reduced cost)。这里就和对偶的视角联系起来了。

    出基操作这里就不细说了,大致的思路是在约束条件下,旧的基变量有一部分会随着入基变量的增长而下降,其中最先下降到0的旧的基变量就会被选为出基变量。

    整个单纯形算法的计算步骤是:

    1. 选取基变量和非基变量,简单能出初始解就好。
    2. 计算所有非基变量的reduced cost,找到最小且为负值的那个作为入基变量。如果reduced cost都大于等于0,迭代终止。
    3. 选出基变量
    4. 解约束边界方程组,回到步骤2

    从单纯形算法角度看列生成算法

    在单纯形的步骤2,需要计算所有非基变量的RC。找到最小的那个。当变量个数很多的时候,这一步就成为了算法运行时间瓶颈。

    在一些情况下,通过巧妙构造问题,可以让这一步不需要遍历所有变量。甚至我们都不需要知道有多少变量,只要能在每次迭代的时候生成一个或者多个变量,提升优化效果就可以了。

    由于不需要遍历所有变量,所以一开始就不需要使用所有变量,只需要使用一组能产生初始解的初始变量构成线性优化问题即可。这种只使用部分变量的模型被称为原问题的restricted master problem(RMP)

    每次迭代时,生成一个或多个让reduced cost最小的变量加入RMP。这个生成步骤就是求解子问题。不断加入新变量直到没有小于0的reduced cost的变量时就达到最优解。

    到这里就和对偶角度分析的结果一致了。

    下面是单纯形算法与列生成算法简要流程图的对比,可以看到,两者的结构是一样的。

    一般来说,我们不会手搓单纯形算法,所以正常都是直接调用单纯形算法库解RMP,然后做列生成,再跑RMP,直到达到最优。

    一个经典例子:Cutting Stock Problem

    这是一个列生成算法的经典例子。

    原纸卷每个长17m,顾客们分别需要25个3m长,20个5m长,18个7m长的纸卷。
    问:如何切割使消耗的原纸卷数量最少?

    令一个原纸卷的切割方案集合为:

    P = {(a, b, c) | 3a + 5b + 7c <= 17}

    其中,a是一个原纸卷切割出的3m纸卷数量,b是5m纸卷数量,c是7m纸卷数量。

    我们用变量x(abc)表示使用切割方案(a, b, c)的原纸卷数量。

    显然,一个变量与一个原纸卷切割方案一一对应。建模如下:

    这里故意不适用传统的下标序号标记,意在突出我们不需要对变量编号,只需要知道变量在对应在什么集合上,如何通过集合中的元素生成变量就行了。

    初始解很好找。比如说我们可以取25个原纸卷按照方案(1, 0, 0)切割,20个原纸卷按照方案(0, 1, 0)切割,18个原纸卷按照方案(0, 0, 1)切割。这当然会有很多浪费。但是初始解可行就可以了,浪费的部分会在下面的迭代中优化掉。

    接下来要生成变量。变量与切割方案一一对应的。所以是要找出一个切割方案(a, b, c),使得reduced cost最小。

    其中w1、w2和w3分别为约束R1、R2和R3的对偶值。

    约束条件除了a、b、c非负外,还需要满足切割后的纸卷长度综合小于或者等于原纸卷的长度。

    这样子问题就构造好了。求解子问题得到新增变量。然后迭代直到最优。具体计算这里不展开了。

    整数规划求解

    前面提到的单纯形算法和列生成算法求解的都是线性规划。在实际应用中,一般还会需要求解整数规划。也就是变量都约束为整数的线性规划。

    这里先提一个概念:整数规划的线性松弛,整数规划问题,不考虑整数约束,剩下的约束条件和目标组成的线性规划问题。

    其实我们并没有很好的方法直接求解整数规划,通常都是不断地调整并求解线性松弛,最后找到最优整数解。

    分支定界

    分支定界是一个用来求整数优化问题的框架。其实思路很简单,就是采用类似二分法的技巧,在线性解空间中暴力搜索整数解。

    首先,求解线性松弛得到线性解。取一个变量x进行分支。比如x线性解值为1.2,那么产生 x <= 1 和 x >= 2 两个分支。将这两个条件分别加入到线性松弛,得到两个线性规划。再求解这两个线性规划,两个又分别分支……直到求得最优解。

    有些情况下判断一个解是否为最优解是有方法的,所以不用搜索所有分支。但是,分支定界在最坏情况下的时间复杂度仍是指数级。为了防止运行时间过长,一般使用分支定界时还会额外加一些终止条件,比如回溯次数限制、运行时间限制、找到第一个整数解就结束等。

    分支定价

    分支定价就是在分支定界框架中,使用列生成算法来求解每个分支节点的算法。

    不过这里,除了根节点,其他节点不用从头开始生成新变量,继承父节点用到的变量即可,这样可以节省很多重复生成变量的过程。

    在01整数规划中,还有更简化的方法,每次列生成得到线性松弛的最优解后,找出值最接近1的变量,新加这些变量等于1的约束,继续跑列生成,直到找出所以值为1的变量。剩下的自然都是0了。这个方法可以加入回溯,也可以不回溯,出现无解就直接结束……据说不回溯也很少出现无解的情况。

    一些相关问题

    退化问题/类退化问题

    通过RC找的新变量不一定能让目标值变得更好,仍然存在不变的可能。极小概率的情况下,单纯形算法可能会有入基变量和出基变量循环出现的情况。由于我们肯定是调用线性规划库来跑单纯形的,所以不用考虑这个……

    列生成没有出基操作,不会出现循环。但是有一些改进会剔除冗余变量,这时就会有极小概率会出现循环了。这种情况不需要费心去处理,玄学调参降低出现概率,并设置最大迭代次数等强制终止条件,确保能终止就好。

    最恶心的情况是没有循环,但是长时间没有提升目标值的情况。这其实是算法卡在一个拐点上了,只要过了拐点就能开始提升。特别是在一些约束较强的问题(比如密集的排班问题)中,使用某些启发式算法或者手工做出来的初始解就很容易出现这种情况。

    而我们为了避免算法跑太久,通常会设置多次迭代没有提升就结束的条件。这可能使算法从拐点出发后,几次迭代无优化就直接结束了。

    这种情况无法完美解决。简单的就是调参加更巧妙地设置结束条件,通过多次试验尽量让算法能跨过这个拐点。还有另一个技巧是可以适当地给约束边界加一下噪音,比如说小于等于1的约束,可以放宽到小于等于1.0001。这样从初始解出发迭代时,由于边界宽松了一些,变量可以有些许变化,会让目标值有一些微小的提升,帮助判断是否需要结束迭代。

    CPLEX计算reduced cost的问题

    使用CPLEX时,我们可以很方便的设置变量的上下界。比如设置 0 <= x <= 1。这时,x <= 1这部分是会影响reduced cost的值的。而CPLEX接口计算的是没有考虑这个条件的……所以可能你自己手搓代码出来reduced cost和CPLEX接口出来的reduced cost不相等。

    更严重的是,可能你会忘了 x <= 1 这个条件,导致列生成的过程中算错reduced cost。

    这个问题其实影响不大,主要是会干扰一些计算过程正确性的验算。

    如何验证子问题有没有严重问题

    没有做分支操作时,线性松弛的目标值如果变差,说明子问题可能出现了一些很蠢的问题。

    线性规划求解算法选择

    每次迭代求解线性规划时,选用不同的算法会影响求解时间。根据经验:

    • 增加少量列时(列生成),使用单纯形算法(Primal)。
    • 增加少量约束时(分支),使用对偶单纯形算法(Dual)。
    • 其他情况,酌情使用对偶单纯形算法或者内点法。通过试验决定。
      • 对偶单纯形算法快的时候很快,慢的时候很慢。
      • 内点法速度比较稳定。

    以上也并不是所有场景通用的。应当针对具体问题,反复试验来确定使用什么算法。

    迭代中剔除冗余变量

    Reduced cost可以用来评估变量的“有用”程度。越小表示变量越有用,越大表示变量越无关紧要。

    列生成迭代次数较多后,变量数量会越来越多,从而每次迭代的运行速度越来越低。可以设定一个变量规模上限,当变量数量大于上限时,从模型中去掉reduced cost最大的那些变量。

    标签: 整数规划对偶单纯形线性规划运筹学分支定界分支定价列生成

    展开全文
  • 本期小编为大家介绍单纯形法的另一种拓展算法—列生成算法,主要从其产生背景、基本思想、应用实例、平台实现以及与单纯形法的区别和联系五个方面展开讲解,一起来看一看吧! 列生成算法(Column Generation ...

    本期小编为大家介绍单纯形法的另一种拓展算法—列生成算法,主要从其产生背景、基本思想、应用实例、平台实现以及与单纯形法的区别和联系五个方面展开讲解,一起来看一看吧!

    列生成算法(Column Generation Algorithm)是一种用于求解大规模线性优化问题的高效算法,其理论基础由Danzig等人于1960年提出。本质上来讲,列生成算法是单纯形法的一种形式,用来求解线性规划问题。

    一、产生背景

    在某些线性规划问题的模型中,约束条件的数目有限,但变量的数目会随着问题规模的增长爆炸式的增长,很难把所有的变量都显性的在模型中表达出来,这类问题就是大规模的线性规划问题。面对这类问题,单纯形法虽然能保证在数次迭代后找到最优解,但由于其需要对众多变量进行基变换,求解过程会异常繁琐。此外,在用单纯形法求解这类问题时,基变量只与约束条件的个数相关,每次迭代只会有一个新的非基变量进基,换言之,在整个求解过程中其实只有很少一部分变量会被涉及到。在这种背景下,研究人员基于单纯形法提出了列生成算法。

    该算法不是直接同时处理所有的候选方案,而是基于当前生成的列的子集,通过限制主问题进行优化求解;其余的候选方案可以改善限制主问题当前最优解时,才会进入该子集。与单纯形法相比,列生成的进基变量是通过求解子问题生成的,而单纯形法的进基变量是模型存在的变量。

    目前,列生成算法已被应用于求解很多著名的NP-hard优化问题,如机组人员调度问题(Crew assignment problem)、切割问题(Cutting stock problem)、车辆路径问题(Vehicle routing problem)、单资源工厂选址问题(The single facility location problem)等。

    二、基本思想

    列生成算法通过求解子问题(sub problem)来找到可以进基的非基变量,该非基变量在模型中并没有显性的写出来(可以看成是生成了一个变量,每个变量其实等价于一列,所以该方法被称为列生成算法)。如果找不到一个可以进基的非基变量,那么就意味着所有的非基变量的检验数(Reduced Cost,RC)都满足最优解的条件,也就是说,该线性规划的最优解已被找到。其思路如下:

    1、先把原问题(Master Problem,MP)转换到一个规模更小(即变量数比原问题少)的问题上,这个只使用部分变量的模型被称为原问题的RMP 问题(Restricted Master Problem)。在RMP上用单纯形法求最优解,注意此时求得的最优解只是RMP上的,并不是MP的最优解。

    2、然后需要通过一个子问题去检测在那些未被考虑的变量中是否有使得RC小于零的情况,如果有,那么就把这个变量的相关系数列加入到RMP的系数矩阵中,返回第1步。

    经过反复迭代,直到子问题中的RC都大于等于零,此时就找到了MP的最优解。流程图如下:

    三、应用实例

    1、问题描述

    有三种长度分别为91416的木材,对应的成本价为5910,需要切割成长度为4的成品30个;长度为5的成品20个;长度为7的成品40个。求解切割方案,使得总体成本价最低。

    首先枚举所有可能切法:

     

    (2)建立模型:定义变量x_{j}表示使用第j种切割方案的次数,c_{j}表示第j种方案的成本,a_{ij}表示第j种方案生成第i种木材的数量(i=1,2,3),所有切割方案的集合为J。a_{j}=(a_{1j},a_{2j},a_{3j})^{^{T}}表示j方案下分别切出来尺寸为4、5、7的木材的个数,b=(30,20,40)^{T}表示所需尺寸为4、5、7木材的最小个数。该问题表示如下:

     (1)求解目标:找到最好的方案组合,使价格最小。

    2、列生成方法:

    (1)初始化

    在枚举出的14种方案中挑选较好(价格最低)的方案组合,即前三种方案:

    (2)主问题

    此时的主问题为:

    基于初始化的方案求解,利用gurobi求出最佳方案组合:x^{*}=(5,20,40)^{T},z^{*}=325,w^{*}=(2.5,2.5,5),即前三种方案分别使用15、20、40次,总成本为325, w^{*}表示生成这三种长度的木材的合理价格。

    (3)子问题

    节省成本:

     即找到一个新的方案,计算该方案较原始方案的节省成本(切出来的总价值-成本)。当节省的成本都小于等于0时,求解问题达到最优。由于原木材有三种:长度尺寸为9、14、16,所以可分解为三个子问题。

     子问题2求解出来的节省成本最大,加入到主问题中。

    (4)迭代

    求解新生成的主问题,直到主问题对应的三个子问题求解出来的节省成本都是负数,表明当前主问题的解已是最优解,停止计算并输出结果。

    四、平台实现

    基于以上求解步骤即思想,依靠Python语言,借助Pycharm平台和gurobi求解器,求解上述板材切割问题。部分代码如下(关注“运筹学”公众号→后台回复“列生成算法”即可获取完整代码):

    最终结果:

    可以得到原问题的最优解为:x_{1}=5,x_{2}=20,x_{4}=20,z^{*}=305,即采用第一种、第二种和第四种切割方案,使用次数分别为5、20、20,最小成本为305。

    五、与单纯形法对比

    1、区别

    1在求解过程上:单纯形法需要计算所有非基变量的RC,而列生成算法通过巧妙构造子问题,让这一步不需要遍历所有变量,甚至都不需要知道一共有多少变量,只要能在每次迭代的时候生成一个或者多个变量,提升优化效果就可以了,通过不断加入新变量直到没有小于0RC的变量来求得最优解。

    2在适用范围上:与单纯形法相比,列生成算法可以求解变量很多的线性规划问题,也就是前面所说的大规模的线性规划问题。

    2、联系

    从本质上来讲,列生成算法就是单纯形法的一种形式,是用来求解线性规划问题的。此外,列生成算法在求解每个子问题时,需要用到单纯形法。

    ★ 在python中安装Gurobi的详细教程可以参考以下网址:

        https://blog.csdn.net/weixin_41596280/article/details/89112302

    ★ 列生成算法参考资料1:https://blog.csdn.net/Rivalsx/article/details/97448943

    ★ 列生成算法参考资料2:https://blog.csdn.net/u014090505/article/details/89019327


    作者|陈怡敏、曹贵玲
    责编|何洋洋
    审核|徐小峰 

    展开全文
  • 列生成(Column Generation)算法

    千次阅读 2021-05-11 20:57:49
    列生成算法的背景 多年来,寻找大规模的、复杂的优化问题的最优解一直是决策优化领域重要的研究方向之一。 列生成算法通常被应用于求解大规模整数规划问题的分支定价算法(branch-and-price algorithm)中,其理论...

    转载自:https://mp.weixin.qq.com/s/y4rojEP3M8Ow3pLKQUKgLw

    列生成算法的背景

      列生成算法通常被应用于求解大规模整数规划问题的分支定价算法(branch-and-price algorithm)中,其理论基础由Danzig等于1960年提出。当求解一个最小化问题时,列生成算法主要的作用是为每个搜索树节点找到一个较优的下界(lower bound)本质上而言,列生成算法就是单纯形法的一种形式,是用来求解线性规划问题的

    列生成算法已被应用于求解如下著名的NP-hard优化问题:机组人员调度问题(Crew Assignment Problem)、切割问题(Cutting Stock Problem)、车辆路径问题(Vehicle Routing Problem)、单资源工厂选址问题(The single facility location problem )等。

    列生成算法的基本思想

      在某些线性优化问题的模型中,约束的数目有限,但是变量的数目随着问题规模的增长会爆炸式的增长,因此不能把所有的变量都显性的在模型中表达出来。在用单纯形法求解这类线性规划问题时,基变量(basic variable)只与约束的个数相关,每次迭代只会有一个新的非基变量(non-basic variable)进基,因此,在整个求解过程中其实只有很少一部分变量会被涉及到。

      简单来说,列生成算法通过求解子问题(pricing problem),来找到可以进基的非基变量,该非基变量在模型中并没有显性的写出来(可以看成是生成了一个变量,每个变量其实等价于一列,所以该方法被称为列生成算法)。如果找不到一个可以进基的非基变量,那么就意味着所有的非基变量的检验数(reduced cost)都满足最优解的条件,也就是说,该线性规划的最优解已被找到,即使很多变量没有在模型中写出来。

    列生成算法实例——板材切割问题(Cutting Stock Problem)

    问题描述

    木材厂卖木材,某顾客需要25根3英尺的木材、20根5英尺的木材和15根9英尺的木材,木材厂通过切17英尺的木材来满足顾客的需求。为了尽量减少木材的浪费,可以用线性规划方法来实现这个目标,同时用列生成来解这个线性规划问题。

    切割方案

    切割过程中,木材厂要确定木材的切割方案(cutting combination)。举例说明,一根17英尺的木材可以切成3根5英尺的,这种切割方案将造成2英尺木材的浪费,实际过程中有很多种可能的切割方案,但是不合理的切割方案不需要被考虑。例如,只把17英尺木材切成一根9英尺,然后扔掉8英尺的方案明显不合理,因为我们可以把它切成一根9英尺、5英尺和3英尺的木材。总的来说,任何一种切割方案浪费木材量超过3英尺,我们都认为是不合理的,因为可以用浪费的木材去获得一根或多根3英尺的木材。不合理的切割方案不会在最优解中出现,因此不需要考虑。根据以上规则,我们可以枚举出以下六种切割方案

    Image

    求解过程

    1. 建立模型

    (1)x_l:    选用第 i 个方案

    (2)等量关系式:

    (3)目标:

    (4)板材切割问题约束:

              

    结合(1)(2)(3)(4)得到最终线性规划模型

    2. 模型求解

                   

         定义第七种切割方法(只切出一个“9英尺”)

                                                              初始基为(x 1,6,7)

         

                                     

            由上到下依次是:目标值z,和 对应尺寸的个数 a3,a5,a9 (分支定价法

             

         找到最大的正检测数,从而找到对应需要进基的变量(x5)

           

        计算需要出基的变量(x7),(保证所有检测数均大于0,选择最小比值)

             

         

                  

         

       

             

            变量值为整数(向上取整,允许适当浪费)

    展开全文
  • 优化|列生成算法及Java调用cplex实现

    千次阅读 2020-12-20 11:47:31
    优化|列生成算法及Java调用cplex实现Cutting Stock ProblemColumn Generation AlgorithmJava调用cplex实现CG算法 Cutting Stock Problem 本文中的课件来自清华大学深圳国际研究生院,物流与交通学部张灿荣教授...
  • 单纯形法和列生成算法解释

    千次阅读 2019-10-04 15:32:00
    单纯形法是求解线性规划代表性的算法。其基于这么样的一个事实:线性规划是在凸集上的凸优化问题,因此其局部最优解也是全局最优解。而这些局部最优解是会出现在该凸集的顶点上,所以单纯形法的思路就是在这些顶点上...
  • 列生成算法求解矩形下料问题(Matlab代码)

    千次阅读 多人点赞 2020-04-04 14:35:02
    ) 说到Dantzig-Wolfe分解,不得不提的就是列生成算法,最早用来解决一维下料问题(cutting stock problem)。但一维下料问题似乎太乏味了,怕学生们提不起兴趣,这里就找了一篇解决矩形下料问题的文章,复现了一下...
  • 第一部分主要讲cutting stock问题的定义,以及如何用列生成算法解决cutting stock问题。 一. cutting stock问题的定义 问题描述:有一批钢管数量为 N,长度都为 L;假设m个顾客,来钢厂下订单,每位顾客需要长度为...
  • 基于Cplex的列生成技术

    千次阅读 2021-01-15 17:15:36
    首先介绍一下什么列生成列生成技术是一种求解大型线性规划问题的技术,广泛应用于机组人员调度问题、切割问题、车辆路径规划问题。以上问题有一个共同点,即小规模的问题可以直接使用线性规划进行求解,但是对于...
  • 该方法的特点是 在每一步列生成算法的迭代中,通过机器学习训练出一个模型来生成新的列(选择一个变量的子集添加到主问题构成新的一列)。该方法通过选择最合适的列来降低主问题的计算时间。我们在带有时间窗约束的...
  • 目录 1 CSP问题与模型 2 列生成方法理论 3 Cplex OPL演示列生成迭代过程 4 多种长度木材的例子 5 java实现代码
  • 行生成算法与列生成算法 其实行生成算法(Row Generation/Constraint Generation)与列生成算法(Column Generation)单独的算法解释是有的: “行生成,列生成”学习笔记 浅析constraint generation(约束生成,...
  • 这篇博文主要是想记录一下我这几天的工作心得。...标题中的约束生成或者行生成是我自己翻译的,可能存在误差(单纯形法中用一行表示一个约束)。前人提出这个算法的主要原因是因为有的问题约束特别多,例...
  • 雪花算法:分布式唯一ID生成利器

    千次阅读 2022-02-23 09:12:59
    前言 无论是在分布式系统中的ID生成,还是在业务系统中请求流水号这一类唯一...市面上比较常见的分布式ID生成算法及类库: UUID:Java自带API,生成一串唯一随机36位字符串(32个字符串+4个“-”)。可以保证唯一性,但
  • 首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样...
  • 解决单幅图像中的人群遮挡和尺度变化问题,提出一种基于多卷积神经网络的人群计数算法。利用具有不同尺寸感受野的卷积神经网络(CNN)和特征注意力模块自适应提取多尺度人群特征,引入可变形卷积增强CNN网络空间...
  • 盘点数独终盘生成算法

    千次阅读 2018-07-20 12:29:32
    数独难玩,那设置数独题目容易吗?为了讲解方便,先给数独的九宫格下一个定义,如下图所示,将数独分为9个九...如要构思一个生成数独题目的程序,应该从哪里入手呢?这里有两种方案:方案一,提前设置好数独库,将题...
  • 迷宫随机生成算法Python实现

    千次阅读 2021-01-30 00:09:47
    最近在B站看到一个关于迷宫随机生成算法的视频《从迷宫生成算法到创意编程》,受到启发,就用刚学的Python语言尝试实现了一下,代码只是模拟算法生成的过程,还没有把迷宫可视化,不过只要解决了算法问题,其余都...
  • 列生成学习笔记

    千次阅读 2020-02-05 22:05:33
    列生成算法解决大规模线性规划的一种算法。 头两年一直没搞明白列生成算法原理及应用(啥都别说了,我知道我笨),最近重新学习的时候发现网上简单明了的资料多了起来(干货 | 10分钟带你彻底了解column ...
  • 算法实验-贪心算法解决背包问题

    千次阅读 2020-02-03 14:26:01
    #贪心算法,每次找到价值最大的放进去,可以拆分 import time def bag ( c , a ) : value = 0 i , j = 0 , 0 for k in sorted ( a , key = a . __getitem__ , reverse = True ) : if ( int ...
  • 运筹系列8:Set partitioning问题的列生成方法

    万次阅读 多人点赞 2018-08-15 22:32:47
    列生成算法是不断添加求解变量的算法,可参考论文。列生成算法常常用于如下的场景:使用set-covering构建的模型,变量非常多,约束相对较少。 具体来说,场景如下:有nnn个0-1变量z1...znz1...znz_1...z_n,每个...
  • 数独的生成算法和解题算法

    万次阅读 2018-06-10 11:43:57
    数独解题与出题算法一、基于递归回溯法的数独解题算法思路:众所周知,数独一般的解法需要用到很多次的推导,对各行各各个九宫格进行排查,删选候选数后挑选候选数最少的去填。仿照这样的思想,我们用C++模拟这样...
  • 目录 一、引言 二、背景 三、检测 四、发展 ...恶意软件如今已经发展为威胁网络安全的头号...对应地,针对DGA算法的研究现在也是安全圈讨论的热点话题,学术界和工业界也有大量DGA域名检测的工作,但是在实际使用中存
  • A*算法解决八数码难题

    千次阅读 2021-01-21 23:01:47
    基于状态空间表示法的搜索算法解决八数码难题 本文的pdf文件链接:link 一、问题重述 1.1 背景介绍        如今处于人工智能和大数据时代,每天都有成千上万的数据产生,而我们...
  • 算法遇上进化论
  • 使用遗传算法解决图着色问题

    万次阅读 2021-01-04 11:05:09
    在图论中,图是对象的结构化集合,用于表示对象对之间的关系。对象在图中表示为顶点(或节点),而一对对象之间的关系使用边表示。图是非常有用的对象,因为它们可以用于表示大量的现实...使用遗传算法解决图着色问题。
  • Prim算法和Kruskal算法:都是解最小生成树问题的贪心算法;它们做贪心选择的方式不同,但都利用了下面的最小生成树性质。 最小生成树性质: 设G=(V,E)是连通带权图,U是V的真子集。 如果(i,j)
  • Python:遗传算法解决八皇后问题

    千次阅读 多人点赞 2020-12-06 23:20:11
    文章目录1 八皇后问题2 遗传算法简介2.1 遗传算法的流程图2.2 遗传算法的详细步骤3 思想过程4 我的程序4.1 程序14.2 程序24.3 程序35 评价 1 八皇后问题 有一个8乘8的棋盘,现在要将八个皇后放到棋盘上,满足:对于...
  • Python实现最小生成树--Prim算法和Kruskal算法

    千次阅读 热门讨论 2020-06-21 21:01:22
    Python实现最小生成树–Prim算法和Kruskal算法 文章目录Python实现最小生成树--Prim算法和Kruskal算法前言设计需求分析系统设计系统实现Prim算法Kruskal算法功能介绍测试数据及代码测试数据完整代码参考文章 前言 ...
  • 1、算法简介 禁忌搜索算法TS(Tabu search),顾名思义核心在于“禁忌”,简单来说就是在某一个过程中把一些不太好的操作给禁止了,直到搜索到一个“最优秀”的。它是在1986年由美国Fred Glover教授提出的,主要是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 169,624
精华内容 67,849
关键字:

列生成算法解决什么