精华内容
下载资源
问答
  • 列生成算法ppt

    2018-07-23 12:35:22
    列生成算法的讲解,主要运用cut-stock-problem来说明其具体的运用
  • 这是国外一篇有关列生成算法相关的topic的介绍,个人认为对于学习列生成算法的人来说很有用。 这是国外一篇有关列生成算法相关的topic的介绍,个人认为对于学习列生成算法的人来说很有用。
  • cutting stock 问题; 原始整数规划模型; 列生成算法


    本文以 cutting stock 问题为例,介绍列生成算法的数学模型。


    1. 问题描述

    长板长度:10m
    子板需求:2m: 100; 3m: 50; 5m: 20 …
    优化目标:最小化,长板切割总数

    2. 原始整数规划模型


    模型参数
    参数 含义
    NN 子板集合
    lil_{i} 子板 ii 的长度
    LL 长板长度

    决策变量
    变量 类型 含义
    xi,jx_{i, j} 0-1 子板 ii 是否在长板 jj

    约束条件

    (1) 分配
    jNxi,j=1iN \sum_{j \in N} x_{i, j} = 1 \quad \forall i \in N

    (2) 长板长度
    iNxi,jliLjN \sum_{i \in N} x_{i, j} \cdot l_{i} \leq L \quad \forall j \in N

    (3) 中心子板
    xi,jxj,jiNjN x_{i, j} \leq x_{j, j} \quad \forall i \in N \quad \forall j \in N

    (4) 有效不等式:需求量下限
    jNxj,jiNliL \sum_{j \in N} x_{j, j} \geq \lceil \frac {\sum_{i \in N} l_{i}} L \rceil


    目标函数

    maxjNxj,j max \quad \sum_{j \in N} x_{j, j}

    3. 列生成算法


    3.1 流程图

    列生成算法流程图

    3.2 限制主问题(restricted master problem)

    模型参数
    参数 含义
    II 所有子板类型的集合
    MM 所有切割方案的集合
    ai,ja_{i, j} 方案 jj 中类型 ii 的子板数量
    did_i 类型 ii 的子板需求量
    决策变量
    变量 类型 含义
    sjs_{j} R+0R_{+}^{0} 按照方案 jj 切割的长板数量
    约束条件

    jMai,jsjdiiI \sum_{j \in M} a_{i, j} \cdot s_{j} \geq d_{i} \quad \forall i \in I

    目标函数

    minjMsj min \quad \sum_{j \in M} s_{j}

    3.3 主问题的对偶问题(dual problem)

    决策变量
    变量 类型 含义
    yiy_{i} R+0R_{+}^{0} 对偶变量
    约束条件

    iIai,jyi1jM \sum_{i \in I} a_{i, j} \cdot y_{i} \leq 1 \quad \forall j \in M

    目标函数

    maxiIdiyi max \quad \sum_{i \in I} d_{i} \cdot y_{i}

    3.4 价格子问题(sub-problem)

    决策变量
    变量 类型 含义
    aia_{i} Z+0Z_{+}^{0} 当前方案中,类型 ii 的子板数量
    约束条件

    iIailiL \sum_{i \in I} a_{i} \cdot l_{i} \leq L

    目标函数

    min1iIaiyi min \quad 1 - \sum_{i \in I} a_{i} \cdot y_{i}

    3.5 其他

    (1)列生成算法需要一组初始可行解启动,获取初始解的启发式方法因问题而异。

    (2)列生成循环过程中,主问题为松弛问题,即变量为连续变量;求得最终结果的是主启发式模型,将主问题变量改为整数变量即可。


    4. 算例对比


    算例1

    长板长度:10m
    子板需求:1m: 100; 2m: 80; 3m: 70; 5m: 50; 7m: 30; 8m: 10

    算例2

    长板长度:20m
    子板需求:1m: 1000; 2m: 500; 3m: 200; 5m: 200; 8m: 100; 10m: 200; 12m: 100; 15m: 150

    运行结果
    算例 模型/算法 求解结果 求解时间
    1 原始整数规划模型 101 24.13
    1 列生成算法 102 22.161
    2 原始整数规划模型 587 1200 +
    2 列生成算法 493 22.431

    注:
    (1)求解器:Gurobi 服务器
    (2)时间限制:1200s
    (3)算例1的最优解:101


    展开全文
  • 博客目录序题目模型建立代码运行结果列生成算法-初始方案列生成算法-第一次迭代列生成算法-第2次迭代列生成算法-第13次迭代列生成算法-第14次迭代列生成算法-取整列生成算法-装载方案详情及每阶段目标值 序 在国内外...

    在国内外疫情的大环境下,直播上课已经是第十周了。按学校规定,对《运筹学》课程安排了期中考试。在设计考试题目的时候,引用了《运筹学 原书第2版》Ronald L.Rardin.“Optimization in Operations Research”. 2nd Edition中书后练习题.13-2 (第十三章介绍的是大规模优化方法)

    题目

    医疗救助中心ERNow正在为小型直升机设计航班,这些小型直升机将用于向受到飓风影响的人们配送医疗、食品和住房物资。下表给出了不同物资重量占飞机可承载重量wiw_i的比列和容量占集装箱容量viv_i的比例。

    i 物资 重量wiw_i 容量viv_i 需求量qiq_i
    1 紧急救助补给 0.04 0.10 30
    2 饮用水 0.20 0.14 20
    3 柴油发电机 0.40 0.24 12
    4 发电机燃油 0.28 0.32 23
    5 帐篷 0.10 0.28 15
    6 检测设备 0.16 0.24 30
    7 毛毯 0.03 0.18 40
    8 雨衣 0.08 0.14 25

    ERNow希望用尽可能少的航班配送次数满足所有物资的需求。

    模型建立

    符号声明:
    xjx_j 表示装载组合jj的运送次数;
    aija_{ij} 表示在第jj个装载组合中物资ii的数量。
    建立受限主问题模型(Restricted Master Problem, RMP):

    minz=jxj\min z=\sum_{j}x_j

    s.t.s.t.

    jaijxjqi,i\sum_ja_{ij}x_j \ge q_i,\forall i

    xj0,jx_j \ge 0, \forall j

    πi\pi_i表示物资ii对应的对偶变量值,则可写出其列生成子问题模型(Sub-Problem, SP):

    minw=1iπiyi\min w=1-\sum_i\pi_iy_i

    s.t.s.t.

    iwiyi1\sum_i w_iy_i \le 1

    iviyi1\sum_i v_iy_i \le 1

    yi0,iy_i \ge 0, \forall i

    代码

    在Microsoft Visual Studio 2013 C++编辑环境下,调用cplex 12.61,实现求解。

    #include <ilcplex/ilocplex.h>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <time.h>
    
    ILOSTLBEGIN
    
    #define RC_EPS 1.0e-6
    
    static void report1(IloCplex& RescueSolver, IloNumVarArray Rescue,
    	IloRangeArray Require);
    static void report2(IloAlgorithm& SchemeSolver,
    	IloNumVarArray Supply,
    	IloObjective obj);
    static void report3(IloCplex& RescueSolver, IloNumVarArray Rescue);
    
    void main()
    {
    	clock_t start_time = clock();
    	IloEnv env;
    	try{
    		//Instance Data
    
    		IloInt num = 8;
    		IloNumArray weight(env, num, 0.04, 0.2, 0.4, 0.28, 0.1, 0.16, 0.03, 0.08),
    			volume(env, num, 0.1, 0.14, 0.24, 0.32, 0.28, 0.24, 0.18, 0.14),
    			demand(env, num, 30, 20, 12, 23, 15, 30, 40, 25);
    
    		//Rescue-Optimization Problem 
    
    		IloModel RescueOpt(env);
    		IloObjective   CoptersUsed = IloAdd(RescueOpt, IloMinimize(env));
    		IloRangeArray  Require = IloAdd(RescueOpt, IloRangeArray(env, demand, IloInfinity));
    		IloNumVarArray Rescue(env);
    
    		for (int j = 0; j < num; j++){
    			Rescue.add(IloNumVar(CoptersUsed(1) + Require[j](min(int(1 / weight[j]), int(1 / volume[j])))));
    		}
    
    		IloCplex RescueSolver(RescueOpt);
    
    		// Scheme-Generation Problem
    
    		IloModel SchemeGen(env);
    		
    		IloObjective ReducedCost = IloAdd(SchemeGen, IloMinimize(env,1));
    		IloNumVarArray Supply(env, num, 0, IloInfinity, ILOINT);
    		SchemeGen.add(IloScalProd(weight, Supply) <= 1);
    		SchemeGen.add(IloScalProd(volume, Supply) <= 1);
    
    		IloCplex SchemeSolver(SchemeGen);
    
    		// Column-Generation Procedure
    
    		IloNumArray price(env, num);
    		IloNumArray newScheme(env, num);
    
    		for (;;){
    			// Optimize over current schemes
    			RescueSolver.solve();
    			report1(RescueSolver, Rescue, Require);
    
    			// Find and add a new scheme
    
    			for (int i = 0; i < num; i++){
    				price[i] = -RescueSolver.getDual(Require[i]);
    			}
    			ReducedCost.setLinearCoefs(Supply, price);
    
    			SchemeSolver.solve();
    			report2(SchemeSolver, Supply, ReducedCost);
    
    			if (SchemeSolver.getValue(ReducedCost)>-RC_EPS) break;
    
    			SchemeSolver.getValues(newScheme, Supply);
    			Rescue.add(IloNumVar(CoptersUsed(1) + Require(newScheme)));
    		}
    		
    		RescueOpt.add(IloConversion(env, Rescue, ILOINT));
    		RescueSolver.solve();
    		cout << "Solution status: " << RescueSolver.getStatus() << endl;
    		report3(RescueSolver, Rescue);
    	}
    	catch (IloException& ex) {
    		cerr << "Error: " << ex << endl;
    	}
    	catch (...) {
    		cerr << "Error" << endl;
    	}
    
    	env.end();
    	clock_t finish_time = clock();
    	cout << "Computing time: " << (finish_time - start_time) / 1000 << "seconds" << endl;
    	system("pause");
    }
    
    
    static void report1(IloCplex& RescueSolver, IloNumVarArray Rescue,
    	IloRangeArray Require)
    {
    	cout << endl;
    	cout << "Using " << RescueSolver.getObjValue() << " copters" << endl;
    	cout << endl;
    	for (IloInt j = 0; j < Rescue.getSize(); j++) {
    		cout << "  Rescue" << j << " = " << RescueSolver.getValue(Rescue[j]) << endl;
    	}
    	cout << endl;
    	for (IloInt i = 0; i < Require.getSize(); i++) {
    		cout << "  Require" << i << " = " << RescueSolver.getDual(Require[i]) << endl;
    	}
    	cout << endl;
    }
    
    static void report2(IloAlgorithm& SchemeSolver, IloNumVarArray Supply,
    	IloObjective obj)
    {
    	cout << endl;
    	cout << "Reduced cost is " << SchemeSolver.getValue(obj) << endl;
    	cout << endl;
    	if (SchemeSolver.getValue(obj) <= -RC_EPS) {
    		for (IloInt i = 0; i < Supply.getSize(); i++)  {
    			cout << "  Supply" << i << " = " << SchemeSolver.getValue(Supply[i]) << endl;
    		}
    		cout << endl;
    	}
    }
    
    static void report3(IloCplex& RescueSolver, IloNumVarArray Rescue)
    {
    	cout << endl;
    	cout << "Best integer solution uses "
    		<< RescueSolver.getObjValue() << " copters" << endl;
    	cout << endl;
    	for (IloInt j = 0; j < Rescue.getSize(); j++) {
    		cout << "  Rescue" << j << " = " << RescueSolver.getValue(Rescue[j]) << endl;
    	}
    }
    

    运行结果

    列生成算法-初始方案

    此时主问题最优目标值为44.7381,即需要使用44.7381架次直升机运输物资:
    在这里插入图片描述
    其中初始方案(Rescue i, i=0,…,7)分别为只满载运送第i+1种物资的情况。

    Rescue2 = 6 表示
    最优解中 只满载运送第3种物资的运输方案 使用了6次。

    列生成算法-第一次迭代

    此时主问题最优目标值为41.480952,即需要使用41.480952架次直升机运输物资:
    在这里插入图片描述
    在这里插入图片描述

    列生成算法-第2次迭代

    此时主问题最优目标值为40.1,即需要使用40.1架次直升机运输物资:
    在这里插入图片描述

    列生成算法-第13次迭代

    此时主问题最优目标值为38.14,即需要使用38.14架次直升机运输物资:
    在这里插入图片描述

    列生成算法-第14次迭代

    子问题已经找不到检验数小于0的装载方案,迭代终止。
    在这里插入图片描述

    列生成算法-取整

    这里就简单对已找到的方案寻找最优组合。整个列生成算法的总用时为2秒。
    在这里插入图片描述

    列生成算法-装载方案详情及每阶段目标值

    装载方案编号 1 2 3 4 5 6 7 8 线性松弛主问题目标值
    0 10 0 0 0 0 0 0 0 -
    1 0 5 0 0 0 0 0 0 -
    2 0 0 2 0 0 0 0 0 -
    3 0 0 0 3 0 0 0 0 -
    4 0 0 0 0 3 0 0 0 -
    5 0 0 0 0 0 4 0 0 -
    6 0 0 0 0 0 0 5 0 -
    7 0 0 0 0 0 0 0 7 44.7381
    8 0 0 2 0 0 0 2 1 41.480952
    9 0 4 0 0 1 0 0 1 40.100000
    10 0 0 0 0 3 0 0 1 39.623810
    11 1 0 0 0 0 0 5 0 39.063810
    12 0 2 0 0 0 3 0 0 38.706667
    13 0 0 0 0 0 2 0 2 38.706667
    14 0 0 0 2 0 0 2 0 38.400000
    15 2 0 2 0 0 0 1 1 38.280000
    16 3 3 0 0 1 0 0 0 38.205000
    17 2 0 0 0 2 1 0 0 38.204762
    18 0 0 0 0 1 0 3 0 38.178571
    19 2 0 1 0 2 0 0 0 38.175497
    20 2 0 1 0 0 0 0 3 38.140000
    展开全文
  • 该代码文件是一个完整... 包含了问题说明、数据、详细的gurobi列生成算法求解代码,是一份完整的航班人员调度分配、列生成算法、gurobi求解器的绝佳学习资料。所有代码均有详细注释,已经经过反复调试,可以直接运行。
  • 从一维cutting问题看列生成算法列生成算法一维cutting问题新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容...

    列生成算法

    列生成在求解大型线性规划时往往都表现良好,在很多时候,一个变量很多的线性规划问题中,往往很多的列是用不到的,或者说,它们并不影响最优解的求解。列生成正是基于这样一种思想,从有限列出发,每次在求解限制问题后,判断是否达到最优,若达到,则返回结果,否则,添加新的列,继续求解,直到求出最优解为止。
    本文将从列生成原理的证明,基于一维cutting问题的步骤说明和python代码实现来详细讲解列生成算法。同时比较该问题的几种模型在gurobi求解下的速度和解的质量。

    一维cutting问题

    一维cutting问题可以描述为:假设有无限多的长度为LL的木板和nn种类型的需求,第ii (ii=1,…,nn)类型需求的尺寸为lil_i,需求数量为did_i,设M={1,2,...,m}M=\{1,2,...,m\}N={1,2,...,n}N=\{1,2,...,n\}试求如何选择下料方式,在满足需求的情况下,使得使用的木板(board)数目最少
    在进一步说明列生成之前,我们先看一维cutting问题的相关模型描述比较不同模型求解的效率。

    该问题的模型建立是简单的,在建立第一个模型之前,我们先定义相关的决策变量:
    yj=1y_j=1 如果第jj个木板被使用,否则yj=0y_j=0yj{0,1}y_j \in \{0,1\};
    xijx_{ij} 代表来自第jj个木板的第ii中类型需求的数量,xijNx_{ij}\in\N.

    modelmodel 1:1:
    minjMyjmin\sum\limits_{j\in M}y_j (1)

    s.t. Iyjxij,iN,jMIy_j\ge x_{ij},i\in N,j\in M (2)

    jMlixijL,jM\sum\limits_{j\in M}l_ix_{ij}\le L,j\in M (3)

    iNxijdi,iN\sum\limits_{i\in N}x_{ij}\ge d_i, i\in N (4)

    公式(1)定义了问题的目标,即使用的board数量最少,显然,II是一个充分大的数,且m=iNdim=\sum\limits_{i\in N}d_i显然是该问题的一个上界。当然,mm取值越大意味着更多的决策变量,而实际上,任何一种启发式方法或者可行方案下使用的board数目都是该问题的一个可行上界。而在该问题中,我们取简单上界m=iNdiLlim=\sum\limits_{i \in N}{\left\lceil \frac{d_i}{\left\lfloor \frac{L}{l_i} \right\rfloor} \right\rceil}。公式(2)限制了当yj=0y_j=0时,即第jj个board不被使用时,xij=0x_{ij}=0。其中,II是一个充分大的常数,因此当yj=0y_j=0时,对xijx_{ij}不作约束。公式(3)限制了从board jj上切下的物品尺寸总和不能超过baord的总长LL。公式(4)则表示相应的需求约束。

    我们通过一个实例的求解来说明下这个模型的求解效率,我们设L=110L=110,考虑5种不同的需求如下表所示。

    尺寸lil_i 20 45 50 55 75
    需求did_i 48 35 24 10 8

    将数据代入模型1,python编程,调用gurobi求解得到的结果为OPT=47OPT=47,时间runtime=30.3sruntime=30.3s.
    进一步地,我们用该模型的松弛形式,即松弛 0yj10 \le y_j \le 1xij0x_{ij} \ge 0 代替model 1中的决策变量约束来估计该问题的下界。得到OPT=0.048OPT=0.048,时间runtime=0.009sruntime=0.009s下界的意义之一在于:随着求解规模的增大,当一个模型的求解时间是呈指数增长时,我们往往会选择一些启发式算法或智能算法来求解相应的问题。因此,此时可以用下界来评价一个算法的有效性(effectiveness),而当你提供一个足够好的下界,而你启发式算法的求解结果和下界差距足够小时,即可以说明你的算法能求解出足够好的近似优解。显然,第一个模型的松弛模型的下界足够差。因为我们可以很简单地得到该问题的一个连续下界
    lowerbound=iNdiliL(5)lowerbound=\left\lceil \frac{\sum\limits_{i \in N}{d_il_i}}{L} \right\rceil (5).
    且通过公式(5)我们可以求得的该实例的下界为45.

    很多时候,模型建立的不同可能会对求解效率产生很大的影响,基于model 1,建立新的cutting模型,如下所示。

    modelmodel 2:2:
    minjMyjmin\sum\limits_{j\in M}y_j (6)

    s.t. jMlixijLyj,jM\sum\limits_{j\in M}l_ix_{ij}\le Ly_j,j\in M (7)

    iNxijdi,iN\sum\limits_{i\in N}x_{ij}\ge d_i, i\in N (8)

    该模型进行了简单的调整,经过求解器求解,我们可以得到OPT=47OPT=47,时间runtime=8sruntime=8s. 而对应的松弛模型runtime=0.003sOPT=44.41runtime=0.003s,OPT=44.41。实际上,我们可以发现,该线性模型求解得结果和公式(5)求解结果是相同的,在其对应的松弛问题中,我们可以定义yjy_j为board jj 使用的比例 0yj10 \le y_j \le 1,从这个角度上来看,它和公式(5)的原理是一致的。

    同时,从这里我们可以看出,建立不同的数学模型,可能会极大地影响模型的求解效率。

    列生成原理

    首先考虑一个目标为极小值的线性规划模型PP 如下所示

    min z=cTxz=c^Tx
    (P)(P) {Axbx0(9)\left\{ \begin{array}{l} Ax \ge b \\ x \ge 0 \end{array} \right. (9)

    其中,AAm×nm \times n的二维矩阵,c,xc,x 均为n×1n \times 1的列向量,bbm×1m \times 1的列向量。设A~\tilde Am×nm \times n'的二维矩阵,且nnn' \le nA~\tilde A中列向量为AA中列向量的子集,则我们可以定义相应的限制问题RPRP如下所示

    min z=cTxz=c'^Tx'
    (RP)(RP) {A~xbx0(10)\left\{ \begin{array}{l} \tilde Ax' \ge b \\ x' \ge 0 \end{array} \right. (10)

    模型(P)(P)和模型(RP)(RP)的对偶问题DPDPDRPDRP可以表示如下:

    max w=yTbw=y^Tb
    (DP)(DP) {ATycy0(11)\left\{ \begin{array}{l} A^Ty \le c \\ y \ge 0 \end{array} \right. (11)

    max w=yTbw=y^Tb
    (DRP)(DRP) {A~Tycy0(12)\left\{ \begin{array}{l} \tilde A^Ty \le c' \\ y \ge 0 \end{array} \right. (12)

    由强对偶性可知,如果(RP)(RP)的最优解是PP的最优解,当且仅当DRPDRP的最优解是DPDP的最优解。此时,由于DRPDRP的行(即约束)是RPRP的行的子集,从另一方面理解,RPRP问题的解空间是DRPDRP的解空间的子集。因此,若DRPDRP问题的最优解满足DPDP的所有约束,则DRPDRP的最优解即为RPRP问题的最优解。

    综上所述,当求出RPRP的最优解xx'^*时,要判断其是否是PP的最优解xx^*,则需要判断DRPDRP模型最优解yy^*是否满足DPDP中的所有约束。设aia_i为系数矩阵AA中的列向量,则模型DPDP可以重新写为:

    max w=yTbw=y^Tb
    (DP)(DP) {aiTyci,i=1,2,...,ny0(13)\left\{ \begin{array}{l} a_i^Ty \le c_i,i=1,2,...,n \\ y \ge 0 \end{array} \right. (13)

    因此,若yy^*DPDP的最优解,即满足DPDP的所有约束,则应该aiTyci,i=1,2,...,na_i^Ty^* \le c_i,\forall i=1,2,...,n。判断yy^*是否满足(13)(13)中的所有约束,等价于求解(14)(14)

    (14)(14)
    min z=ciaiTyz=c_i-a_i^Ty^*
    aiAa_i \in A

    如果我们求解该问题w0w^* \ge 0,即i,aiTyci\forall i, a_i^Ty^* \le c_i,此时yy^*即为DPDP的最优解。若w<0w^* \lt 0,则应添加相应的aia_{i^*},继续求解,直到w0w^* \ge 0为止。

    集合覆盖模型

    该部分建立该问题的集合覆盖(set-covering model),如下所示:

    min jPxj\sum\limits_{j \in P}{x_j}

    {jPnjixjdi,iNxjN,jP(15)\left\{ \begin{array}{l} \sum\limits_{j \in P}n_{ji}x_j \ge d_i,i \in N\\ x_j \in N,j \in P \end{array} \right. (15)

    其中,PP为所有可行的切割方式(pattern)(pattern)njin_{ji}为pattern jj中第ii中类型需求的数量,xjx_j为pattern jj的使用数目。

    但是事实上,实现罗列出来所有可行的pattern 是不可行的,而往往在最优解中使用到的pattern的数量一般是远远小于总的pattern数量的。因此,借鉴列生成的思路,从有限列(即限制问题RPRP)出发,经过不断的迭代,每次判断当前有限列是否达到最优,若达到,返回当前最优解;否则,添加列,直至达到最优为止。其流程图如下所示。

    Created with Raphaël 2.2.0开始求解RP求解定价子问题reduced cost < 0?添加列至RP结束yesno

    列生成步骤说明

    本部分通过一维cutting问题的实例详细说明该问题的求解步骤。
    设初始集合覆盖模型系数矩阵为:

    n=[5000002000002000002000001]n = \left[ {\begin{array}{l} 5&0&0&0&0 \\ 0&2&0&0&0 \\ 0&0&2&0&0 \\ 0&0&0&2&0 \\ 0&0&0&0&1 \\ \end{array}} \right]

    如第1列n1=(5,0,0,0,0)Tn_1=(5,0,0,0,0)^T代表的切割方式表示第一种类型需求为5,其余为0,因为Ll1=5\left\lfloor \frac{L}{l_1} \right\rfloor = 5,其余列以此类推。

    事实上,建立一个这样的初始求解系数矩阵,能保证问题始终存在可行解。

    iteriter 1:求解限制问题RPRP,x=(9.6,17.5,12,5,8)Tx^*=(9.6, 17.5, 12, 5, 8)^T,对应的对偶变量π=(0.2,0.5,0.5,0.5,1.0)T\pi=(0.2, 0.5, 0.5, 0.5, 1.0)^T,求解定价子问题:

    min z=1yTπz=1-y^T\pi

    {iNyiljLyiN\left\{ \begin{array}{l} \sum\limits_{i \in N}y_il_j \le L\\ y_i \in N \end{array} \right.

    yiy_i表示在该可行的patern中第ii中类型需求的数目,则y=(1,2,0,0,0)Ty^*=(1,2,0,0,0)^Tz=0.2<0z^*=-0.2 \lt 0,因此添加(1,2,0,0,0)T(1,2,0,0,0)^T到原问题系数列,继续求解;

    iteriter 2: 求解新的RPRP问题,x=(6.1,012,5,817.5)Tx^*=(6.1, 0,12, 5, 8, 17.5)^T,对应的对偶变量π=(0.2,0.4,0.5,0.5,1.0)T\pi=(0.2, 0.4, 0.5, 0.5, 1.0)^T,求解定价子问题,y=(1,0,0,0,1)Ty^*=(1,0,0,0,1)^Tz=0.2<0z^*=-0.2 \lt 0,因此添加(1,0,0,0,1)T(1,0,0,0,1)^T到原问题系数列,继续求解;

    iteriter 3: 求解新的RPRP问题,x=(4.5,012,5,0,17.5,8)Tx^*=(4.5, 0,12, 5, 0, 17.5, 8)^T,对应的对偶变量π=(0.2,0.4,0.5,0.5,0.8)T\pi=(0.2, 0.4, 0.5, 0.5, 0.8)^T,求解定价子问题,y=(3,0,1,0,0)Ty^*=(3,0,1,0,0)^Tz=0.1<0z^*=-0.1 \lt 0,因此添加(3,0,1,0,0)T(3,0,1,0,0)^T到原问题系数列,继续求解;

    iteriter 3: 求解新的RPRP问题,x=(0,0,8.25,5,0,17.5,8,7.5)Tx^*=(0, 0, 8.25, 5, 0, 17.5, 8, 7.5)^T,对应的定价子问题z>0z^* \gt 0,结束循环,输入最优解46.25;

    由上述问题可以看到,对列生成求解的下界向上取整,其值和最优解相等。因为,集合覆盖模型往往能获得一个更好的下界,因为一般来说,集合覆盖模型的可行解是原问题的可行解,而原问题的可行解不一定是结合覆盖模型和可行解。

    python 代码实现

    本博客所有涉及模型实现和列生成算法为python调用gurobi编写,相关代码链接可见 https://github.com/shaoxiang-zheng/operation-algorithm.git

    展开全文
  • 优化|列生成算法及Java调用cplex实现Cutting Stock ProblemColumn Generation AlgorithmJava调用cplex实现CG算法 Cutting Stock Problem 本文中的课件来自清华大学深圳国际研究生院,物流与交通学部张灿荣教授...

    Cutting Stock Problem

    本文中的课件来自清华大学深圳国际研究生院,物流与交通学部张灿荣教授《高级运筹学》课程。

      列生成算法的引入,让我们从一个经典的问题开始,即下料问题(Cutting Stock Problem)。
    在这里插入图片描述
      假设有某家公司售卖3种尺寸分别为3-ft、5-ft和9-ft的产品,3种产品的需求量分别为25、20和15。那么这家公司该如何在满足其需求的前提下,通过切割一条17-ft的木板,最大程度地减少浪费呢。
    在这里插入图片描述
    我们当然可以手动推导一些方案出来,如上图所示就有6种不同的方案。对于以有的方案,我们可以按以下的方式建立模型:
    在这里插入图片描述

    这里可以思考一个问题,模型中每一列的xix_i在每一行约束中对应系数的物理意义是怎样的?

    但是如果候选方案的数量巨大,那么约束的长度会很长,甚至没有办法去罗列出所有的切割方案。

    Column Generation Algorithm

      为了解决类似CSP的问题,学者们提出了一种解决大规模线性规划的算法:列生成算法。
    通常求解线性规划的方法为单纯形法,对于单纯形法来说,有:
    xBT=B1bTB1NxNT x_B^T=B^{-1}b^T-B^{-1}Nx_N^T

    z=cBB1bT+(cNcBB1N)xNT z=c_BB^{-1}b^T+(c_N-c_BB^{-1}N)x_N^T
      在传统的方法下,每一列NjNN_j \in N,都会调用cjcBB1Nc_j-c_BB^{-1}N来选择一列NjN_j^*,它对应于具有最大负值的非基本变量xjx_j^*。这是一种枚举的方法,如果非基本变量的规模很大,那么计算工作量就会很大。那么该怎样简化这个枚举的过程呢?
      从上面的模型可以观察到,每一种切割方案xix_i在每一行约束中对应系数的物理意义为该方案对应切割3种不同尺寸产品的个数。根据这一点就可以对问题做一个转化,来决策一个列NjN_j是怎样。它对应一种切割方案(a1,a2,a3)T(a_1,a_2,a_3)^T,在本文的例子中,它满足3a1+5a2+9a3173a_1+5a_2+9a_3\le 17。此外对于一个最小化问题,在选择入基的决策变量时,要选择最优表中对应检验数最小的决策变量,它能够最大化改进原问题的目标函数,那么找出这个决策变量对应的目标函数即为1cBB1(a1,a2,a3)T1-c_BB^{-1}(a_1,a_2,a_3)^T。那么总结一下,可以通过求解以下的模型来找到一个最优的入基变量:
    min1cBB1(a1,a2,a3)T min 1-c_BB^{-1}(a_1,a_2,a_3)^T

    s.t.   3a1+5a2+9a317 s.t.\ \ \ 3a_1+5a_2+9a_3\le 17

    a1,a2,a30 and integer a_1,a_2,a_3\ge 0 \ and \ integer

    (a1,a2,a3)T(a_1,a_2,a_3)^T即对应一个约束列,因此称为column generation。选择了入基变量之后,再通过xBT=B1bTB1NxNTx_B^T=B^{-1}b^T-B^{-1}Nx_N^T来选择出基变量。

    Java调用cplex实现CG算法

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    感谢大家的阅读,完整project文件请关注公众号并在github获取。下一期会给大家带来CG算法求解Vrptw问题。

    作者:夏旸,清华大学,工业工程系/深圳国际研究生院 (硕士在读)
    欢迎大家关注公众号运小筹。
    在这里插入图片描述

    展开全文
  • 论文研究-多星联合对地观测调度问题的列生成算法.pdf, 多星联合对地观测调度问题作为一类大规模组合优化问题, 其求解算法往往采用启发式或超启发式. 运用列生成思想对该...
  • 作者:高源编者按:本文由传统集合划分优化问题入手,结合工业背景,引入列生成技术在路径优化选择中的运用,并使用经典例子解释特殊结构在列生成算法中的重要使用。一、集合划分问题集合划分问题是组合优化中的一类...
  • 书接上文(MATLAB调用lpsolve的详细介绍帖),...这里还是采用大家学习列生成算法常用的例子来讲述:如何用MATLAB调用lpsolve来编写列生成算法,求解卷纸切割问题。 例子:有16米长的卷纸若干卷,现分别需要3m,6m,7
  • 列生成算法的学习

    2019-11-04 10:14:44
    因此,一般软件用的是barrier method,也就是内点法求解,这个是多项式时间算法,这个算法好像可以很快求解得到最优解的。注意,是好像,没有验证过。 2、继续问题。如果是整数规划的大规模线性规划问题,还是要...
  • 作者:高源编者按:本文由传统集合划分优化问题入手,结合工业背景,引入列生成技术在路径优化选择中的运用,并使用经典例子解释特殊结构在列生成算法中的重要使用。一、集合划分问题集合划分问题是组合优化中的一类...
  • 航班调度问题
  • 参考文献:はじめての列生成法 装箱问题(bin packing problem)我们可以这样定义BPP问题。输入 bin的容量 ,要装入bin的item的集合 ,各个item 的大小 输出 使用最少的bin的数量,把item装到bin里约束 向bin里装的item...
  • excel的列生成算法

    2017-05-24 10:46:00
    * 根据当前号,返回字符 * @param int $i * @return string */ function get_excel_row_name( $i ){ $char1 = floor ( $i / 26 ); $char2 = $i % 26 ; if ( $i % 26 == 0) $char1 -- ; ...
  • 列生成column generation算法,是求解大规模线性规划问题的一种常用算法,在运筹优化领域有着非常广泛的应用。 本篇介绍它的最初形式,原理及应用。 1.最初是为了解决下料问题 即cut-stock problem。这个问题在cplex...
  • 单纯形法是求解线性规划代表性的算法。其基于这么样的一个事实:线性规划是在凸集上的凸优化问题,因此其局部最优解也是全局最优解。而这些局部最优解是会出现在该凸集的顶点上,所以单纯形法的思路就是在这些顶点上...
  • 根据问题特点,使用Danzig-Wolfe策略将这个模型分解为一个带有集划分约束的主问题和一个具有背包特征约束的价格子问题,开发了分支价格算法进行求解。计算结果表明所开发的分支价格算法能够最优求解生产实际问题。
  • 列生成算法求解矩形下料问题(Matlab代码)

    千次阅读 多人点赞 2020-04-04 14:35:02
    ) 说到Dantzig-Wolfe分解,不得不提的就是列生成算法,最早用来解决一维下料问题(cutting stock problem)。但一维下料问题似乎太乏味了,怕学生们提不起兴趣,这里就找了一篇解决矩形下料问题的文章,复现了一下...
  • 俽澔:基于基本最短路径列生成的车辆路径问题​zhuanlan.zhihu.com 注: 上述链接的问题带有时间窗,大家可以自动忽略关于时间的约束 数据 本次使用的数据可参考 master苏:ortools系列:容量约束VRP问题​zhuanlan....
  • 木材下料问题: 原有三种可用木材,长度分别为9,14,16寸,价格分别为5,9,10. 现在需要30块4寸,20块5寸...求解新生成的主问题,直到主问题对应的三个子问题求解出来的redust cost都是负数,表明,当前主问题的解已...
  • 目录 1 CSP问题与模型 2 列生成方法理论 3 Cplex OPL演示列生成迭代过程 4 多种长度木材的例子 5 java实现代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,588
精华内容 635
关键字:

列生成算法