SAS之OPTMODEL简介（三）

Mixed integer linear programming(MILP)

混合整数线性规划

说到混合整数线性规划，首先要了解什么叫整数线性规划，整数线性规划是指线性规划中的部分（或全部）变量的值要求取整数。整数线性规划和线性规划的一般标准形式差异并不大，除了在约束条件上有点稍微不同，其他基本一致。整数线性规划的一般标准形式如下所示：

上述约束条件中当S={1,…,n}时，该约束规划称之为纯整数线性规划，当S真包含于{1,…,n}中时，该约束规划称之为混合整数线性规划。简明扼要的举一个例子，直接上代码：

上述结果运行如下所示：

从上述结果可以看到求解器solver显示模型为MILP，采用算法为分支切割法，这是对MILP模型常用的一种算法，x4符合体重设置限定结果为整数，且模型达到最优化，函数目标值为122.5.

混合整数线性规划探讨到这里已经差不多了。

但是！你以为这就结束了吗？NO！

如果就这样就结束了，那本章介绍基本毫无意义可言。因此，接下来我们将要探讨整数线性规划的中的一个有趣的案例。在探讨这个案例之前，我们需要了解一下这么几个方面的知识：

1. 关于算法的时间复杂度；

算法的时间复杂度对于从事算法方向、深度学习方向的人来说是特别敏感的，我们通常说一个算法的时间复杂度是多少多少来表明这个算法的难易程度，而难易程度并不是指这个算法运行时间的长短，而是说随着问题数据规模的扩大，这个算法运行时间增长的快慢。通常我们会把算法的时间复杂度用一个多项式来进行定义，例如O(1),表示常数级多项式，即算法运行时间不随数据规模而发生变化，再例如O(n)，表示一次多项式，即算法的运行时间与数据规模保持一致，这一类我们通常称之为P类问题（Polynomial）。但是也有一部分是至少从目前来看是没有办法用多项式来表示的，例如O(n!)阶乘型复杂度以及O(a**n)指数型复杂度,这是属于非多项式级别的，这种问题我们称之为NP类问题（nondeterministic poly-nomial）。

2. 什么是0-1规划；

在整数线性规划中，当出现约束条件中的变量的取值要求都限定为0或者1的时候，我们称之为0-1规划。

3. 关于逻辑电路的定义。

逻辑电路是指通过逻辑运算来形成电路的逻辑门电路，简称门电路。电路由若干输入端和一个输出端组成，主要包含这么几种：非门（NOT）、与门（AND）、或门（OR）、与非门（NAND）、或非门（NOR）、异或门（XOR）、同或门（XNOR）等。其表现形式如下所示：

以或非门（NOR）为例做一个简单说明，A、B表示输入端，取值0和1分别代表不输入和输入，F表示输出端，取值0和1代表不输出和输出，当 (A+B)=0即F=1-（A+B）时，F表示输出为1，否则F为0不输出，其他类别同理。

那么接下来我想为各位分享的这个有趣的问题就是：逻辑电路问题。逻辑电路问题可以称之为NP问题当中最早出现的一个问题，可以称之为NP问题的鼻祖。在整数线性规划中属于0-1规划，到目前为止解决这类问题通常都是采用分支切割法，简单来说就是先将约束条件放宽，然后求解，求得可行解如果不满足约束条件，则切割掉部分已求得的可行域再次求解，直到求得满足约束条件的最优解为止，其算法的时间复杂度为O(2**n)，虽然其算法的时间复杂度很高，但是我们仍然可以通过OPTMODEL这一过程步来进行求解。

为了理解后面提出的案例，首先给出如下示例：

上图为一逻辑电路，由三个NOR门电路构成，A和B分别为输入端，其真值表下图所示。为了与NOR对比，贴出NOR门的真值表如下右所示：

上述逻辑电路工作原理为：当A=0，B=0时，假设左上方为A，右上方为B，中间下方为C，则A和B由于为NOR电路，且只有一个输入端，因此A、B等同于非门（NOT），因此A、B输出端均为1，那么A、B作为C的输入端，由C为NOR门，对应真值表可知，当输入端均为1时，输出为0，所以C输出为0；同理可以推出另外三种情况。

接下来介绍逻辑电路案例：已知：对于如下结构的逻辑电路，每一个逻辑门电路都是NOR门，限定条件每个NOR门最多只能拥有两个输入端（包括A、B、来自上一个NOR门的信号输出）。

问：至少需要多少NOR门（同时NOR门是否需要A、B端或者不需要）能构成如下所示的真值表？ 

首先明确题目已知条件，然后将上述问题转化为数学问题：已知条件：

1.   总共7个NOR门，NOR门性质确定，存在对应真值表，信息传输方向已确定：自上而下进行传输；
2.   每个NOR门的输入端会来自三种情况：A、B、上一个NOR门；输入端最多只能有两个，需要注意来自上一个NOR门可能不止一个，例如NOR3可能会有来自NOR6和NOR7的输入，如果出现这种情况则NOR3不存在A、B端；
3.   每个NOR门都会被用到或者不被用到。

接下来为问题设定变量和参数，并转化为整数线性规划模型：设定NOR门索引编号变量为gate，gate范围为[1,7]，用（pred,gate）表示NOR门的输入端（仅指上一个NOR门，不包含A、B端）和输出端索引，row表示真值表的行号，符号图如下所示：

设定约束条件变量，主要包含变量如下所示：

UseGate表示NOR门是否使用，AssignAGate表示NOR门是否存在A输入端，AssignBGate，表示NOR门是否存在B输入端，Output则表示一个大真值表，里面包含了所有NOR门的不同情况下的输出值。

逻辑电路线性规划模型可以表示如下：

约束条件：

1. 所有判断变量UseGate、AssignAGate、AssignBGate均为0-1变量数组；

   
   

2. 保证输入端A、B的值存在的前提是对应NOR门使用；

   
   

3. 每个NOR门输入端的个数总和保证小于等于2；

   
   

4. 大真值表的第一行即NOR1最终输出值就是上述小真值表的输出结果；

   
   

5. 该NOR门输出端的值存在的前提是该NOR门被使用；

   
   

6. NOR门的性质约束：

• 所有输入端（A、B、上一个NOR门）都为0时，输出端为1；

• 当输入端都为1时，输出端为0；

• 当输入端既存在0又存在1时，输出端为0；

目标函数：

在接下来的过程中我们将通过读取数据集的方式将数据读入OPTMODEL过程来进行求解：

SAS代码如下所示：

运行程序之后，我们可以得到如下结果：

运行时间在log中如下所示：

NOTE: “PROCEDURE OPTMODEL”所用时间（总处理时间）:

      实际时间          5.99 秒

      CPU 时间          1.21 秒

从上述结果可以看到最终只有5个NOR门被选中，分别为NOR1-NOR5，同时只有NOR3存在A、B输入端，NOR4存在B输入端，NOR5存在A输入端，NOR1、NOR2都不存在A或者B输入端；因此结果可以描述如下表 所示：

NOR1为最终输出端，与最终目标真值表一致，符合题目需要。

逻辑电路的规划问题，对于大多数非工科专业的同学来说可能都是非常陌生的，这一篇文章也大概对逻辑电路的各类门都简单地做了一个介绍，主要目的还是为了希望能够让大家更清楚地了解这一类的规划问题。我本人也并不是很了解逻辑电路，也是自己摸着门路去看，去学习才有了一些基础性的掌握，所以如果对我所介绍的这篇文章里面有什么疑问的话，可以直接在微信公众号直接给我留言，可以一起交流这类问题。

那么本篇关于MILP的介绍到这里就结束了，下一篇将为大家分享非线性规划（NLP）。

公众号：mingfeng07数据搬运工

个人微信：xiaopengpeng07

欢迎加我个人微信一起来愉快的玩耍啦！