主编: 许国志 副主编 顾基发 车宏安
<系统科学与工程研究> ISBN 7-5428-2430-9
第277-293页
上海科技教育出版社2000.10
摘要 根据以下三个题目:第一，讨论组合最优化的定义(2.1)， 第二，讨论最优化原理“整体最优解是局部最优的”， 第三，把导数差分的思想移植过来，建立了对称差分解法(5.3-4)。 将所得的方法汇集成一个树状结构，提出一个求解初等组合最优化问题的方法的方法。 具体到某个问题，希望能依此发现它的算法。
关键词: 组合最优化定义;三种类型的最优化原理;对称差分解法。
AMS(1991)主题分类:90C27。
引言
组合最优化是一门新兴的、发展迅速的学科，是数学规划和运筹学的一个分支。
研究组合最优化的问题确实需要[1，第2页]“新的方法、新的探索途径和新的数学上的顿悟"(new methods，new approaches and new mathematical insights)。 经典的思维和方法对本学科究竟能够起到多大的作用，依然是值得深思的.作者一直[6-18]在探讨三个题目:
第一，组合最优化的定义是什么?能够从它得到什么启迪?
第二，我们所研究的是最优化问题，当然应该弄清楚最优化原理“整体最优解是局部最优的，如果它在局部.”
第三，如何把导数和差分的思想移植到本学科中来，为我所用?
本文将特别研究如何从这三者得到求解问题的方法，汇集成一个树状结构，提出一个求解初等组合最优化问题的方法的方法。 具体到某个问题，就可依此发现它的算法。
组合最优化的定义
组合最优化的定义
迄今没有一个公认的定义.本文接受马仲蕃[4]所给的定义如下：
组合最优化是在给定有限集的所有具备某些特性的子集中，按
某种目标找出一个最优的子集的一类数学规划。
用-ABC 或 ABC 表示具有一组性质的术语ABC。根据上述，我们作如下的定义
定义2.1 组合最优化是一类数学规划。
一个组合最优化问题，记作 XYZ， 是指对于每一个 -集合 ， 在其所有的-(子)集合中求一个-(优化)集合。
在给定的-中寻找一个-(优化)集合的任务叫做问题的一个实例， 记作，或简记作.
一个问题是由它的所有实例所组成.为了探讨一个问题的理论方面的事情，我们总是选一个具有代表性的实例，即所谓的典型实例入手。
对于，把-集合叫做论域。
的-(子)集合叫做可行解或可行集。可行集的元素叫做它的可行元素， 而在中但不属于该可行集的元素叫做关于该可行集的自由元素。
可行集簇叫做可行(解，集)域，记作D。
的一个子集合叫做碎片(fragment)，如果它属于某个可行集.碎片簇记作R。
的一个子集合或者一个可行集可以对应一个或者几个值。 如果有两个，把一个叫做(主)值， 另一个叫做参数。 可行集的主值记作。 参数值记作。 定义在D上的叫做目标函数。
实例的答案包括最优解，最优值以及与本问题有关的信息。
XYZ的一个算法是一组规则，用来在有限多步内解出该问题的某类实例。
一类问题的一个方法是一组规则，用来在有限多步内直接导得类内每个问题的一个算法.
为了突出一个命题的重要性，或者便于引用，我们有时把这个命题叫做原理。
定义2. 2 组合最优化论是研究满足定义2.1的诸问题的理论、原理、方法、算法和应用的学问。
正则问题
定义2.3 给定 XYZ: 在D上，有一个目标函数。 对于任一-集合，在 XYZ: 的可行域上， 是它的目标函数。如果对于， 总有，把 XYZ: 叫做正则的。如果每一个实例是正则的， XYZ是正则的。
正则性可以把组合最优化的问题分为两类。把它写成一个命题，并用符号来表示。
: XYZ 是正则的。
给定. 每个是它的一个子实例。 除去空子实例和本身，其它的子实例是真子实例。 一个实例是简单的，如果它没有真子实例。
众多的组合最优化问题都是正则的。但是，例如，决策论中的Savage的后悔法就不是[8]。
特性集 PPP
本文还将列出关于-集合，的基本性质， 公理以及一些最优化原理，记作或， 构成特性集 PPP ( properties，postulates and principles of optimality)。
集合的序关系是重要的.我们列出以下两个特性。
: -集合是半序的。
: -集合是全序的。
取子集合该是最基本的一种运算。一个圈的任一真子图都不再是圈。 一个连通图的真子图可能是连通的，也可能不是。 而一个简单图的任何真子图总是简单的。表明情形是复杂的。 但是，一个-集合的子集合也就是这么三个可能性。 接受这一事实，有助于引用。把后两种写成特性:
: 有的-集合有-真子集合。
: -集合的每一个真子集合都是-的。
对于-集合，也有同样的特性:
: 有的-集合 有-真子集合。
: 对于每一个-集合，存在一个 使 得 。
: -集合的每一个真子集合都是的。
以 后还将有其它的命题添加到特性集中来。
枚举法和隐枚举法
从定义2.1可以立刻得到求解组合最优化问题的三个基本方法。 它们是枚举法，隐枚举法和同解法。本节讲前两个。第一个是枚举法。
对于 XYZ: ，有。 一个系统搜索的所有子集合的公式是。 它的展开式的每一项是的一个子集合。 先从中挑选所有的可行解，再按它们的值挑出最优的。这就是枚举法，记作 ENUMERATE。
一般而言，直接从定义2.1来求解问题都难有效，但是它非常直观，按章办事，此其一。 第二，计算机是极为重要的计算工具。虽然它的巨大发展使得有飞速计算的能力和海量存储的空间，但是节约求解费用(计算量)依然是一个科学原则。 最后，在数学甚至每一个科学领域里，人们总是在追求有效性。 计算阶行列式的值，求解阶线性方程组，计算函数的导数等等，人们都是从发展理论入手，再发现有效方法。 在组合最优化论中对各种问题寻求有效算法也是一个中心课题。
作为一个例子，讨论-问题， 其中是指目标函数等于可行集的诸元素的值之和， 等价于: 如果集合有一个子集不是-的，则A不是的。 应用它，并规定
(i) .
(ii) 等于从删去所有非-集合的结果。
于是得到两个方法，都叫做隐枚举法，记作 IMPL-ENUM-。 一个是先列出所有的可行解，再从(主)值求出最优值和所有的最优解;另一个是求得每一个碎片时，计算它的值，然后得到答案。
第三个基本方法 同解法
对于 XYZ，设有两个实例和。如果它们有相同的答案，就写作
改进规则是指能断定所给实例是否可改进，并能完成相应任务的规则。 对于，
(i) 如果可改进，就能构造一个改进实例; 即与具有相同答案，且按所规定的准则，比更“好”的实例。
(ii) 如果不可改进，能够断定集合本身就是的一个最优解。
对于(i)，我们写 ，或者简记作。 两者之间的关系可以写成，其中叫做改进子(improvor)。
对于(ii)，如果不可改进，我们有。
给定 XYZ: ，如果有一个改进子使得 而且存在一个正整数有， 那么所给实例有一个最优解。 改进子提供的方法叫做第一同解法。
一般地，如果有一个改进子序列 且有 这个改进子序列提供的方法叫做第二同解法。
有时，改进规则还要求如下的规则。
(iii) 设有正整数.如果， 则断定实例(在步之内)没有最优解。
至此，我们从定义得到了三组五个求解方法。 今后还要从三个最优化原理和关于可行集的对称差导出许多方法。 为了记述这些方法成为一个有规律的集合，叫做方法集。 我们像特性集那样，采用符号表示第组第个方法的第变形。 表示从定义2.1直接得到的方法。 当时，依次为从下面要讲的第一，二，三最优化原理得到的方法。 时是从对称差导得的方法。还有近似法，启发法，随机法等，需要继续编号。 因此，枚举法记作，两个隐枚举法记作和， 两个同解法记作和。
初等组合最优化论
人们熟知，组合最优化中有一个非常重要的理论部分，就是计算复杂性。 讨论了多项式(P)问题，NP问题，NP完全问题以及求解方法等等.我们规定
定义2.6 初等组合最优化论 讨论组合最优化论中的正则问题， 且不涉及NP概念和凸多面体理论的部分。
第一最优化原理
第一最优化原理
下面是我们关心的一般最优化原理：
:整体最优解是局部最优的，如果它在局部。
在组合最优化中，给定XYZ: 时， 它有三种集合(或簇):论域，可行域 D和某个可行集。 我们自然希望把这个一般原理应用于它们，建立三个相应的原理。
首先，在论域上，把(子)集合作为整体，其子集合为局部。 如果 Instance 及都有解，那么一般原理可以写成如下的命题。
: 第一最优化原理或子集合型最优化原理
XYZ: 的论域是。 整体的最优解是局部的最优解，如果它在局部。
不失一般性，只讨论适定性实例。 即对于， XYZ: 的解总是唯一的，记作; 当非空，它的解也是非空的.
若，，及分别有(唯一)最优， 及 ，把，分别作为局部与整体，可以写成
若，则
。
等价地
于是可以写成一个便于代数演算的形式:
: 第一最优化原理或子集合型最优化原理
: 唯一性 有唯一的优化集合. 写作 ，。
: 存在性 当且仅当 。
: 对于所有的，使得 , , ， 总有。
四个求解的方法
把所有问题构成问题类。 对于实例- XYZ: ， 由可以导得求解实例的两个方法。 第一个规则记作DELETE，是从这等式的右端到左端，得到去劣(自由元素)法，记作。 设想有 XYZ: ，如果能够把写为，而且能够容易求出， 即从中删去若干个关于的自由元素。与基数较小的是同解的。 如果能够不断地做下去，就能得到最优解。
应用的第二个规则，记作EXTENSION， 是从等式的左端到右端: 如果的优化集合是，增添了集合， 还能求出，就等于求出了。这个思路得到扩展法。
定理 3.1 一个问题可以用去劣法和扩展法求解，当且仅当它属于-问题类。
设实例- XYZ: 的主集合是。 在中，令，就得到一个方法，叫做生成法。
对于, 令，, 及 如果写 ， 及，则有 这就得到分治法 。
几个例
例 3.1 平面凸壳问题，最小支撑树问题，首个最小数问题(在有限个实数中求最小的个数)等都满足第一最优化原理， 上述四个方法也都能应用，并可以建立相应的算法以及它们的变形.
例 3.2 二部分图中值和最大匹配问题不满足第一最优化原理。 例如有一个赋值二部分图，其中， 边集合和边的值是。 是主集合。
设 及， 于是有，， 但是。 所以不可能应用上面所列的四个方法得到相应的算法来求解二分图的值和最大匹配问题。
定理 3.2 (i) 二分图的值和最大匹配问题，一般图最大匹配问题，最大流问题， 以及最小费用最大流问题都没有从得到相应的算法.
(ii) 中国邮路问题也没有从得到相应的算法， 这是因为二分图的值和最大匹配问题是(i)中的其它问题的子问题。 因此所有这些问题都不满足第一最优化原理。 而中国邮路问题要用到完全图中的值和最大匹配问题的算法。
第二与第三最优化原理
第二最优化原理
关于可行域D，取，有
: 第二最优化原理或可行解型最优化原理
对于，设及 。
: 唯一性 是唯一的。写作 ，。
: 存在性 当且仅当 。
: 。
注意，这原理和第一最优化原理在形式上是相同的，但是算子 的定义范围是不同的。
定理4.1 每一个正则组合最优化问题具有第二最优化原理。
利用这个原理可以直接得到两个熟知的分支定界法，记作和。在这方面，我们没有什么新的见解，不赘说了。
第三最优化原理与最优扩充问题
第三种最优化情形是关于可行解的碎片的。
碎片的子集合是碎片，后者是前者的子碎片，前者是后者的一个扩充。 两者之差是后者的扩充部分。 如果是一个碎片，它有一个扩充，记作， 它的扩充部分是，记作-扩充部分。 在碎片簇R中，给定。 把它的若干个扩充作为整体。
-扩充部分作为局部。 如果每个碎片都能定义一个主值，于是有
: 第三最优化原理或碎片型最优化原理
若，, ， 及，则
在上面，我们用同一组符号表示了两种意义。 一是集合间的运算，。 二是数量之间的运算。读者注意了上下文，阅读时将不致发生误解。
我们从得到
定理4.2 等价于下面的命题: 对于， 有。
定理4.2 设 - XYZ: ， 其中， 而的值为，则实例有第三最优化原理。
满足上述定理的组合最优化问题叫做最优扩充问题。
例 4.1 最小支撑树问题
设有最小支撑树问题的一个实例- TREE:
，其中是一个实数集.
支撑树可以定义为主集合的一个子集合， 如果它的导出支撑子图是边数最大的无圈支撑子图。 每一个碎片对应一个支撑森林， 它的连通分支数为。 碎片的值等于诸边的值之和。 对于一个碎片， 如果有一个最简单的真碎片(即一条边)， 使得是另一个碎片， 边必然是连接的两个连通分支的边， 或者说。 连接的任意两个连通分支的边构成集。 中最优碎片记作， 它是值最小的边集合。 中任一条边添加到，构成一个-最优扩充。 于是有
定理4.3 图中有一个森林(碎片)， 其中是一个树， 如果是满足的一条边， 则含有这个森林的(若干个)最小支撑树中至少有一个含有边.
有的作者就把这定理作为建立最小支撑树问题的许多著名算法的出发点.
例4.2 最大独立集问题
有一个典型实例- INDPDT
，
其中的值是。 实例的任务是求解值和最大的独立集.
给定一个碎片， 要求一个含有的值最大的基集。 林诒勋[2]指出，这是一个独立集最优扩充问题。 他讨论了这个问题并在排序论中得到了应用。
Bellman最优化原理与离散型动态规划
定义4.1 数学系统叫做半环(semi-ring，)， 如果集合是关于的具有零元素的可交换半群， 关于的具有单位元素的半群，且分配律成立。
优选半环(optimizing semi-ring，)是满足或的半环。 若，则说不劣(优)于。 如果优(劣)于，叫做阴(阳)元素，而是中性的。
强优选半环(strongly optimizing semi-ring，)是一个优选半环， 还满足条件:如果， 则对于任一， 有。
这三种半环依次记作， 和。
设，， 。 容易证明，（有的学者还叫做极小代数），是一个强优选半环。 它的零元素是，单位元素（即中性元素）是实数。 负数是阴元素，正数是阳元素。 同样，可以证明，（有的学者还叫做极大代数）， 和都是强优选半环。 和是优选半环，却不是强优选的。 可以作为半环的一个例子，但不是优选的。
网络是赋值于的无阴回路有向图。
最优路问题的一个实例，记作--PATH: ，是在网络中求解一条(即从顶点u到v的)-最优路。
路可以定义为主集合的子集， 如果它的导出子图是一条途径(可以含有圈的路)， 网络中没有值为阴的圈。 因此只需要讨论路而不需要途径。 把从到的路和从到的路作为可行解。 它的每个子集作为碎片。 要求最优路就是求一个值积最优可行解。 所以最优路问题是一个组合最优化问题。
最简单的真碎片是一条边。 取一条有向边，从到的一条路是的一个扩充部分。 的最优扩充是所有的扩充部分中的最优集，记作，值为。 中任一条路添加到，构成的一个最优扩充。 从出发的每一条有向边都有一个最优扩充。 它们中的最优的是所求的一条-最优路。
从出发取有向边，值为。 它的最优可行扩充的值是。 取遍的邻点，有 这是求解最优路问题的基本公式。我们有
定理4.4 (Bellman 最优化原理 1957) -路是最优的， 当且仅当路上任取一点，则在上的-路是从到的所有路中最优的。
最优路问题是重要的，因为它们是离散(固定与不固定阶段)型动态规划的几何模型。
多阶段有向图与嘉量原理
有向图是(多)阶段的， 如果顶点集可以划分为这样的个部分 及， 使得一条有向边的终点在第状态集合时， 它的始点必然在第状态集合中。 与的导出子图叫做第阶段。
在阶段赋嘉量有向图中， 有向边的(主)值叫做嘉量，记作。 若两个顶点之间没有有向边，就当作有一条嘉量为零元素的有向边。 于是第阶段是一个单向的二分图，它的邻接矩阵是
可写作 设
结果是矩阵。 的元素等于， 其中是路 的嘉量。 是从到的最优路的嘉量。
定理4.5 在(4.4.1)中， 设，，则 定理4.6 (嘉量原理1980)[5-7] 在强优选半环的网络上， -路是最优的，当且仅当路上任取两点，则在上的-路是从到的所有路中最优的。
我们还开展了一系列的工作[5-7]。例如从(4.4.3)得到表格计算方法等等。
对称差分解(SDD)法
N()与C()
对于两个-集合，有两种差集。 一是简单差，与。 把它们构成一个集合对。 另一是对称差。 这两种差的关系是 其中叫做一个变换项。 于是 与
叫做与的互易对。 集合对叫做互易(子)对。 如果， 而且变换项满足条件。 互易对是简单的，如果它没有真子对。
对于一个可行解，考虑这样的一个简单集合对，， 使得 。 叫做关于的一个简单互易对， 或者是的一个增量(increment)。 是关于的可行碎片，而是关于的自由碎片。
给定赋值系统。 每一个碎片有一个(主)值，有时还有一个参数值，分别写作参数值：和主值。 对于所有， 的一个参数可能就是碎片的基数或者别的什么。
的增量簇记作，的紧邻簇记作:
令 其中 。
令 及 ， 就有下面的分解公式
(参数形式)
(主值形式)
最简单又最重要的目标函数之一是
: , (值和形式)
而参数函数表示基数，(5.1.2) 等价于下面的公式。 令 及 就有下面的分解公式
(参数形式)
(主值形式)
定义5.1 XYZ是精确的， 如果对于它的每一个实例 XYZ: ， 局部最优解总是整体最优的。
把它写成一个特性如下：
: XYZ 是精确的。
下面，只考虑目标函数取得最大的情形。 其它情形也有类似的概念、定理和方法.
基本定理
把下面的三个不言自明的定理叫做基本定理。
定理 5.1 已知- XYZ: 及 。
(i) 若 及。
(ii) 若 ，则。
(iii) 若 ，则是的一个参数得到改进的可行解。
定理 5.2 已知- XYZ: .
(i) 若，则。
(ii) 若，则。
(iii) 若，则是的主值得到改进的可行解。
定理 5.3 已知- XYZ: 及 。
(i) 可行解的基数是最大的，如果。
(ii) 是唯一的基数最大的可行解，当且仅当。
(iii) 可行解是最大的，当且仅当。
(iv) 是唯一的最大可行解，当且仅当。
对称差分解(SDD)法
基于前面的讨论，把下面的方法，记作，叫做对称差分解(symmetric difference decom-position method，SDD)法[15，16，18]，用来求解组合最优化问题。 取一个初始可行解，并计算。 找出它的增量簇并作出它的分解公式。 根据基本定理，断定当前可行解是最优的，停止，并指出或算出它的值。 否则根据基本定理，找出一个改进可行解，把它作为当前解，作下一轮的计算。
四个SDD法
把进一步具体化，可以得到更明确的方法，把它们记做: SDD-。
第一个方法，是取一个初始可行解，计算。 从增量簇中逐一取出增量，计算。 如果， 从中删去， 否则把作为新的可行解。 如果，则当前可行解是最优的。
第二个方法，，是如果可行解的值满足， 且可以作。 计算。 如果，停止。 可行解是最优的，其值是。 否则取一个 使得， 把作为新的可行解，它的值等于。 从它作新的一轮改进。
第三个方法是: 任取的一个简单自由碎片， 找出能够和它匹伍的所有简单可行碎片， 构成的增量， 作。 如果，从中取一个， 使得满足， 于是得到一个改进可行解。 否则，再取另一个简单自由碎片。 通过所有简单自由碎片都不能得到改进可行解，就是最优解。 我们得到SDD法。
最后是:如果简单自由碎片都是单元素集合， 这就显得特别简单有效。 得到SDD方法。
几个例
例 5.1 最小支撑树问题[17] 设有一个典型实例 TREE:， 其中图是一个赋值连通图。 任一支撑树是可行解。其全体记作。 设，是互易对。 取, 含有唯一的圈。 圈中除外诸边的长度最大者记作，则有一个增量。 如果， 则有一个改进可行解。 如果， 边添加进无法得到改进可行解， 则弃舍。 应用就得到调优算法。
例 5.2 二分图的最大匹配问题[17] 设有一个典型实例 MATCH: ， 其中是一个二分图。 把匹配叫做可行解，其全体记作。 设，是互易对。 图中每个顶点至多邻接和的边各一条。 导出子图中每个顶点的度数至多为2。 它的连通分支或是一个圈，或是一条路(即人们熟知的交错路)。 如果，就一定存在一条关于的可扩路， 设它对应，其中，， 于是是一个改进可行解。 这就是Berg定理和匈牙利算法的出发点。
例 5.3 最短路问题，平衡运输问题，网络最大流问题，最小费用最大流问题，旅行商问题和中国邮路问题等等也可作同样的讨论， 并利用SDD方法，分别得到Bellman最优化原理，三元运算(triple operation)，Ford-Fulksen算法，调优算法和管梅谷算法等等。
例 5.4 线性规划问题[16] 设有线性规划的典型实例 LP: ， 。 它的任务是求解，其中 是矩阵， 它由列向量所组成，仍记作。 是维列向量， 是维行向量。 是向量的值。 令， 相应地，。 由的列向量组成的矩阵如果有逆，是一个基。 如果, 是可行基，它的值等于。 我们知道，如果实例有最优解，它可以在一个可行基处达到。
设是主集合，满足条件的 ， (的一个子集合)叫做可行解。 实例的任务是在可行域D上求的最大值。 因此线性规划是一个组合最优化问题。 设，其中， 。 如果，，， 及 ，。 对于，有 及 。
定理 5.4 设， 则有。
给定可行解，取自由向量。 如果存在一个使得是一个增量， 于是。 所以有。
若， 有(。 是的一个改进。
可行解是最大的， 若， 即，不存在使得。 这是人们熟知的改进单纯形算法，也就是算法。 这个结果似乎更令人有点意外。
求解初等组合最优化问题的方法的方法
至此，我们从定义，从三个最优化原理以及对称差分解法代数地得到了五类十六个方法。 把它们列成一个树形结构是显然的。
我们建议: 给定一个问题的一个实例，按以下思路来研究。 断定它确实是一个组合最优化问题的实例之后，依次检查它
是否满足第一最优化原理，
是否满足第三最优化原理，
是否能够从对称差分解法得到启发，
能否建立同解法和隐枚举法，
分支定界法是不得已才用的，
枚举法只对规模很小的实例可用。
前四项中有一项是肯定的，就可以利用所属的方法发现相应的算法。 再把所得到的那些算法进行计算复杂性的研究。 如果前四项中一个也不满足，我们也许有更充分的理由怀疑问题不属多项式问题类。 当然还有近似法，启发法，随机法等用来求解。
我们把上述建议叫做求解初等组合最优化问题的方法的方法。
利用它来发现一个具体问题的实例的算法就成了这个实例的算法的算法。这是我们从[14]开始就梦寐以求的。
最后，作者感谢许多学者，特别费浦生，林诒勋，张福基，毛经中，唐国春诸位教授和周三明博士，感谢他们对作者的长期的帮助和鼓励，同时期盼读者们的批评和指正。
参考资料
Lawler E. L.，Combinatorial Optimization: Networks
and Matriods. Holt，Reinhart and Winston 1976。
林诒勋，试论最优化原理的一般形式，曲阜师院学报(自然版) 3(1985)35.
—(LinY.X.)，An ordered independence system and its
applications to Scheduling problems，European Journal of Operational
Research，74 (1994) 183-195。
马仲蕃，条目“组合最优化“，《中国大百科全书 -
数学卷》第865页，1988。
秦裕瑗，《Optimum Path Problems in
Networks》，Hubei Education Press，1992.
—，Bellman 最优化原理–论动态规划
I，《应用数学》，7:3 (1994)，349-354。
—，优化路问题的代数方法–论动态规划
II，《应用数学》，7:3 (1994)，410-416。
—，决策论的两类判据，《管理工程学报》，8:3
(1994)，167-172。
—，论优化问题的公理方法 I，《应用数学》，9:3
(1996)，261-265。
—，论优化问题的公理方法 II –
算法原理与六个基本算法，《应用数学(增刊)》(1996)，9-12。
—，论优化问题的公理方法 III –
多阶段决策问题，《数学杂志》，16:3(1996)，329-335。
—，论优化问题的公理方法 IV –
有限改进算法与迭代算法，《数学杂志》17:3(1997)，325-330。
—，论优化问题的公理方法 V –
优化集合的代数表达式，《数学杂志》17:3(1997)，331-334。
—，算法的发现 (I) –
组合最优化的一个基本方法，《数学杂志》，14:3 (1994)，4336-444。
—，算法的发现(II) –
对称差(的)分解法及其应用，《数学杂志》15:1 (1995)，82-88。
—，郑肇葆，算法的发现(III) –
对称差(的)分解法的另一应用，《数学杂志》，18: 1(1998)，76-80。
—，郑肇葆，算法的发现(IV) –
论组合优化的特性清单，已被《数学杂志》，18:4(1998) 421-7。
—，Symmetric-difference decomposition methods for
combinatorial
optimization，《国际组合数学学术会议和夏季讲演会(合肥)》论文集1997.5。