掘金 后端 ( ) • 2024-05-07 18:01
写给女朋友的OPL教程[三] 决策、约束和调度
女朋友 教程

决策类型

决策变量在优化问题中为未知。 它具有域，域是对该变量的所有可能值集的紧凑表示。 决策变量类型是对其确切性质取决于模型底层优化器的对象的引用。 决策变量只能在给定模型实例的上下文中进行实例化。

OPL 模型的目的是查找决策变量的值，以便所有约束都得到满足，或者在优化问题中，查找满足所有约束的变量的值并优化特定目标函数。 因此，OPL 中的变量本质上是决策变量，与 Java 和 ILOG Script 之类的编程语言中的变量有本质区别

  • 说实话，同为编程语言中的变量，OPL中关于决策变量的定义、使用和其它语言本质上其实是不同的，所以我尽量不引用其它情况的例子，而是从它语言本身出发来解释它是啥，它有啥用

  • 随便拿一道题作为例子，如下：

$$ Maximize z = 5x_1+4x_2\ 6x_1+4x_2 \leq 24\ x_1+2x_2 \leq 6\ -x_1+x_2 \leq 1\ x_2\leq2\ x_1,x_2\geq0 $$

  • 这里的$x_1$和$x_2$，就是所谓的决策变量，这里的变量含义与OPL中相同，此时如果我们要定义这两个变量，可以这么表示：
dvar float+ x1;
dvar float+ x2;

  • 这简单的一句话，需要分成四部分：

    • dvar：用于定义决策变量的关键字，声明或者定义决策变量都需要使用它

    • float ：表示浮点数（小数）,表示我们要解出的决策变量结果为小数，这里使用了float+，表示这个变量是一个非负浮点数

    • x1： 标识符，表示这个决策变量的名字

    • ;： 语句结束符，这句话到此结束。我们在这里定义变量的时候点出了它的变量类型和名字，就已经完成了，所以到此结束。如果要定义新的变量，就要新开一句话，然后再用这个结束。它不是唯一的语句结束符

  • 为什么我一直要强调决策变量，因为只有需要我们解出的值才需要如此声明，且它们是不能被直接赋值的，也就是说，dvar float+ x = 5.0;是一个错误的语句。

  • 通常我们在解决这样的最优化问题时需要指定决策变量的取值范围，即决策变量的域，

dvar int x in 1..100;

  • 这样我们就声明了一个可行解，它的取值被约束在了[1,100]之间，这里用到了关键字in

  • 如果我们需要对不同的决策变量进行不同的约束，我们可以利用数组

int cons[1..4] = [ 100,200,300,400 ];
dvar int x[ index in 1..4 ] = 1..cons[index]

  • 这样我们就得到了四个可行解，它们受到的约束分别为：

    • x[1]: [1,100]

    • x[2]: [1,200]

    • x[3]: [1,300]

    • x[4]: [1,400]

  • 一般情况下我们都会使用带+号的快捷声明方式

dvar int a in 0..maxint;
dvar int+ a_positive;

dvar float b in 0..infinity;
dvar float+ b_positive;
  • 上述同种数据类型的二者表示结果等价

决策变量表达式

  • 还记得上面我举的一个简单最优化的例子吗？如果我想用一个标识符来表示不等式左边的式子，该怎么做呢？
dvar float+ x1;
dvar float+ x2;
dexpr float p = x1 + x2;

  • 这里我们使用了关键字dexpr,来声明一个决策变量表达式。在使用表达式时，注意带+号的数据类型都无法使用

  • 我们可以通过使用这样的式子，来复用一些重复的式子，它也增加了代码的可读性，再比如我前面举过的水果的例子。每个水果早上和晚上都有不同的价格，如果我需要解出怎样定价，才能使得早上和晚上差值最小的情况下，使得总利润最大。这个时候差值的计算，我们就可以利用决策变量表达式

dvar int+ morning;
dvar int+ evening;
dexpr int minus = morning - evening;

运算符

  • 这里列出了几种常用的运算符，用于数据之间的运算
运算符 描述 + 加法 - 减法 * 乘法 div 整数除法 mod(%) 取余 abs 取绝对值(返回值为float)
  • 下面的示例中给出了一些运算式和结果
2 + 3 // 5
3 - 1 // 1
2 * 2 // 4
6 div 3 // 2
5 mod 2 // 1
5 % 2 // 1
abs(-1) // 1.0

关系运算符

  • 关系运算符得到的结果只有两种：true和false,这两个也是opl中的关键字

  • 常用的关系运算符如下所示：

表达式 描述 == 等于 != 不等于 < 小于 <= 小于等于 > 大于 >= 大于等于
  • 我们可以很自然地得到以下的例子：
1 <= 5 <= 10 // true
2 > 10 // false

逻辑运算符

  • 逻辑运算符一般用于对表达式得出的布尔值进行运算

  • 常用的逻辑运算符如下所示：

表达式 描述 ! 取非 || 或者（析取） && 并且 ( 合取 )
  • 三种运算符的运算法则如下所示
! ( true ) \\ false

true || true \\ true
true || false \\ true
false || false \\ false

true && true \\ true
true && false \\ false
false && false \\ false
  • 如果三者出现在同一式子中，运算顺序为：! > && > ||

聚合运算符

  • 这里只介绍最常用的sum,min,max,prod 
int data[ 1..4 ] = [ 5,6,7,8 ];
int sumData = sum( index in 1..4 ) data[index];
int minData = min( index in 1..4 ) data[index];
int maxData = max( index in 1..4 ) data[index];
int prodData = prod( index in 1..4 ) data[index];

  • 从上到下，值依次为：

    • sumData: 求data各元素的和

    • minData: 求data各元素的最小值

    • maxData: 求data各元素的最大值

    • prodData: 求data各元素的积

约束

约束是一部分布尔表达式。

某些约束的可用性取决于其上下文。 上下文可以是：

  • 指定声明数据时的数据初始化

  • 优化模型

    • constraints 块

    • subject to 块

  • 用于过滤迭代以进行聚合或生成的表达式。

  • 上面说的东西其实很抽象，搬出我们之前举出的例子就是：

$$ Maximize    z = 5x_1+4x_2\ 6x_1+4x_2 \leq 24\ x_1+2x_2 \leq 6\ -x_1+x_2 \leq 1\ x_2\leq2\ x_1,x_2\geq0 $$

  • 下面的不等式，都是约束

  • 我们在编写程序解决问题时，不仅需要声明约束，还需要弄清楚待优化的目标函数

  • 上述问题转化为程序，是这样求解的：

dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
    6*x1 + 4*x2 <= 24;
    x1 + 2*x2 <= 6;
    -x1 + x2 <= 1;
    x2 <= 2;
}

优化指令

  • 指minimize和 maximize两种，分别表示目标函数的最小化和最大化

  • 在上题的求解中$z = 5x_1+4x_2$就是我们需要求解的目标函数

  • 注意：

    • 优化指令需要整数或浮点数类型的目标函数

    • 不能在 maximize 或 minimize 语句和约束定义之间插入其它代码。 如果没有目标定义的约束，最好使用类似于subject to {}的空约束

条件约束

  • 如果我们希望决策变量在某些量不同时，拥有不同的约束，我们就可以使用条件约束 
int x = 10;
dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
      if( x > 5 ){
        x1 + 2*x2 <= x;        
      } else if( x < 6) {
        -x1 + x2 <= 1;        
      }
    6*x1 + 4*x2 <= 24;
    x1 + 2*x2 <= 6;
    x2 <= 2;
}
  • 条件约束语句结构一般如下所示：
if ( ... ) {
    ...
}else if( ... ){
    ...
}else{
    ...
}

  • if后的括号中写下对应的条件，满足后执行其后大括号内的语句。

  • 注意：条件约束中的条件必须是基本条件，即不得包含决策变量

forall

  • 对应其它语言的for语句，一般用于枚举约束，所以只能在subject to的语句块中使用

  • 我们可以用forall来声明一系列的约束：

int x = 10;
int capacity[1..4] = [ 10,20,30,40 ]; 
dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
      forall( i in 1..4 ){
        x1 <= capacity[i];  
    }
    x1 + 2*x2 <= x;        
    -x1 + x2 <= 1;
    6*x1 + 4*x2 <= 24;
    x1 + 2*x2 <= 6;
    x2 <= 2;
}
  • 也可以对集进行枚举 
int x = 10;
{int} upperBound = { 100,200,300,400 };
{int} lowerBound = { 10,20,30,40 }; 
dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
      forall( lower in lowerBound, upper in upperBound  ){
        lower <= x1 <= upper;  
    }
    x1 + 2*x2 <= x;        
    -x1 + x2 <= 1;
    6*x1 + 4*x2 <= 24;
    x1 + 2*x2 <= 6;
    x2 <= 2;
}

约束标签

优点

  • 通过约束标签，您可以利用 IDE 问题浏览器中的扩展功能，该功能用于发现给定应用程序中哪些约束比较严格，并查找线性程序中的双变量值。

  • 如果有可用的解法，您可以访问已标注约束的松弛值和对偶值。

  • 不可行的模型中的宽松项和冲突搜索过程仅考虑已标记的约束。

  • 对我而言，当一个约束被标注，意味着我们可以更好地理解我们写下的约束是为了什么，同时IDE对标签的支持也使得我们排查错误变得更方便

缺点

  • 标注约束存在可能非常大的性能和内存成本，尤其是将元组模式用作索引的情况下。 因此，建议您不要对大型模型使用标签，或者如果使用，至少使用元组索引来代替元组模式。

  • 更准确地说，在以下三种情况下使用约束标签：IDE 扩展操作、在存在解法的松弛和对偶值中以及松弛和冲突检测。 如果您不需要这三种用例，应丢弃标签以加快执行速度并降低内存耗用量。

  • 可以这么理解：使用标签会使得代码的运行变慢，但对于一些小的优化问题而言它并不是很严重的问题，实际上不会带来太大的影响（因为现在的电脑性能不算差）

标注约束

  • 标识符 :就可以直接对约束进行标注
int x = 10;
dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
      label1: 
        x1 + 2*x2 <= x;
    label2:        
        -x1 + x2 <= 1;
    label3:
        6*x1 + 4*x2 <= 24;
    label4:
        x1 + 2*x2 <= 6;
    label5:
        x2 <= 2;
}

  • 如上我分别对5个约束进行了标注，一般标签其后的语句缩进要更远一些，这样表示起来更清晰

  • 也可以使用索引标签：

tuple Label{
  string name;
}
{Label} labels = { <"Chinese">,<"English">,<"Spanish">,<"French"> };
constraint indexed[labels];
dvar int+ x1;
dvar int+ x2;
maximize 5*x1 + 4*x2;
subject to{
      forall( label in labels ){
        indexed[label]:
        x1 <= 10;
    }
    x1 + 2*x2 <= 10;
    -x1 + x2 <= 1;
    6*x1 + 4*x2 <= 24;
    x1 + 2*x2 <= 6;
    x2 <= 2;
}
  • 这里constraint用于声明将接收标签约束的约束数组,indexed[label] 即使用的索引标签

调度

  • 在 OPL 和 CP Optimizer 中，时间点表示为整数，但可能非常广的时间点范围意味着时间实际上是连续的。 在随着实际上连续的时间进行调度的结果是，需要在模型中以紧凑的方式表示某些随时间而变的已知数量的演进（例如，资源的即时效率/速度或者在给定日期 t 完成某项活动的提前/延迟成本）。 为此，CP Optimizer 提供了分段线性函数和分步函数的概念

  • 调度问题的一个重要特征是时间区间可以是可选的以及是否执行时间区间是可能的决策变量。 在 CP Optimizer 中，这一点通过每个区间变量关联的布尔存在状态概念进行捕获。 在区间变量存在之间可以表示逻辑关系，例如，用于声明区间 a 存在时，区间 b 也必须存在

  • 调度的另一个方面是向时间区间分配稀缺资源。 随着时间的资源演进可以通过两种变量类型进行建模

  • 调度中的一些经典的成本函数包括提前/延迟成本、完工时间、活动执行或非执行成本。 CP Optimizer 将这些经典成本函数泛化，并且提供一组可以组合在一起的基本表达式；允许您表达各种各样能够供 CP Optimizer 搜索高效利用的调度成本函数

分段线性函数

  • 假如我们需要表示这样的分段函数：

piecewiselinearfunc.jpg

  • 该函数包含斜率10,20,和40，分界点分别为100和200，在0处取值为0

  • 我们需要使用关键字piecewise来声明这样的函数：

dvar int+ x;
pwlFunction F = piecewise{ 10 -> 100 ; 20 -> 200 ; 40 } ( 0,0 );
int result = F(250);

  • 这里我们使用了关键字pwlFunction来声明一个分段函数，并在其后应用决策变量x来解决问题

  • 我们再对piecewise后的语句进行分析：

    • { 10 -> 100 ; 20 -> 200 ; 40 }: 这里的10 -> 100，前者表示这一段函数的斜率，后者表示这一段函数的分界点，因为第三段函数直接往后延申，所以我们不需要指定分界点

    • (0,0): 单纯指定斜率和分界点是不够的，这样无法确定分段函数的具体形状，往往我们还需要指定一个分段函数上的点以确定位置，(0,0)就是这样的一个给定点，默认情况下分段函数的起点取值为0

  • 这里25作为x值被带入到分段函数中进行计算，运算结果为250

分步函数

  • 分段函数有一些比较特殊的情况：如果整个函数呈现“锯齿状”，每段函数的斜率都是0，这样的函数称之为分步函数

functions.jpg

  • F2,F3就是分步函数，我们需要stepFunction来声明分步函数：
stepFunction F2 = stepwise{ 0->0; 100->20; 60->30; 100 };
stepFunction F3 = stepwise(i in 0..51, p in 0..1) { 100*p -> (7*i)+(5*p) ; 0 };
  • 除了关键字不同，其它参数的解释都与分段线性函数一致

注释

  • 还记得前面我在代码中举的例子吗？有部分例子我使用了像//这样的符号，其后一般跟的是我写的代码的解释，或者是特定代码的结果，但它们并不是代码规则的一部分，也就是说代码在执行时会把这些东西给忽略掉。

  • 像这样只用于进行解释说明，但没有实际作用的表达式，我们称之为注释

// 这是一行单行注释
int a = 5;
/*
    @Author: EricMoin
    @Date: 2024.05.07
*/
int b = 55555;

  • //：单行注释，其后的内容不会被执行

  • /* ... */：多行注释，/*开始，一直到*/结束的内容都被视为注释的内容

  • 一般来讲，规范的代码一定会含有注释。因为团队合作的情形中，单靠标识符来理解他人的代码还是有困难的，将注释写入代码中可以让他人更快地理解你的代码。就算是自己的代码，在一段时间过后也需要相当长的时间来回忆当初为什么要写下这一段文字，但如果只是解决小问题，那自然无关紧要（懒得写）

总结

  • 到这里，opl基本的语法知识介绍基本结束。之前的很多部分我都省略了更难以理解的内容，以精炼其中最简单最重要的点来让妳熟悉并掌握基础知识。往后我会以解决问题的角度出发，通过解决一个个经典问题，来引出更复杂的内容。

  • 加油吧，解题的脚步，才刚刚开始
相关内容
向鱼感谢女朋友
女朋友的情绪价值过于饱满了
女朋友长得像杨紫是怎样的一种体验？
520 想送女朋友一块手表，预算 3000 元有哪些性价比高的推荐？
520送女朋友口红丢人吗
和女朋友同居一年了，给jym看看这一年的吃吃吃！
女朋友会说中日韩英语言（都是母语水平），她想做点兼职，有啥门路？
打算买一个小电动车给女朋友开，需求如下： 1. 轻量，颜值高 2. 续航能力别太差，上班来回大概7公里 3. 价格2k左右，越便宜越好 4. 售后不要太差 5. 车子最好可...
健身男追女教练大量私讯「当我女朋友」 电话连环扣跟骚罪起诉
JYM，已经戒烟第九天了，昨天晚上烟瘾达到巅峰，最后还是忍住了拿烟钱给女朋友买了束花。但是现在感觉瘾又发作了，这样下去肯定扛不住啊家人们，大家都是怎么控...