生产经营管理数学建模两阶段特殊结构混合0-1规划的分解算法

第４期

２００９年８月第１８卷运筹与管理Ｖ０１．１８．Ｎｏ．４Ａｕｇ．２００９０ＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＣＥＭＥＮＴＳＣＩＥＮＣＥ

两阶段特殊结构混合０．１规划的分解算法

刘均华，姜波

（清华大学经济管理学院，北京１０００８４）

摘要：本文介绍了一种用于求解具有特殊结构的两阶段混合０一ｌ规划问题的原始一对偶分解算法，并以

ＣＰＬＥｘ软件作为核心求解器将算法实现。该算法将原问题分解成两个相对简单的子问题，较传统分解算法有

更平衡的分解结构和收敛性。实验数据表明，该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下

三角结构混合０一ｌ规划问题时，相比ｃＰＬＥｘ提供的分枝剪枝法，在时间效率上有明显提高。算法最后通过固

定Ｏ—ｌ变量的取值可以得到满足管理精度要求的近似最优解。

关键词：混合Ｏ—ｌ规划；分解算法；原始－对偶分解；ｃＰＬＥｘ９．０；分枝剪枝法

中图分类号：０２２１．１文章标识码：Ａ文章编号：１００７—３２２ｌ（２００９）０４，Ｏｏｏｌ－０６

ＡＤｅＣＯｍｐＯＳｉｔｉＯｎＭｅｔｈＯｄｆＯｒＳＯｌＶｉｎｇＴｗＯ—ＳｔａｇｅＭｉｘｅｄ

Ｏ－１ＰｒＯｇｒａｍｍｉｎｇｗｉｔｈＳｐｅｃｉａＩＳｔｒｕｃｔｕｒｅ

ＬＩＵＪｕｎ－ｈｕａ．ＪＩＡＮＧＢｏ

（Ｓｃ＾ＤＤＺ矿Ｅ∞ｎＤｍ记ｓｏｎｄ肘矗ｎ口ｇｅｍｅｎｔ。乃￡，曙＾“口№ｆ北您ｆ秒，８ｅ彬，曙１０００８４，Ｃ＾ｆｎｏ）

ＡｂＳｔｒａＣｔ：Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓ

ｐｒｏｂｌｅｍｓｗｉｔｈ８ａｐｒｉｍａｌ－ｄｕａｌｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄｔｏｓｏｌｖｅｔｗｏ－ｓｔａｇｅｍｉｘｅｄ０－１ｐｒｏｇｒａｍｍｉｎｇｉｔ’ｓｓｐｅｃｉａｌｓｔｍｃｔｕｒｅ．Ａｆｔｅｒｄｅｄｕｃｔｉｏｎａｎｄｄｉｓｃｕｓｓｉｏｎａｂｏｕｔｔｈｅａｌｇｏｒｉｔｈｍ，ｉｍｐｌｅｍｅｎｔｅｄ

ａｗｉｔｈＣＰＬＥＸ９．０．ＴｈｅｎｅｗｍｅｔｈｏｄｄｉＶｉｄｅｓｔｈｅｏｒｉｇｉｎａｌｐｒｏｂｌｅｍｉｎｔｏｔｗｏｓｉｍｐｌｅｓｕｂｐｒｏｂｌｅｍｓａｎｄｈａｓ

ｓｔｍｅｔｕｒｅａｎｄｒ８ｐｉｄｃｏｎｖｅｒｇｅｎｃｅｓｐｅｅｄｔｈａｎｔｒａｄｉｔｉｏｎａｌｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄｓ．Ｃｏｍｐｕｔａｔｉｏｎａｌｍｏｒｅｂａｌａｎｃｅｄｏｕｒｔｅｓｔｓｓｈｏｗｔｈａｔａｐｐｒｏａｃｈｈａｓｈｉｇｈｅｒｔｉｍｅｅ仿ｃｉｅｎｃｙｔｈａｎｂｒａｎｃｈ ａｎｄ－ｃｕｔａｌｇｏｒｉｔｈｍｓｕｐｐｌｉｅｄｂｙＣＰＬＥＸｉｎｓｏｌｖｉｎｇｌａｒｇｅ－ｓｃａｌｅｔｗｏ—ｓｔａｇｅｍｉｘｅｄ０一ｌｐｒｏｇｒａｍｍｉｎｇｐｍｂｌｅｍｓｗｉｔｈｈｉｇｈｅｒｄｅｎｓｉｔｙａｎｄｃｏｕｐｌｉｎｇｍｔｉｏ．Ａｆｔｅｒｈｅｕｒｉｓｔｉｃ

ｃａｎｍｅｔｈｏｄｗｉｔｈ０ ｌｖａｒｉａｂｌｅｓｆｉｘｅｄｉｓａｐｐｌｉｅｄ，ｎｅａｒ ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｂｅｏｂｔａｉｎｅｄ．

ＫｅｙｗＯｒｄＳ：ｍｉｘｅｄＯ ｌｐｒｏｇｒａｍｍｉｎｇ；ｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄ；ｐｒｉｍａｌ ｄｕａｌｄｅｃｏｍｐｏｓｉｔｉｏｎ；ＣＰＬＥＸ９．０；ｂｒａｎｃｈ－ａｎｄ－ｃｕｔａｌｇｏｒｉｔｈｍ

０引言

０一ｌ变量常被用来表示系统是否处于某个特定的状态或者决策时是否取某个特定的方案，在工业、商业、交通运输、经济管理和军事等领域都有重要的应用。由于性质不同的变量（连续变量和０一ｌ变量）和约束（纯线性约束、混合线性约束和纯０—１约束）在系数矩阵中所处的位置不同，混合０—１规划模型会表现出多样化的结构。现实中的大规模混合Ｏ—ｌ规划模型通常具有更加特殊的结构，而且规模越大，这种结构性可能越明显。本文主要研究具有下列结构的混合Ｏ一１规划问题

收稿日期：２００８．“一１４

作者简介：刘均华（１９８ｌ ）。男．博士研究生。主要从事线性规划和混合Ｏ—ｌ规划分解算法方面的研究；姜波，男。博士，攻读博士学位期问主要研究方向为大规模线性规划算法和矩阵分解。

２运筹与管理２００９年第１８卷

ｎｌａＸ

０ＭｌＰ、’

Ｓ．ｔ．

Ａ２Ｉ茗Ｉ＋Ａ２２ｘ２≤６２

戈。≥ｏ，戈２≥ｏ；ｚ１，砖∈｛ｏ，１｝

其中ｃ。，＝（ｃ…ｃ。：）ＥＲ“，ｃ：＝（ｃ：。，ｃ：：）∈月”，ｃ。。和ｃ：。对应原问题中的连续变量，ｃ。：和ｃ：：对应原问题中的。一ｌ变量。同理。令Ａ。。＝（Ａ：。，Ａ：。）∈尺”‘。“，Ａ：。＝（Ａ：。，Ａ；。）ＥＲ“２。“，Ａ：：＝（Ａ：：，Ａ；：）∈Ｒ“２。“，石．，茗：，６。，６：是维数与前面的系数矩阵对应一致的向量，，。＝口。，口。＋１，…。ｎ。，Ｌ＝ｇ：，ｑ：＋１，…，ｎ：（下文中称石。和ｘ：为混合变量）。上述混合０一ｌ规划问题（肘伊）整体上可以划分为两个阶段，第一阶段的约束称为独立约束，

第二阶段的约束称为耦合约束，混合变量髫．称为耦合变量，戈：称为独立变量。具有这种结构的问题，其共同的特点就是在每个阶段中都包含了混合整数变量和混合线性约束，而且Ｏ—ｌ变量在整个问题中仅占很小的部分，很多问题很难直接求解。虽然传统的整数规划算法（例如分枝定界法¨ｌ、割平面法心Ｊ１）有时也可以求解，但是算法的求解效率和空间效率很难满足日常管理的需要，本文主要研究利用分解算法来求解这类问题。

１分解算法简单回顾

目前用于求解。一ｌ规划问题的分解算法主要是Ｄａｎｔｚ唔一ｗｏｌｆｅ分解算法”１（以下简称Ｄ．ｗ分解方法）和Ｂｅｎｄｅｒｓ分解算法¨１。Ｄ－ｗ分解算法最初主要针对具有块角结构的线性规划问题，很多实际问题，例如多周期生产计划问题、能力扩展计划问题、稀缺资源分部门配置问题、电力生产系统的排班问题等，系数矩阵都具有块角结构，ｓｗｅｅｎｅｙ和Ｍｕｒｐｈｙ¨１在解决具有该结构的混合０—１规划问题时采用了Ｄ．形分解算法。

利用Ｄ一矽分解算法求解混合整数规划，需要将原问题的变量和约束进行分组，形成与上述（Ｍ，尸）问题结构相同的模型。其中独立约束Ａ。。石。≤６。是一个混合０一ｌ系统，仅与变量石。相关；约束Ａ：。戈。＋Ａ：：算：≤６：是与变量名：耦合的耦合约束。选择第一个混合０—１系统构成一个子问题，利用该子问题可行域凸包极点和极方向的。一１组合来表示混合变量ｚ。，形成分解方法的主问题。主子问题之间通过列生成的方法进行迭代。Ｄ一形分解算法最终可以提供一个较原问题线性松弛更紧的边界，其主问题可以看作拉格朗日松弛方法¨’副的对偶问题。

Ｄ一形分解算法最后得到的是原问题（最大化问题）最优目标函数值的上界，提供的最优解对于原问题来说是不可行的。为了能得到原问题的可行解或最优可行解，该方法还需借助启发式方法，以分解算法得到的解为搜索起点利用启发式方法搜索整数可行解，也可以转入分枝剪枝过程，求解受限的原问题来获得原问题的可行解。

求解混合整数规划更为著名的方法是Ｂｅｎｄｅｒｓ分解算法。它最初就是针对混合整数规划问题提出的分解方法。Ｂｅｎｄｅｒｓ分解方法将连续变量和整数变量分解，通过固定０—１变量（髫…茗：：）的取值构造一个线性规划子问题，然后利用该线性规划问题来构造主问题的割（切平面）。主子问题通过行生成的方法进行迭代：主问题向子问题提供０一ｌ变量（戈㈨茗：：）的取值，子问题求解后向主问题提供新的对偶变量完成一次迭代循环。Ｂｅｎｄｅｒｓ分解算法的主问题是松弛的原问题，随着割约束的不断加入而趋近于原问题，经过有限次迭代后收敛到原问题的最优解。

后来Ｂｅｎｄｅｒｓ分解算法经过Ｇｅｏｆｆｒｉｏｎｗｌ、ｗｏｌｓｅｙ¨训等人的扩展之后可以应用在纯整数规划、非线性规划等领域，被称为广义Ｂｅｎｄｅｒｓ方法（ＧｅｎｅｒａｌｉｚｅｄＢｅｎｄｅｒｓＤｅｃｏｍｐｏｓ越ｏｎ）。广义Ｂｅｎｄｅｒｓ分解算法的思想与传统Ｂｅｎｄｅｒｓ分解算法类似，只是在构造主问题时利用了弱对偶原理（即拉格朗日对偶），子问题向主问题传递的是拉格朗日乘子，此时主问题中包含了拉格朗日松驰后原问题的耦合约束。

近些年来，求解０一ｌ规划问题的Ｄ 形分解算法和Ｂｅｎｄｅｒｓ分解算法得到比较广泛的关注：Ｖａｎｄｅｒ＿ｂｅｃｋ‘ｕ“引、ｗｉｌｈｅｌｍ‘１４１、Ｌｎｂｂｅｃｋｅ等‘”１都对列生成方法和Ｄ．形分解算法进行了深入研究；Ｐａｄｂｅｒｇ‘１６１研究了行生成方法和分枝剪枝方法，ｃｏｒｄｅａｕ【１７１等人将Ｂｅｎｄｅｒｓ算法应用在铁路调度问题的机车和车厢调度问题中，ｃａｉ¨３】等人应用广义Ｂｅｎｄｅｒｓ分解算法求解了水资源管理的非凸规划模型，ＭｃＣｕｓｋｅｒ¨引等人将嵌套

第４期刘均华，等：两阶段特殊结构混合Ｏ．１规划的分解算法３Ｂｅｎｄｅｒｓ分解算法用来求解多区域电力系统中的相关问题，Ｒｅｋｉｋ［２町利用Ｂｅｎｄｅｒｓ分解算法求解了一种考虑休息时间和排班方式的集成模型（实际上是一类旅行行程模型）。

尽管上述传统的Ｄ一缈和Ｂｅｎｄｅｒｓ分解方法得到广泛的应用，但传统分解方法存在固有的缺陷：存在不平衡的分解结构。在传统的分解结构中，主问题始终占据主导地位，接收来自子问题的信息（极点解）并保存在其矩阵结构中，而子问题仅利用主问题提供的当前信息，不存储过时的信息，因此处于被动的被支配地位。这种信息利用的不对称结构使得传统分解方法的收敛效率一直是人们质疑的地方。因此，改进传统分解方法的不对称结构，设计一种比传统分解方法有更高收敛效率的新分解算法会有更为广阔的应用前景。

２原始一对偶分解算法

原始一对偶分解算法的最初动机来自上述混合整数规划问题的特殊结构以及两种传统分解算法之间信息传递的一致性：按照Ｄ一形分解算法构造主问题的思路，在原问题中将混合变量并。的取值限制在其对应的独立约束可行域凸包的极点集中，形成一个受限制的原问题，求解该问题（或其松弛问题）可以产生Ｂｅｎｄｅｒｓ主问题需要的对偶解；按照ＢｅｎｄｅｒＳ分解算法构造主问题的思路，利用拉格朗日乘子（也可以称为广义对偶变量）以及子问题对应的拉格朗日对偶问题放松耦合约束，形成一个松弛的原问题，求解该问题可以产生Ｄ．形主问题需要的混合变量茁。的解。这样就形成了原始．对偶分解算法的原始子问题（Ｍ，Ｐ．Ｐｓ）和对偶子问题（肘，Ｐ．ＤＳ）

ｍａｘ

８．ｔ．ｃＩｘ：Ａ：＋ｃ２石２Ａ２ｌｘ：Ａ：＋Ａ２２戈２≤６２

ｅ：Ａ：＝ｌ

Ａ：∈｛ｏ，１｝；石２为混合变量（彤，Ｐ．粥）

ｍａｘ

ｓ．ｔ．ｃｌ茗Ｉ＋妒Ａ１１并ｌ≤６Ｊ

０ＭＩＰ—Ｄｓ、）∥：－并－＋妒≤山…，：为溉量｛（ｃ：一一：：）石：｝

戈。为混合变量

其中ｘ：是集合ｘ。＝｛茗，为混合变量ＩＡ。。茗。≤６。｝凸包的极点，Ａ：为相应的凸组合系数，ｅ：为全ｌ的向量；ｐ是耦合约束对应的对偶变量。

从上述分解结构来看，原始子问题是受限的原问题，为原问题（ｍａｘ）的最优目标值提供了下界，随着新得到的茗。极点的加人生成了新的极点组合，不断缩小下界与原问题最优目标值之间的间隙，最终从下界逼近原问题的最优目标值；另一方面，对偶子问题是松弛的原问题，为原问题的最优目标值提供了上界，随着新得到肛值的加人生成了新的约束，不断缩小上界与原问题最优目标值之间的间隙，最终从上界逼近原问题最优目标值。

原始－对偶分解算法的一个重要特征就是具有平衡的分解结构，两个子问题处于平等的地位，同时扮演了传统分解算法的主问题和子问题的角色。原始子问题接受对偶子问题提供的茗。极点解，并用凸组合的形式对其进行描述，与Ｄ．形主问题的作用相同；同时为对偶子问题提供割约束，扮演着Ｂｅｎｄｅｒｓ子问题的作用。类似的，对偶子问题接受原始子问题提供的割约束，扮演着Ｂｅｎｄｅｒｓ主问题的作用，同时为原始子问题提供极点解，扮演着Ｄ．形子问题的作用。所以。原始一对偶分解算法是更为一般的、具有完美对称性的分解算法。

但是，上述混合０－１规划原始一对偶分解算法的原始子问题仍然是一个混合０．１规划问题，无法像线性规划问题那样利用对偶理论直接得到最优对偶解。为了获得（近似）对偶信息，可以利用原始子问题的线性松弛来获得对偶解。利用线性松弛问题来求解对偶解的方法在很多文献中都得到了应用¨’儿１。本文也将通过求解原始子问题的线性松弛问题（肘俨．Ｐｓ驴）获得近似对偶解ｐ’，保证在得到近似最优解的同时能够快速收敛。如果此时求解子问题（肘，Ｐ—ＪＰＩｓ驴）所得原始解中的连续变量为茗：。，根据Ｄｕａｌ Ａｄｅｑｕａｔｅ性

４运筹与管理２００９年第１８卷质一】，那么对偶子问题（Ｍ俨一Ｄｓ）可以进一步表示为

ｍａｘ

８．ｔ．ｃｌ茗ｌ＋妒ＡＩｌ舅ｌ≤６Ｉ

（肘伊－Ｄｓ）ｐ，哇２ｌ石ｌ＋妒≤肛６２＋（ｃ２Ｉ—ｐ’Ａ：２）石；Ｉ＋８ＨＰ．．｛（ｃ２２一ｐ＋Ａ；２）石２２｝

’２２ＥＩｕ ＩＩ

省，为混合变量

在收敛条件设置方面，可以根据原始子问题的线性松弛问题（膨，Ｐ．黔驴）和对偶子问题（肼，Ｐ－ＤＳ）的最优目标函数值均无法继续改善来判断原始－对偶分解算法的停止，也就是在对偶子问题中没有有效切面继续被生成或者新加入的约束无法继续改善其目标函数值，同时原始子问题的线性松弛问题中也没有有效极点继续被生成或者新生成的极点无法继续改善其目标函数值。利用线性松弛求解对偶解的过程中，开始时主要在原始子问题的线性松弛问题（聊一Ｐｓ￡Ｐ）和对偶子问题（Ｍ俨－ＤＳ）之间迭代：求解问题（Ｍ伊．ＰＳ己Ｐ）得到对偶解ｐ以及原始解石：。，并将其传递给对偶子问题（Ｍ伊．ＤＳ），对偶子问题得到新的ｐ和戈：。值后添加一行新约束，重新求解更新的对偶子问题可以得到原始解菇。，并作为极点解被传递给原始子问题（肘，Ｐ．ＰＳ）与其线性松弛问题（肘，Ｐ—ＰＳ￡Ｐ），重新求解扩张后的问题（肘俨．Ｐ５￡Ｐ），依次进行迭代。经过Ｊ｝次迭代之后，原始子问题的线性松弛问题和对偶子问题都无法继续改善，此时的原始子问题（Ｍ，Ｐ－Ｐｓ）已经被添加了．｜｝列极点变量，求解该问题便可以得到混合变量菇：的解。最后通过启发式思想，固定原问题有意义的变量值，便得到了原问题的近似最优解。

如果以０—１变量作为原问题有意义的变量，那么上述原始一对偶分解算法的基本过程如下所示：

（１）令Ｓ：。代表所有已知ｘ。极点解的集合，Ｓ。代表所有已知的ｐ极点解的集合；并令Ｓ；，＝ｐ，Ｓ，＝ｐ，收敛误差为占，迭代次数后＝Ｏ，令原始子问题与其线性松弛问题以及对偶子问题目标函数的初始值分别为：冀￡Ｐ＝一∞，ｚ；ｓ＝一∞，：：ｓ＝＋∞；

（２）令．｜｝＝．｜｝＋ｌ，求解对偶子问题（ＭＰ－Ｄｓ）

如果对偶子问题不可行，则原问题不可行，停止计算；

否则。可以求得原始极点解石。以及当前目标函数值：ｋ，如果：：，≤二：１，更新集合ｓ，。＝ｓ，。ｕ｛髫。｝和ｚ：，，并为ｘ。加列，转到（３）；

（３）求解原始子问题的线性松弛（肘，Ｐ—Ｐｓ凹）

如果原始子问题的线性松弛问题不可行，则原问题不可行，停止计算；

否则，可以求得对偶极点解ｐ以及当前目标函数值＝幺。，，如果：ｋ＂≥：茹，更新集合ｓ，＝ｓ，ｕ｛ｐ｝与：；。ＬＰ，转到（４）；

（４）收敛性检验

如果ｚ塞１一：：。≤Ｆ并且ｚ；ｓ。Ｐ一孑；≥≤Ｆ，收敛过程结束，转（５）；

否则转到（２）；

（５）启发式求解过程

求解原始子问题（Ｍ，Ｐ－Ｐｓ），得到原始解菇：和Ａ。以及目标函数值彳篙；

固定原问题（膨，尸）的ｏ．１变量值分别对应向量（ｘ。 Ａ。。ｚ：）中的ｏ．１变量部分，求解受限的原问题可以得到相应的目标函数值以及连续变量解，从而得到原问题的近似最优解。

３原始．对偶分解算法的初步实验结果

我们分别用ｃ语言在ｗｉｎｄｏｗｓ操作系统下编程实现原始－对偶分解算法，通过调用ＩＬＯＧ公司的ＣＰＬＥｘ【２１１软件求解线性规划和整数规划。实验问题是１８组用随机生成方法生成的０．１混合整数规划模型，每组问题有１０个模型，总规模分别为２００×２００和４００×４００。为保证随机生成模型的可解性，对模型参数做了如下限制：目标函数系数ｃ¨和ｃ：。∈［１００，２００］，ｃ。：和ｃ：：∈［一１００，０］，右边项系数６。和６：Ｅ［２００，４００］，系数矩阵Ａ：。、Ａ；，和Ａ：：Ｅ［ｏ，４０］，Ａ：，、Ａ毛和Ａ；：∈［＿４００，－２００］，收敛误差为１０～。生成的随机矩阵基本信息如下表所示。

第４期刘均华，等：两阶段特殊结构混合０．１规划的分解算法５

表ｌ随机矩阵基本信息

问题—丽型堕面一萎蓍—丽监鉴西一竞毳稀疏度Ｉ２００２００２０４０４０２０５９５．１５％

２２００２００２０４０４０４０５ｌｌＯ．１３％

３２００２００４０２０４０１８５０４．６３％

４２００２００４０２０４０３６５２９．１３％

５２００２００４０４０４０１８７６４．６９％

６２００２００４０４０４０３６７７９．１９％

７４００４０Ｉｏ４０４０８０８１１７５．０７％

８４００４００４０４０８０１６０４７１０．０３％

９４００４００４０８０８０８１３２５．０８％

ｌＯ４００４００４０８０８０１６２３０１０．１４％

儿４００４００８０４０４０７３２７４．５８％

１２４００４００８０４０４０１“８７９．０５％

１３４００伽８０８０４０７３５０４．５９％

１４４００４００８０８０４０１４５４６９．０９％

１５４００４００８０４０８０７３５０４．５９％

１６钺）ｏ伽８０４０８０１３３３６８．３３％

１７烈）ｏ４００８０８０８０７４１９４．６４％

１８４００４００８０８０８０１４７０９９．１９％

为了评价原始一对偶分解方法的计算效率和求解精度，所有实验问题都利用目前求解整数规划效率最高的商业软件ＩＬＯＧＣＰＬＥｘ直接求解（使用分枝剪枝法和多种启发式方法）。原始．对偶分解算法迭代过程中所需的对偶解通过线性松弛方法来获得，迭代过程结束后可行解通过固定Ｏ一１变量的值求解受限的原问题来获得。

表２分枝剪枝法和原始．对偶分解算法的求解效率比较

注：。最优值间隙＝（分枝剪枝法最优目标值一分解算法最优目标值）／（分枝剪枝法最优目标值）；“时间比率＝（分枝剪枝法ｃＰ【，时间）／（分解算法ＣＰＵ时间）。

从表２中可以看到原始一对偶分解算法在求解混合０一ｌ规划问题时具有以下规律：在其他条件相同的情况下，随着问题规模的增大（整数变量比例保持不变，如问题３和问题１５）、整数变量比例的增大（如问题１０和问题１８）、问题稀疏度的增大（如问题ｌｌ和问题１２）、耦合约束数目的增加（如问题１１和问题１３），原始一对偶分解算法和分枝剪枝法的求解时间都越来越长，但原始－对偶分解算法相对于分枝剪枝法求解效率的提高越来越明显。较为特殊的，在其他条件相同的情况下，随着耦合变量数目的降低（如问题１８和问题１４），原始一对偶分解算法和分枝剪枝法的求解时间都越来越短，但原始一对偶分解算法相对于

分析上述规律出现的原因：ＩＬｏＧｃＰＬＥｘ提供的分枝剪枝法内部集成了优秀的启发式算法，对于小规分枝剪枝法的求解时间呈现出快速增长趋势，需要搜索的节点数也越来越多，而原始．对偶分解算法却把分枝剪枝法求解效率的提高越来越明显。模、较为简单的混合Ｏ一１规划问题可以很快搜索到最优解；但随着问题规模的增大、问题复杂度的提高，

６运筹与管理２００９年第１８卷问题分解成规模相对较小并且较为简单的两个子问题，在每个子问题中搜索的节点数大大减少，求解效率大大提高。上述较为特殊的情况，可能与问题的分解结构有关：当耦合变量的数目较少时，在对偶子问题的割约束中包含更少并。变量的分量，求解该混合０一ｌ规划问题时效率更高。

在迭代过程中，由于原始子问题的线性松弛问题始终向对偶子问题提供了近似的对偶解，所以对偶子问题并不能完全达到原问题的最优目标值，但是却为原始子问题提供了比较有效的原始解信息，从而保证原始子问题能向着原问题的最优目标值优化。所以，在循环完成时，原始子问题已经积累了足够的用于求解最优解（或近似最优解）的信息，因此采用将０—１变量解反代回原问题简化求解的方法得到的将是与原问题最优解非常接近的近似最优解。

Ｇｅｏｆｆｒｉｏｎ¨１曾经在推导广义Ｂｅｎｄｅｒｓ分解算法的过程中提到，如果原始子问题所得到的是ｓ一最优解，算法过程中所得到的是６一最优解，那么最后得到的应该是原问题的（８＋６）一最优解。表２中的最优解间隙表明了利用线性松弛方法获得对偶解、利用拉格朗日松弛方法推导Ｂｅｎｄｅｒｓ主问题以及在算法无法继续迭代时利用启发式过程求得可行解的原始一对偶分解算法迭代过程中可能出现的对偶间隙，原始一对偶分解算法最终得到原问题最优值的紧下界。该最优解间隙与目标函数系数、问题的规模以及约束矩阵的结构特点等有关，但是从表中的实验数据可以看到，这种下界与实际最优目标值的误差被控制得很好（平均在０．５０％以内），可以满足日常管理精度的要求。

４结论

混合Ｏ一１规划问题的算法需要在模型的规模、边界的弱化和求解的速度三个方面进行权衡。从上面的数值实验可以看出，通过挖掘实际问题中常见混合０—１规划问题的特殊结构，借助原始一对偶分解算法，我们将原来难以求解的混合０—１规划分解成两个规模较小的近似子问题，在满足收敛性的要求下大大提高了求解效率，做到了三者之间的有效平衡，在实际问题中将有很好的应用前景。

参考文献：

［１］ＬａｎｄＡＨ，ＤｏｉｇＡＣ．Ａｎａｕｔｏｍ８ｔｉｃｅｔｈｏｄｏｆｓｏｌｖｉｎｇｄｉｓｃｒｅｔｅｐｒｏｇｒａｍｍｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．Ｅｃｏｎｏｍｅｔｒｉｃａ，１９６０，２８：４９７－５２０．［２］ＧｏｍｏｒｙＲＥ．Ｏｕｌｌｊｎｅｏｆａｎａｌｇｏｒｉ山ｍｆｏｒｉｎｔｅｇｅｒｓｏｌｕｌｉｏｎｓｔｏ“ｎｅａｒｐｒｏ伊ａｍｓ［Ｊ］．ＢｕｌｌｅｔｉｎｏｆｔｈｅＡｍｅｒｉｃａｎＭａＩｈｅｍａｔｉｃａｌＳｏｃｉｅ－

ｔｙ，１９５８，６４：２７５—２７８．

［３］ｃｏｍｏｒｙＲＥ．Ａｎａｌｇｏｒｉｌｈｍｆｏｒｉｎｔｅｇｅｒｓｏｌｕｔｉｏｎｓｔｏｌｉｎｅａｒｐｒｏｇｒａｍｓ［Ａ］．ｃｒａｖｅｓＲＬ，ｗｏｌｆｅＰ．Ｒｅｃｅｎｔａｄｖａｎｃｅｓｉｎｍａｔｈｅｍａ【ｉ．

ｃａｌｐｒｏｇｒａｍｍｉｎｇ［Ｃ］．ＮｅｗＹｏｒｋ：ＭｃＣｒａｗＨｉｌｌ，１９６３．２６９—３０２．

［４］ＤａｎｔｚｉｇｃＢ，ｗｏｌｆｅＰ．Ｄｅｃｏｍｐｏｓｉｔｉｏｎｐｒｉｎｃｊｐｌｅｆｏｒｌｉｎｅａｒｐｍｇｒａｍｓ［Ｊ］．０ｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，１９６０，８（１）：１０１－１１１．［５］ＢｅｎｄｅｒｓＪＦ．Ｐａｒｔｉｔｊｏｎｉｎｇｐｒｏｃｅｄｕｒｅｓｆｏｒｓｏｌｖｊｎｇｍｉｘｅｄ－ｖａ“ａｂｊｅｓｐｒｏｇＩ翟ｍｍｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．ＮｕｍｅｆｉｓｃｈｅＭａｔｅｍａｌｉｋ，１９６２，４：

２３８．２５２．

［６］ＳｗｅｅｎｅｙＤＪ，ＭｕｒｐｈｙＲＡ．Ａｍｅｔｈｏｄｏｆｄｅｃｏｍｐｏｓｉｔｉｏｎｆｏｒｉｎｔｅｇｅｒｐｍｇｒａｍｓ［Ｊ］．ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，１９７９，２７（６）：１１２８．１１４Ｉ．［７］ｃｅｏｒｆ●ｉｏｎＡＭ．Ｌａｇｆａｎｇｅａｎｒｅｌａｘａｔｉｏｎａｎｄ“ｓｕｓｅｓｉｎｉｎｔｅｇｅ。ｐｒｏｇｒａｍｍｊｎｇ［Ｊ］．Ｍａｔｈｅｍ８ｔｉｃ８ｌＰｒｏｇｒａｍｍｉｎｇｓｌｕｄｙ，１９７４，２：

８２．１１４．

［８］ＦｉｓｈｅｒＭＬ．Ｔｈｅｌａ铲ａｎｇｅａｎｒｅｌａ）【ａｔｊｏｎｍｅｔｈｏｄｆｏｒｓｏｌｖｉｎｇｉｎｔｅｇｅｒｐｍｇｒａｍｍｉｎｇ［Ｊ］．Ｍａｎａｇｅｍｅｎｔｓｃｉｅｎｃｅ，１９８１，２７（１）：１一１８．［９］ｃｅｏ胁ｏｎＡＭ．ｃｅｎｅｒａｌｊｚｅｄｂｅｎｄｅＢｄｅｃｏｍｐ（）ｓｉｔｉｏｎ［Ｊ］．ＪｏｕｒｎａｌｏｆｏｐｌｉｍｉｚａｔｉｏｎＴｈｅｏｒｙａｎｄＡｐｐｌｉｃａｔｉｏｎ，１９ｒ７２，ｌｏ（４）：２”一２５９．［１０］ｗｏｌｓｅｙＬＡ．ＡｒｅｓｏｕｒｃｅｄｅｃｏｍｐｏｓｉｔｉｏｎａＩｇｏｒｊｔｈｍｆｏｒｇｅｎｅｒａｌｍａ￡ｈｅｍａ“ｃａｌｐｒｏｇｒａｍｓ［Ｊ］．ＭａｔｈｅｍａｔｉｃａｌＰｒｏｇｒａｍｍｉｎｇｓｔｕｄｙ，

１９８ｌ，１４：２４４—２５７．

［１１］ＶａｎｄｅｒｂｅｃｋＦ．Ｏｎｄａｎｔｚｉｇ—ｗｏⅡ毫ｄｅｃｏｍｐｏｓｉｔｉｏｎｉｎｉｎｔｅｇｅｒｐＩＤｇｍｍｍｉｎｇａｎｄｗａｙ８ｔｏｐｅｒｆｂ珊ａｂｒａｎｃｈｉｎｇｉｎａｂｒａｎｃｈ－ａｎｄ—ｐｒｉｃｅ

ａｌｇｏｒｊＩｈｍ［Ｊ］．ｏｐｅｒａｔｉｏｎＲｅｓｅａｒｃｈ，２【）ｏｏ，４８（１）：ｌｌｌ １２８．

［１２］ＶａｎｄｅｒｂｅｃｋＦ．ｉｍｐｌｅｍｅｎｌｉｎｇｍｉｘｅｄｉｎｔｅｇｅｒｃｏｌｕｍｎｇｅｎｅｒａｔｉｏｎ［Ａ］．Ｄｅｓａｕｌｎｉｅ碍Ｃｃ，Ｄｅｓｒｏｓｉｅ璐Ｊ，ｓｏｌｏｍｏｎＭＭ．ｃｏＩｕｍｎ

Ｇｅｎｅｒａｔｉｏｎ［ｃ］．ＫＩｕｗｅｒ，２００４．

［１３］ＶａｎｄｅｒｂｅｃｋＦ．ＡｇｅｎｅｒｉｃＶｉｅｗａｔｔｈｅｄａｎｔｚｉｇ ｗｏｌｆ毫ｄｅｃｏｍｐｏｓｉｔｉｏｎａｐｐｒｏａｃｈｉｎｍｉｘｅｄｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇ：ｐａｖｉｎｇｔｈｅｗａｙｆｂｒ

ａｇｅｎｅｒｉｃｃｏｄｅ［Ｊ］．０ｐｅｍｔｊｏｎｓＲｅｓｅａｒｃｈＬｅＩｔｅｒｓ，２００５．１－７６．

［１４］ｗｉｌｈｅｌｍｗＥ．Ａｔｅｃｈｎｉｃａｌｒｅｖｉｅｗｏｆｃｏｌｕｍｎｇｅｎｅｒ８ｔｉｏｎｉｎｊｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．０ｐｔｉｍｉｚａｔｉｏｎａｎｄＥｎｇｊｎｅｅｒｉｎｇ，２００ｌ，２：

１５９１２００．

［１５］ＬｕｂｂｅｃｋｅＭＥ，ＤｅｓｒｏｓｉｅｒｓＪ．ｓｅｌｅｃｔｅｄｔｏｐｉｃｓｉｎｃｏｌｕｍｎｇｅｎｅｒａｔｉｏｎ［Ｊ］．０ｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２００４：１．３２．

［１６］ＰａｄｂｅｒｇＭ．ｃｌａｓｓｉｃａｌｃｕｔｓｆｂｒｍｉｘｅｄ—ｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇａｎｄｂｒａｎｃｈ—ａｎｄ－ｃｕｔ［Ｊ］．ＭａｔｈｅｍａｔｉｃａｌＭｅｔｈｏｄｓｏｆＯｐｅｒａ“ｏｎｓＲｅ—

ｓｅａｒｃｈ，２００５，１３９（１）：３２１．３５２．

［１７］ｃｏｒｄｅａｕＪＦ，ｓｏｕｍｊｓＦ，ＤｅｓｒｏｓｉｅｒｓＪ．Ａｂｅｎｄｅｒｓｄｅｃｏｍｐｏｓｉｔｉｏｎａｐｐｒｏａｃｈｆｏｒｔｈｅｌｏｃｏｍｏｔｉｖｅａｎｄｃａｒａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ［Ｊ］．

ＴｒａｎｓｐｏｒｌａｔｉｏｎＳｃｉｅｎｃｅ，２０００，３４（２）：１３３ １４９．

［１８］ｃａｉｘ，ＭｃｋｊｎｎｅｙＤｃ，ＬａｓｄｏｎＬＳ．ｓｏｌｖｉｎｇｌａｒｇｅｎｏｎｃｏｎｖｅｘｗａｔｅｒｒｅｓｏｕｒｃｅｓｍａｎａｇｅｍｅｎｔｍｏｄｅｌｓｕｓｉｎｇｇｅｎｅｒａｌｉｚｅｄｂｅｎｄｅ墙

ｄｅｃｏｍｐｏｓｉＬｉｏｎ［Ｊ］．０ｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２００ｌ，４９（２）：２３５—２４５．

［１９］ＭｃｃｕｓｋｅｒＳ，ＨｏｂｂｓＢＦ．ＡｎｅｓｌｅｄｂｅｎｄｅｒｓｄｅｃｏｍｐｏｓｉｔｉｏｎａｐｐｒｏａｃｈｔｏＩｏｃａｔｉｎｇｄｉｓｔｒｉｂｕｔｅｄｇｅｎｅｒａｔｉｏｎｉｎａｍｕｌｔｊａｒｅａｐｏｗｅｒ

ｓｙｓｔｅｍ［Ｊ］．ＮｅｔｗｕｒｋｓａｎｄｓｐａｌｉａｌＥｃｏｎｏｍｉｃｓ，２００３，３（２）：１９７．２２３．

［２０］ＲｅｋｉｋＭ．ｕｓｉｎｇｂｅｎｄｅｒｓｄｅｃｏｍｐｏｓｉｔｉｏｎ￡ｏｉｍｐＪｊｃｉｌｌｙｍｏｄｅｌＩｏｕｒｓｃｈｅｄｕｌｉｎｇ［Ｊ］．ＡｎｎａｌｓｏｆＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２００４，１２８：

ｌｌｌ—１３３．

［２１］ＵｓｊｎｇｔｈｅｃＰＬＥｘｃａｌｌａｂｌｅｌｉｂｒａｒｙ．ＣＰＬＥｘｏｐｔｉｍｉｚａｔｉｏｎ。ｉｎｃ．．

两阶段特殊结构混合0-1规划的分解算法

作者：

作者单位：

刊名：

英文刊名：

年，卷(期)：刘均华， 姜波， LIU Jun-hua， JIANG Bo清华大学经济管理学院,北京,100084运筹与管理OPERATIONS RESEARCH AND MANAGEMENT SCIENCE2009,18(4)

参考文献(21条)

1.Padberg M Classical cuts for mixed-integer programming and branch-and-cut 2005(01)

2.Lübbecke M E;Desrosiers J Selected topics in column generation[外文期刊] 2004(6)

3.Wilhelm W E A technical review of column generation in integer programming[外文期刊] 2001

4.Vanderbeck F A generic view at the dantzig-wolfe decomposition approach in mixed integerprogramming:paving the way for a generic code 2005

5.Geoffrion A M Generalized benders decomposition 1972(04)

6.Fisher M L The lagrangean relaxation method for solving integer programming[外文期刊] 1981(01)

7.Geoffrion A M Lagrangean relaxation and its uses in integer programming 1974

8.McCusker S;Hobbs B F A nested benders decomposition approach to locating distributed generation ina multiarea power system[外文期刊] 2003(02)

9.Cai X;Mckinney D C;Lasdon L S Solving large nonconvex water resources management models usinggeneralized benders decomposition[外文期刊] 2001(02)

10.Cordeau J F;Soumis F;Desrosiers J A benders decomposition approach for the locomotive and carassignment problem[外文期刊] 2000(02)

11.Sweeney D J;Murphy R A A method of decomposition for integer programs[外文期刊] 1979(06)

12.Benders J F Partitioning procedures for solving mixed-variables programming problems 1962

13.Dantzig G B;Wolfe P Decomposition principle for linear programs[外文期刊] 1960(01)

14.Gomory R E An algorithm for integer solutions to linear programs 1963

http://www.77cn.com.cning the CPLEX callable library

16.Rekik M Using benders decomposition to implicitly model tour scheduling[外文期刊] 2004(0)

17.Gomory R E Outline of an algorithm for integer solutions to linear programs[外文期刊] 1958

18.Vanderbeck F implementing mixed integer column generation 2004

19.Vanderbeck F On dantzig-wolfe decomposition in integer programming and ways to performa branchingin a branch-and-price algorithm[外文期刊] 2000(01)

20.Wolsey L A A resource decomposition algorithm for general mathematical programs 1981

http://www.77cn.com.cnnd A H;Doig A G An automatic ethod of solving discrete programming problems[外文期刊] 1960

本文读者也读过(6条)

1. 刘均华.蓝伯雄.LIU http://www.77cn.com.cnN Bo-xiong 基于CPLEX的原始——对偶嵌套分解算法[期刊论文]-运筹与管理2008,17(6)

2. 孙岚 CPLEX在优化调度中的应用[期刊论文]-福建电脑2005(11)

3. 杨建仪.YANG Jian-yi 邮政高速运输网优化[期刊论文]-科学技术与工程2008,8(12)

报2007,25(5)

5. 曾艳.Zeng Yan 0-1规划中并行隐枚举法的实现方式[期刊论文]-计算机应用与软件2010,27(7)

6. 数学优化的行业标准-ILOG CPLEX[期刊论文]-运筹与管理2009,18(1)

本文链接：http://www.77cn.com.cn/Periodical_ycygl200904001.aspx

本文来源：https://www.bwwdw.com/article/4z3i.html