文档介绍：运筹学语言NCL及其工业应用
©2000-2008 ENGINEST. All rights reserved.
NCL语言
NCL语言©2000-2008. ENGINEST. All rights reserved
Simpler • Smarter • Swifter
语法分析器(parser):模式识别技术
支持自然建模
支持可视化模型调测及诊断
解算器(solver):混合集合规划
求解实数、整数、布尔值、时间、索引
及集合类型上的混合约束;
支持一阶逻辑、集合推理、数值分析等
求解规则编程(rules)
支持启发式求解策略
支持业务规则:快速构建解决方案
NCL是一门集逻辑、优化及求解规则为一体的智能描述型语言,
支持业务建模和问题求解,独立于领域,跨行业。
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
混合域(实数、整数、布尔值、索引及集合)上的联合求解系统;
支持一阶逻辑、集合推理、实数域数值分析等。
集合对信息的聚合性(基数、上界、下界、交、并、差、前继、后继)
动态量词逻辑增强模糊推理的能力,支持更强大的问题描述与求解:
- " 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语言的求解框架
NCL语言©2000-2008. ENGINEST. All rights reserved
Simpler • Smarter • Swifter
约束切割(Constraint Cut)和树搜索(Tree Search)
Simpler • Smarter • Swifter
NCL求解规则
最小化松弛度(Least Slack)
一般来说,松弛度越小,非确定性越小,产生回溯的可能性也越小;
最大化松弛度(Greatest Slack)
域越大,分枝后变化越大, 域切割的扩散性越大。一般来说,很适用于实数变量;
最小化遗憾度(Least Regret)
分枝时分枝点处的搜索准则的差异越大,选枝越容易,回溯时遗憾度越小。
本例中,我们倾向选择这样的order:它距离可能的nextOrder中最近的与次近的
差距最大,即最大化“次小与最小之差”。那么该order相对其他“次小与最小之
差”较小的order,选枝选错的可能性要小,因而该步回溯时遗憾度要小;
顺序性(Ordering Search)
根据一些实际的业务规则选枝搜索以使解空间尽量保持凸性;
贪婪性(Greedy Search)
局部最贪婪地向有利于优化目标的方向选枝搜索。该准则一般用作最后一条。
NCL语言©2000-2008. ENGINEST. All rights reserved
Simpler • Smarter • Swifter
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 = ? (→), ∀