面向多最优解组合优化问题的决策求解算法

胡振震，袁唯淋，罗俊仁，邹明我，陈 璟

(国防科技大学 智能科学学院, 湖南 长沙 410073)

最优化是应用很广的一个数学分支，很多问题都可以看成是某种形式的最优化问题。最优化问题根据变量是否连续分为两类，其中离散变量的优化问题称为组合优化问题。组合优化通常是在一定的约束条件下，根据目标函数要求，从一个有限的集合里寻找一个最优的对象，如一个数、一个集合，或者一个排列[1-3]。在一定约束条件下求目标函数的极值问题也称为数学规划，因此组合优化问题也是规划问题。组合优化的很多理论也基于规划，如线性规划、动态规划、整数规划等[4-6]。

组合优化的概念源于计算科学，与运筹、决策、管理、经济等学科紧密相关，科学研究和工程应用十分广泛。当前组合优化已经发展成一个涵盖许多规划问题的学科，比如：旅行商问题、背包问题、划分问题、指派问题、最短路径问题、网络最大流问题、最小费用流问题、最小顶点覆盖问题、最小支配集问题、最小生成树问题、斯坦纳最小树问题等。尽管组合优化研究已经取得了丰硕的成果，但因为现实问题的复杂性，仍然还有很多问题需要研究：一是针对新应用问题的模型和方法研究，比如线性约束下的平行机排序问题[7]、“新高改”高中“走班”排课问题[8]、连续背包问题[9]、矩形背包问题[10]等；二是针对已有问题的新方法研究，比如寻路问题的规范排序 A 星算法[11]、图匹配问题的深度强化学习方法[12]、旅行商问题的图卷积网络方法[13]、背包问题的强化学习方法[14]、二次背包问题的剪枝算法[15]等。

本文是针对一类新问题开展研究。现实中很多组合优化问题只有一个最优解，只要找到它就可完成求解，但也存在一些特殊的问题具有多个最优解，而且决策者必须获取全部最优解才能据此适时做出决策，比如财务预算要在预算总值固定情况下得到所有的可能分配方案。这类问题具有两个显著特征：一是最优解是多个且需全部求出；二是目标物品或数值的总和是固定的。两个特征使该类问题有别于单最优解问题，可称之为多最优解组合优化问题。目前专门针对多最优解组合优化问题的研究少有报道，本文将其作为研究对象并以固定总和实数子集问题和费城中国餐馆购买鸡翅问题为例开展建模和分析。

1 相关工作

组合优化是离散变量的最优化问题，往往可以写成线性规划的形式。一个求最小目标的问题可用如下数学模型描述：

(1)

其中，x为决策变量，D表示问题或者决策变量的定义域(有限个值组成的集合)，F为目标函数，G(x)≤0为约束条件。当求解的变量是整数时，转变为整数规划问题。

线性规划问题常用的求解算法主要是单纯形法及其相关扩展算法。整数规划中的两种主要算法——分枝限界法和割平面法与线性规划的算法具有密切联系[5]。对于变量取值是0或1的整数规划问题(称为0-1整数规划问题)，有两种更为直观的求解方法：一是枚举法，即枚举所有变量等于0或1的所有组合，然后判断所有组合是否满足约束条件并使目标函数最优; 第二种是隐枚举法，同样是枚举所有的组合，但引入一些过滤条件，过滤掉局部不满足约束或目标函数值非优的组合，从而减少计算量[16]。0-1整数规划问题，也可以看作是多阶段决策问题，从这一角度建模可以运用动态规划的方法求解。动态规划不是一种特殊的算法，而是一种考察问题的途径和思路。针对不同的问题，往往需要建立针对性的模型进行求解[5,17]。

除了确定性算法外，组合优化问题还可采用启发式算法。无论是人为的构造启发式，还是基于一些最优化方法(如禁忌搜索、模拟退火、遗传算法等)设计启发式，主要目的是解决大规模问题中确定性算法无法在有限时间内求得精确解的问题，即利用启发式算法在有限时间内获得可接受的解(如近似解)。启发式往往依赖于问题的性质，需要针对不同类型的问题修改，所以通常情况下启发式设计并不容易。近年来深度强化学习被发现具有一定的潜力用来求解组合优化问题，可以通过学习来获得好的启发式[18-22]。但这些方法主要是针对单最优问题。从需要获得多最优解的角度看，上述方法中枚举法、隐枚举法、基于动态规划原理的算法最具有获得问题的全部解的潜力，所以本文的研究主要集中于此。

2 问题定义与求解

2.1 问题形式化描述

多最优解组合优化问题可以定义为：从一个有限集合中寻找多个对象、数、集合或排列，使目标达到最优。它要求将多个最优解全部求出，且约束为等式。在数学形式上可以表示为：

(2)

固定总和实数子集问题和费城中国餐馆购买鸡翅问题是两个典型示例。固定总和实数子集问题源于实际预算问题：数据集X包含一系列数据{8.05, 6.98, 6.19, 5, 22.96, 4.71, 4.74, 4.25, 6.34, 2.77, 7.31, 3.59, 18.28, 19.55}，希望从中找到多组数(多个子集)使其累加总数为84.03。如果把问题的求解变量看作是取值为{0,1}的变量，即把问题看作是在数据集X中对每个数据做挑选的决策，选中则变量取为1，不选中则取为0，如式(3)所示：

(3)

购买鸡翅问题源于一家位于美国费城的中餐馆，其鸡翅菜单与众不同，不标注鸡翅单价而是标注不同数量鸡翅组合的价格，如表1所示。问题是求解购买指定数量鸡翅时的全部最优惠购买方案。类似地，可以把问题建模为0-1整数规划问题(0-1决策问题)，如式(4)所示：

Find allx=arg(min(vx))

(4)

其中，b为要购买的鸡翅总数。

表1 鸡翅菜单

严格地说，固定总和实数子集问题是一个多最优解的约束满足问题，但也可以转换为最优化问题；购买鸡翅问题则是一个标准的优化问题，要求购买固定数量鸡翅的同时使得花费的代价最小。

2.2 枚举和隐枚举法

枚举和隐枚举法是多最优解组合优化问题的直观解法。以固定总和实数子集问题为例，引入一对相反的不等式，式(3)的约束问题就能转换为一个优化问题，如式(5)所示。这是典型的整数规划形式，可以理解为n=14个变量(阶段)的0-1整数规划(决策)问题。

(5)

首先考虑枚举法，由于数据集中总共包含14个数据，对应于14个变量，因此任意数量(1～14)的数据都可以进行组合，枚举组合总数为214-1。枚举过程可以利用字典序循环实现。由于目标函数是所选数据的和，所以每个组合都需要累加计算，运算量接近14乘以枚举组合数。因此，对于数据集规模为n的问题，枚举方法的时间复杂度约为O(n2n)；枚举过程不额外增加存储空间，所以空间复杂度为O(n)。显然时间复杂度的指数级增长源自枚举组合数随数据集规模增大产生的指数级增长。

隐枚举法思想有些类似于分支定界法，基本思路是：当检测到某些分支组合不符合约束要求，则避免进一步往下分支，从而减少总的计算量。隐枚举过程可以理解为搜索树的扩展，数据集中的每一个数作为一层的决策，以选择和不选择两种情况扩展分支，因此搜索树是一个不断扩展的二叉树，如图1所示。图中“×”表示当前节点已经不满足约束条件，因此可以剪掉。如果不考虑剪枝，那么隐枚举法的决策树从根节点到第14层的叶子节点是完整的，叶子节点数量为214，因此时间复杂度为O(n2n)，与枚举法相同。若考虑剪枝则可以使其计算复杂度与枚举法相比有明显的下降，但下降的程度与问题的求解特征和方式相关，也与剪枝约束条件相关，不是一个固定值。

2.3 基于动态规划的方法

若将问题看作多阶段决策问题，可以自然地运用动态规划原理来建模求解。对于一个n阶段的决策问题sk+1=f(sk,xk),k=1,…,n，其中sk是第k阶段的系统状态，xk是第k阶段的决策变量，优化问题可以看作求决策向量x1,x2,…,xn使得目标函数(指标)达到极值：

(6)

式中，Vk为各阶段的目标函数。 根据动态规划的最优性定理，可以将求指标极值问题转换为分阶段的递推过程：

(7)

或者：

(8)

式(7)和式(8)分别称为逆序和顺序的动态规划方程[4]。由此多阶段的决策问题可以分解为在各个阶段的状态和目标函数递推过程中做出最优的决策。

为解决固定总和实数子集问题，首先用一个简单的示例来考察动态规划的求解结构。问题是从数据集[1,2,3,4]中选择数据子集使其和为7。这是一个完全类似的问题，可表示为整数规划的形式，并转换为多阶段决策问题：

(9)

先考虑顺序递推的方法，定义状态为决策(选择该阶段决策变量数据)前的数据总和。实际状态的转移和指标的递推为：

(10)

根据各阶段的状态转移式(10)可知，求决策变量需要从最后一个阶段开始，若f4的所有可能值已知，则使f5最优可以将x4求出，进而知道f4的最优值，进一步将x3求出来，不断递推直到求出所有阶段的决策变量。对于这样一个求解过程，可以考虑两种结构：一种是循环，一种是递归。循环的结构是先将k-1阶段的所有状态s和指标f求出，再求k阶段的状态和指标，直到最后一个阶段，然后再求解决策变量。通俗讲就是向前建表(递推状态和指标)，向后查表(求决策变量)。而递归的结构是以递归的方式从最后一个阶段的状态开始递归，当存在前一阶段的未知状态和指标时，则递归地进入前一个阶段的计算中，直至第一个阶段的状态和指标计算完成，这样等价于完成了建表的过程，接着通过查表可以求解决策变量。

图2给出了顺序递推形式下利用循环方法构造的求解结构。图中的曲线表示递推的过程。从状态s1和指标f1开始递推到s5和f5，根据式(10)可知f5=7为最优的目标。根据递推的过程可以计算得到x4=1,s4=3，根据s4=3状态可以知道有两条递推路径到它。如果是只有一个解，那么查询过程只要找到一条解路径即可，但对于多最优解问题，必须获取全部路径，可以发现x4=1,x3=1,x2=0,x1=0和x4=1,x3=0,x2=1,x1=1是两个最优解，图中两条蓝色的路径就是最优解的路径。

图3给出了顺序递推形式下利用递归方法构造的求解结构。图中的曲线表示递归调用时的过程。根据约束条件状态s5=7已知，但f5是未知的，要求f5则需递归的求f4，接着f3，直到f1。因为状态s定义为决策前的和，因此f1只有一个值为0，其他状态下的f值都定义为负无穷。那么递归完毕同样得到所需的f值后，也可以根据查表得到解。

图2 顺序递推循环求解结构Fig.2 Loop solving structure for sequential recursion

图3 顺序递推递归求解结构Fig.3 Recursive solving structure for sequential recursion

从上述分析可知，顺序递推形式下，通过循环或者递归都能得到解。类似地，逆序递推形式同样也可以使用循环和递归两种求解结构，因此一个动态规划问题求解在实现上可以有四种结构，而且可以用图证明逆序循环的结构和顺序递归的结构是一致的，而逆序递归和顺序循环的结构是一致的。总的来说，顺序和逆序形式与指标推导式相关，顺序递推是指标从前往后推，决策变量从后往前计算；逆序递推是指标从后往前推，决策变量从前往后计算。循环和递归则与指标递推式的具体实现相关，循环是先计算指标推导式的等号右侧项，而递归是先调用指标推导式的等号左侧项。另外状态的定义也不是固定的，也可以定义为各阶段决策完成后的状态，对应的则需修改递推式的下标形式。

2.4 基于0-1决策动态规划多最优解算法

根据前述分析，在动态规划递推建表过程中，多个最优解能够用递推路径表示，与单最优解问题的差异主要体现在查表求决策变量过程中。一般的简单递推式查表，只能得到一条最优解路径，但是多最优解问题必须得到多条最优解路径。

以顺序递推循环求解结构为例，单个最优解问题可以用一个很简单的逻辑进行求解：从最后一个阶段开始，最优的fn已知，如果fn!=fn-1，那么必有xn=1，如果fn==fn-1，那么必有xn=0，然后根据最优的fn-1在前一个阶段继续求解。但若要得到多条解路径则不同。

一种直观解决思路是考虑建表过程中，当递推某阶段出现多种不同决策可以得到相同指标时，记录多个决策，并在查表时根据这一信息向后搜索。然而这种方式会带来内存空间的增大，因此若不希望增大内存空间，那么只能在建表的信息里实现对路径搜索。观察图2中第3和第4阶段，目标状态f4=3可以从f3=0和f3=3得到，这是两条路径。不同于单最优解的逻辑，在查表过程中已知最优fn情况下，应判断fn==fn-1+cn-1xn和fn==fn-1两种情况，当都满足条件时则采用分支的形式继续下一阶段。由于已经在建表过程中确认解的存在，因此完全可以采用深度优先搜索的方式得到不同路径的解，而且搜索分支不用深入第1阶段，只要达到fn==0(状态也等于0)就可以终止分支，如算法1所示。

算法1 整数状态的多最优解动态规划算法

分析算法的结构可知，在状态是整数的情况下，利用循环结构来实现状态递推，可以方便地利用数组(或列表)数据结构来记录指标(目标函数)信息，并可同时利用数组的索引信息来表示阶段和状态。但是对于如式(3)这样的实数问题，阶段是整数可方便表示，但状态却是实数的，不便于表示。因此基于动态规划的基本原理，考虑顺序递推的循环结构，针对性地提出一种状态实数表示的算法，即采用列表加字典的数据结构算法，核心是利用实数表示的状态作为字典的key值，如算法2所示。

算法2 实数状态的多最优解动态规划算法

实数状态的多最优解算法与整数状态的算法基本结构一致，差异主要由使用实数作为字典的key而产生。要注意由于实数在计算机中只是高精度的近似表示，所以在作为key以及运算时可能产生的问题可以使用固定模式的实数表达来解决。当然如果从另外一个角度看，实数状态的问题也可以直接转换为整数状态的问题来解决，比如：式(5)可以将c和b同乘以100，那么整个问题变为整数问题，而且解是相同的。分析算法1可以知道，基于0-1决策的动态规划法的空间复杂度主要由指标f的矩阵决定，为O(nb)，b为整数表示的状态总数(对于上述实数问题，b=84.03×100=8 403)。对于时间复杂度，计算主要体现在建表和查表过程中，建表过程中计算的区域约为nb/2，加上一些比较运算，可以认为在O(nb)量级。而查表过程由解的数量m和表的阶段数n决定，最小的情况是nm，而最极端的情况是mn，因此时间复杂度在O(nb+nm)和O(nb+mn)之间的范围内。

比较算法2与隐枚举算法，建表过程中的s≤b判断可以看作隐枚举法的剪枝约束，而动态规划相比隐枚举法的主要优势在于建表过程中对状态的规约，相同的状态合并到一起考虑，而隐枚举法一直都是以叉树的形式在扩展。基于动态规划的算法正是在对状态的不断规约中使得其分支数不断地缩减从而减小计算量。

3 两种改进的多最优解算法

前面提出的基于0-1决策的算法有效解决了本文多最优解问题的两个特征带来的问题。固定物品(数值)总和的问题通过固定目标终状态解决，多最优解的问题通过考虑多条解路径查找来解决。同时由于状态的压缩使其相比枚举和隐枚举算法在计算复杂度上具有明显的优势。

购买鸡翅问题，要求购买目标数量的物品，求代价最小的多个最优购买方案，仍采用前述方法开展分析。最直观的求解思路仍然是采用枚举，枚举所有的购买方案组合，从中得到全部的最优惠方案。枚举时需要考虑不同数量组合的鸡翅可以购买多次的问题，比如要购买12只鸡翅，可以购买3次4只，或2次6只，或1次4只1次8只等。因此购买b(>200)只鸡翅，需要在b/4+b/5+…+b/200=n个数据的组合中寻找，比如购买256只鸡翅，需要在587个数据中寻找最优组合，那么枚举总数为2587-1，显然这种规模已无法有效求解。可考虑用隐枚举法和动态规划法，即将问题转换为n个阶段的0-1决策问题。然而，隐枚举法在购买数量上升到一定的程度后计算时间也变得不可接受，图4表明采用隐枚举法在购买数量为28时计算时间已经呈现指数级上升。

图4 最优解数量较少情况下的计算时间Fig.4 Computation time of cases with small number of optimal solutions

基于0-1决策的多最优解动态规划算法结果如图4中红色虚线所示，图4中蓝色实线是根据量级O(nb)估计的计算时间。结果表明在多数情况下计算时间会接近正比于O(nb)，但在某些特殊情况下，比如图中购买120和216只鸡翅的情况，计算时间有跳跃式的上升，而这正是最优解数量较多的情况。由于图4只是为说明问题，所以只选取了有限情况(曲线上星号标记)进行计算。

3.1 基于相同决策路径合并的改进算法

显然前述算法在最优解数量较多的特殊情况下，时间复杂度可能会往差的mn方向发展。这是因为当解的数量很多且阶段数量很大时，使用递归的查表可能会近似于搜索一个n层m叉树问题，这显然是非常耗时的，例如：购买188只鸡翅时，最优解的数量为69，利用前述算法计算时间为67.1 s；购买192只鸡翅时，最优解数量为300，计算时间已达2 874.7 s，将变得不可接受。

显然对于要求出全部最优解的给定问题，解的数量m是固定的，那么只能从问题的决策阶段上来考虑降低极端条件下的计算复杂性。在前面的问题建模中，采用了0-1决策思路，其中一些阶段的决策是购买相同数量的鸡翅组合，因此这些阶段的作用是相同的。如果能够对其进行处理和简化，即将相同作用的决策路径合并，那么搜索空间将会大幅度减小。基于这种相同决策路径合并的改进思路，可采用宽度优先搜索实现，如算法3所示。

算法3核心改进在于宽度优先搜索节点扩展过程中对相同决策效果的节点进行了删减。购买相同鸡翅数量情况下的改进算法与原算法计算时间比较如图5所示，可以看到改进算法相比原来算法具有明显的改进，在最优解数量比较多的情况下也没有出现与原算法类似的跳跃性增长。

图6给出了购买4～300只鸡翅问题的改进算法计算时间结果。很明显看到，计算时间与最优解数量的关系，计算时间总体符合O(nb+nm)的正比估计(图中蓝色线为根据该量级估计的计算时间)，但随着解数量的增加有一定的偏离，且解的数量越多则偏离越大，但总体性能仍可接受。

算法3 相同决策路径合并的改进算法

图5 改进算法与原始算法的计算时间比较Fig.5 Computation time comparison between improved algorithm and original algorithm

购买188只鸡翅时，改进算法的时间为2.3 s，是原算法的1/29；购买192只鸡翅时改进算法计算时间为5.3 s，是原算法的1/542。

图6 改进算法计算时间与解数量的关系Fig.6 Relation of computation time to solution number for improved algorithm

3.2 基于0-x决策的改进算法

对原算法的改进除了进行相同决策路径合并的思路外，其实也可以从建模的角度进行改进。如果能够将0-1决策问题转变为0-x决策问题，那么决策阶段数也可大幅下降，从而降低极端情况下的时间复杂度。因此考虑将问题建模为[0,b/cj]决策问题，其中每个阶段求解变量的最大值为b/cj，数学模型如式(11)所示。

(11)

这种改进思路是利用0-x决策建模减少总的决策阶段数，使得表的整体搜索深度明显下降，可采用深度优先类搜索算法实现，计算时间也将有明显的改善。基于0-x决策的改进方法实现如算法4所示。

算法4 基于0-x决策的改进算法

与前述改进算法最大差别是，前述算法采用0-1决策，而算法4采用[0,b/cj]决策，在建表过程中同一阶段的递推需要比较b/cj种选择，在查表过程中的递归则由原来的2个分支变为b/cj个分支，原理是通过阶段内更多的比较和计算来换取决策阶段数的下降。

算法4的复杂度仍然由建表和查表过程决定，表的结构为n行b列，只是n由原来0-1决策的b/4+b/5+…+b/200变为count(4,…,cj,…,200)。建表过程的时间复杂度仍为O(nb)，查表过程没有重复分支所以时间复杂度为O(nm)。图7给出了0-x决策查表和0-1决策查表过程的局部差异，其中j阶段的0-x决策对应了i到i-2阶段的0-1决策。对应于xj=1，0-1决策有3种情况xi=1或者xi-1=1或者xi-2=1，而这三种情况其实是一个相同的决策，只是由于0-1决策结构导致分成3个阶段来决策。所以，0-x决策的建模避免了0-1决策中的很多重复搜索，前面基于相同决策路径合并的改进算法实质也是解决这一重复问题。

(a) 0-1决策(a) 0-1 Decision

(b) 0-x决策(b) 0-x Decision图7 0-1决策和0-x决策的查表路径差异Fig.7 Searching path difference between 0-1 and 0-x decision

图8给出了购买4～300只鸡翅利用基于0-x决策改进算法的运行时间情况，显然计算时间基本符合时间复杂度O(nb+nm)的正比估计。与图6相比可知，基于0-x决策的改进算法的性能相比基于0-1决策相同决策路径合并的改进算法也有明显的提升，例如最优解数量最多的购买298只鸡翅的情况，计算时间也仅为0.437 5 s。由此得出结论，对于存在多次相同决策的问题，更适合建模为0-x决策问题，因为即便采用相同决策路径合并，基于0-1决策的算法性能也达不到基于0-x决策算法的水平，而每次决策都不相同的问题，则更适合建模成0-1决策问题。(本文所有实验代码见：https://github.com/hushidong/multi-optimal-solution-combinatorial-optimization-problem)

图8 基于0-x决策改进算法计算时间与解数量的关系Fig.8 Relation of computation time to solution number for improved algorithm based on 0-x decision

4 结论

本文提出了一类具有固定物品(数值)总和及多最优解特征的组合优化问题。该问题不同于一般的单最优解组合优化问题，必须求解所有最优解。以固定总和实数子集问题和费城中国餐馆购买鸡翅问题为例，比较分析了枚举、隐枚举和动态规划三类不同方法。通过动态规划求解结构分析，明确了状态定义、指标递推、决策变量求解对于算法实现的影响。提出基于0-1决策的多最优解的动态规划算法，并针对实数状态问题提出了基于字典数据结构的实数状态表示求解算法。该算法在最优解数量较少时能够获得较好的性能，但最优解数量较多的情况下，计算时间呈现跳跃式上升。基于降低时间复杂度考虑，提出了压缩决策阶段的改进思路，并实现了两种改进算法：基于相同决策路径合并的0-1决策求解算法和基于0-x决策的求解算法。结果表明通过减小决策的阶段数可使算法性能得到明显提升，两种改进算法的对比表明具有多次相同决策的问题更适合于建模成0-x决策问题。本文将一类多最优解的特殊的组合优化问题作为一类独立问题专门进行研究，能够帮助解决现实中一些多最优解的决策问题，且对开发新的建模和求解方法也有促进作用，下一步将持续推进算法优化和实际应用。