运筹学语言NCL及其工业应用.ppt
《运筹学语言NCL及其工业应用.ppt》由会员分享,可在线阅读,更多相关《运筹学语言NCL及其工业应用.ppt(36页珍藏版)》请在三一文库上搜索。
1、运筹学语言NCL及其工业应用,2000-2008 ENGINEST. All rights reserved.,NCL语言,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,语法分析器(parser):模式识别技术 支持自然建模 支持可视化模型调测及诊断 解算器(solver):混合集合规划 求解实数、整数、布尔值、时间、索引 及集合类型上的混合约束; 支持一阶逻辑、集合推理、数值分析等 求解规则编程(rules) 支持启发式求解策略 支持业务规则:快速构建解决方案,NCL是一门集逻辑、优化及求解规则为
2、一体的智能描述型语言, 支持业务建模和问题求解,独立于领域,跨行业。,2000年国际逻辑编程协会的官方杂志JLP发表 J. Zhou: Introduction to the constraint language NCL. JLP: 45(1-3): 71-103 (2000).,顶级创新企业 法国参议院奖,法国科技创新奖,Solving by Describing,混合集合规划: 超越线性模型的建模,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,混合域(实数、整数、布尔值、索引及集合)上的联合求
3、解系统; 支持一阶逻辑、集合推理、实数域数值分析等。,集合对信息的聚合性(基数、上界、下界、交、并、差、前继、后继) 动态量词逻辑增强模糊推理的能力,支持更强大的问题描述与求解: - “ i A () - i A () - i A xi 基于算法耦合的推理 - NCL有300多种域切割算法; - 算法之间耦合形成网状关系,进一步提升求解能力。,“ i 1,6 xi = O, A 1,6, #A = 2, i A xi = 6,1,3,2,4,6,7,NCL可在预求解(pre-solve)阶段确定 : A = 3, 4 x3 = 2, x4 = 4, x3 + x4 = 6,NCL语言的求解框架
4、,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,约束切割(Constraint Cut)和树搜索(Tree Search),Simpler Smarter Swifter,NCL求解规则,最小化松弛度(Least Slack) 一般来说,松弛度越小,非确定性越小,产生回溯的可能性也越小; 最大化松弛度(Greatest Slack) 域越大,分枝后变化越大, 域切割的扩散性越大。一般来说,很适用于实数变量; 最小化遗憾度(Least Regret) 分枝时分枝点处的搜索准则的差异越大,选枝越容易,回
5、溯时遗憾度越小。 本例中,我们倾向选择这样的order:它距离可能的nextOrder中最近的与次近的 差距最大,即最大化“次小与最小之差”。那么该order相对其他“次小与最小之 差”较小的order,选枝选错的可能性要小,因而该步回溯时遗憾度要小; 顺序性(Ordering Search) 根据一些实际的业务规则选枝搜索以使解空间尽量保持凸性; 贪婪性(Greedy Search) 局部最贪婪地向有利于优化目标的方向选枝搜索。该准则一般用作最后一条。,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter
6、,NCL语言 2000-2008. ENGINEST. All rights reserved,Square Packing: NCL描述建模的例子,将一些小正方形拼成一个大的正方形, 要求任意两个小正方形交集为空且 相邻的正方形间不含间隙。,d = 112, n = 21, i 1, n ( si = , Xi 1, d , Yi 1, d , Xi = xi, xi + (si-1) , Yi = yi, yi + (si-1) , ), i j 1, n Xi Xj = Yi Yj = , i 1, n (min xi) Xi = ? (), i 1, n (min yi) Yi = ?
7、 ().,21个小正方形的边长为: 50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 17, 16, 15, 11, 9, 8, 7, 6, 4, 2。 大正方形的边长为112 。 NCL可以找到符合条件的所有8个解。,所有的小正方形不可以重叠,所以任意两个小正方形的横坐标两两不交或纵坐标两两不交。,来源: C.J. Bouwkamp & A.J.W. Duijvestijn. Catalogue of simple perfect squared Squares of orders 21 through 25. Eindhoven University
8、of Technology, Technical Report 92 WSK 03, The Netherlands, November 1992.,Simpler Smarter Swifter,两两不等与两两不交,“两两不等的整数”与“两两不交的集合”的约束遍布组合优化问题: 整数变量的两两不等 i j 1, n xi xj , 集合变量的互不相交 i j 1, n Ai Aj = ,NCL语言 2000-2008. ENGINEST. All rights reserved,集合覆盖与拼排,Simpler Smarter Swifter,“集合划分”和“拼排”的约束常见于计划与排程问题中
9、: 集合划分 C = i 1, n Ai , i j 1, n Ai Aj = , 二维拼排 i j 1, n xi xj yi yj, i j 1, n xi xj Ai Aj = , i j 1, n Ai Aj = Bi Bj = ,NCL语言 2000-2008. ENGINEST. All rights reserved,整数索引与排序,Simpler Smarter Swifter,整数排序 i 1, n ( xi 1, n, yi = zxi ), i j 1, n ( xi xj , zi zj ),整数递归排序 i 1, n-1 ( xi 2, n , zi zxi ) ,
10、i j 1, n-1 xi xj ,整数索引与排序的算法遍布计算机系统的各级运算中。 整数索引与排序的约束更是NCL语言的基础。,NCL语言 2000-2008. ENGINEST. All rights reserved,集合索引与排序,Simpler Smarter Swifter,集合排序 i 1, n ( xi 1, n, Ai = Bxi ), i j 1, n ( xi xj , Bi Bj ),集合递归排序 “ i 1, n-1 ( xi 2, n , Bi Bxi ) , i j 1, n-1 xi xj ,集合索引与排序的约束是scheduling及routing类问题的基础
11、。,NCL语言 2000-2008. ENGINEST. All rights reserved,求和约束,Simpler Smarter Swifter,变量求和的约束常见于能力(capacity)及背包等类问题: 实数求和 f = i A gi , 整数求和 y = i A xi , 布尔值求和 y = i A ai ,NCL语言 2000-2008. ENGINEST. All rights reserved,累积约束,Simpler Smarter Swifter,二维累积: i D yi = j A (i Cj) xj , 递归累积: i 1, n-1 ( xi 2, n, zxi
12、= z i + wxi ),NCL语言 2000-2008. ENGINEST. All rights reserved,NCL建模举例: Set Partitioning(定义),Simpler Smarter Swifter,给定任务集合TASK及班次集合SHIFT,对应每个班次i给定: 任务子集 TaskShifti 班次成本 costShifti 问题要求从SHIFT中选出最优的子集Partition,覆盖所有任务且使成本最小。 该模型可以应用于如 Crew scheduling等物流优化问题。,NCL语言 2000-2008. ENGINEST. All rights reserve
13、d,来源: K.L. Hoffman & M. Padberg, Solving airline crew scheduling problems by branch-and-cut, Management Science, vol. 39, no. 6, pp657-682, June 1993.,NCL建模举例: Set Partitioning(NCL 模型),Simpler Smarter Swifter,nbTask = , % Number of tasks nbShift = , % Number of shifts TASK = 1, nbTask, SHIFT = 1, nb
14、Shift, i SHIFT ( costShfiti = , % cost of shift i TaskShifti = , % set of tasks of shift i ), Partition SHIFT, i Partition TaskShifti = TASK, % set partioning constraint i j Partition TaskShifti TaskShiftj = , min i PartitioncostShfiti i SHIFT ( min inf TaskShifti % ordering search min costShfiti %
15、greedy search max # TaskShifti % greedy search ) i Partition ?,NCL语言 2000-2008. ENGINEST. All rights reserved,NCL建模举例: Set Partitioning(结果),Simpler Smarter Swifter,对于nw19, nw09, nw06, nw07, NCL在20分钟内可以找到并证明最优解; 对于nw11, NCL在46分钟内可以找到并证明最优解。,NCL语言 2000-2008. ENGINEST. All rights reserved,nw19: k Parti
16、tion costShfiti = 10898 Partition = 62, 134, 484, 942, 1543, 2126, 2699 nw09: k Partition costShfiti = 67760 Partition = 3, 10, 18, 27, 42, 108, 210, 424, 810, 1217, 1306, 1929, 2170, 2581, 2651, 2904 nw06: k Partition costShfiti = 7810 Partition = 4, 136, 200, 421, 874, 1538, 2901, 3845 nw07: k Par
17、tition costShfiti = 5476 Partition = 23, 88, 591, 1943, 3017, 5150 nw11: k Partition costShfiti = 116256 Partition = 9, 52, 135, 221, 333334, 368, 2414, 2960, 3638, 4077, 6286, 6940, 7380, 7511, 8438, 8696, 8753, 8819,NCL建模举例: Set Partitioning(比较),Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. A
18、ll rights reserved,对比德国的Oz小组的结果:T. Mller. Solving set partitioning problems with constraint programming. In PAPPACT98, pp313-332, 1998.,Mller 的Oz 算法: pre-processing + CP solver + global constraint,Mller98中所有其他问题均能被NCL轻易地求解在此不作赘述,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling(定义),- 次序变量: orderi
19、,j 表征作业 j 在机器 i 上的工序的执行次序; - 工序时间段变量: Taski,j表征作业 j 在机器 i 上的工序的执行时间段; - 排序后时间段变量: Sortedi,j表征在机器 i 上的排在第j个执行的作业的工序时间段; - 集合排序模型用来描述(资源独占性)生产排程问题: i MACHINE i MACHINE j JOB j k JOB ( Taski, j = Sortedi, orderi,j , orderi,j orderi,k, Sortedi,j Sortedi,k ),来源: J.F. Muth & G.L. Thompson. Industrial Sche
20、duling. Prentice Hall, 1963.,工序时限约束 优先执行约束 资源独占约束,优化目标: 最小化工期,Simpler Smarter Swifter,10台机器10件作业的MT10问题在1963-1988的25年间无人能解。,仅3类约束:,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling(NCL 模型),nbJob = O, % number of jobs nbMachine = O, % number of machin
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 语言 NCL 及其 工业 应用
链接地址:https://www.31doc.com/p-2709626.html