交替割平面法和双割平面法及其测试结果

提出了交替地使用两个出平面和同时使用两个割平面去求解纯整数规划模型的两种新方法，并对这些算法进行了测试对比．结果表明：总体而言，它们都优于Gomory割平面法．

基于内点割平面法的混合整数最优潮流算法

提出了一种采用内点割平面法求解混合整数最优潮流(OPF)的算法。该算法循环执行3个步骤:①求解OPF的可行解并将其线性化;②从线性内点法的最优解中判断基变量;③根据基变量产生混合整数割平面。与单纯形割平面法相比,内点割平面法不仅简单易实现,计算效率高,而且随着问题规模的增加,更能发挥其多项式时间特性的优点。文中还对退化问题的处理以及稀疏技巧的应用进行了深入的讨论。通过对IEEE典型系统的数值仿真计算显示出所提算法对于大型电力系统最优潮流问题的精确求解是非常有效的。

基于特殊有效不等式求解机组组合问题的内点割平面法

基于特殊的有效不等式(valid inequalities,VIs),提出一种求解计及爬坡约束机组组合(unit commitment,UC)问题的内点割平面法。采用线性化技术将UC问题转化为一个混合整数二次规划(mixed integer quadratic programming,MIQP)。根据UC问题约束的特点,产生3种特殊的VIs,即覆盖不等式(cover inequalities,CIs)、提升覆盖不等式(lifted cover inequalities,LCIs)和广义流覆盖不等式(generalized flow cover inequalities,GFCIs),进而将其作为割平面,建立求解MIQP的内点割平面法。100机组24时段等6个系统的仿真结果表明,产生CIs、LCIs和GFCIs的方法快速有效,所提内点割平面法具有良好的收敛性和稳定性,能有效处理爬坡约束,与其他多种方法相比较,获得了更好的数值结果。

电力系统最优潮流的内点割平面法分析与改进

针对电力系统优化运行控制的最优潮流问题,采用内点割平面法求解多重解的线性规划问题,算法迭代次数多,计算速度低,严重的可能导致算法不收敛.为此提出一种识别最优基的方法,通过对优化问题的解空间进行旋转和映射,将最优解沿可行域的棱移动至顶点,得到问题的最优基,从而解决原算法失效的问题.进一步采用随机扰动法和阶梯矩阵变化法提高算法的计算效率,平均计算时间缩短了20%左右.对电力系统标准测试系统IEEE14-300节点系统的数值仿真结果表明,改进算法能够正确处理最优解的各种情况,扩大了内点割平面法的应用范围.

解ILP的割平面法的收敛性问题

在整数线性规划即ILP的割平面解法中,一个公认的经常存在的问题便是向最优解的收敛问题,即由于缺少割平面方程选取的准则,因而常常向最优解收敛得很慢。本文根据对偶单纯形方法解题的基本思路,提出了割平面方法应用中选取割平面方程的优选准则,因而为解决该方法应用中一直没有解决的收敛性问题提供一种有效手段。

求解整数规划的割平面法的研究

在使用割平面法求解整数规划时,寻找Gomory约束是其中最为关键的一步.一般地,选取非整数解变量中分数部分最大的一个基变量,写下相应行的约束,由此推导出Gomory约束.本文主要讨论当非整数解变量中分数部分最大的基变量有两个以上时,如何通过比较选取切割条件较强的Gomory约束,以减少切割次数和运算量,较快地找到最优解.

线性多目标决策的割平面法

木文利用在交互过程中决策者的要求,形成一个割平面.依次逐步逼近决策者的满意解.首次允许决策者修改某个过高要求的目标、提出了更接近于实际决策过程的交互式线性多目标决策的割平面法.文章最后给出了一个实际决策的例子,以说明方法的有效性.

割平面法的改进

通过对解整数规划问题的割平面法中Gomory约束适当交换,给出一种加速获解的办法。

整数线性规划的一种新的割平面法

本文提出了一种新的求解整数线性规划的割平面思路 .它利用目标函数等值面的移动来切割与(IL P)相应的 (SL P)可行域的“无用”部分 ,再通过扩大与 (SL P)最优基相应的非基变量的取值来压缩 (SL P)的可行域 ,由此求得整数线性规划的最优解 .

整数规划割平面法解题新探

该文提出了在使用Ｇｏｍｏｒｙ割平面法解整数规划时，可通过作比较，选出切割条件较强的一个割平面方程或同时取几个割平面方程的方法．可以减少切割次数和计算量．

高莫雷割平面法及其应用研究

本文介绍高莫雷割平面法及其求解森林经理中的人员和设备分配等整型规划问题。通过分析高莫雷割平面法原理,设计算法流程图,并编制程序。在具体实例上对算法进行了测试,结果与现实相符合。

整数规划的有效集割平面法

探讨了用线性规划的有效集法求解整数规划问题，称之为有效集割平面法。有效集割平面法导出割平面方程比单纯形平面法导出割平面方程更为直观、自然，且整个计算过程的计算量大大减少。本文导出的割集平面方程亦可使用于单纯形法。

非线性多目标决策的割平面法

非线性多目标决策的割平面法顾荣忠（河海大学国际工商学院南京２１００９８）非线性多目标决策方法可以分为两大类．一类是非交互式决策方法．即决策者不参予决策过程，仅在一开始就给出他的要求或效用．至于如何求得和为什么获得如此的最后解，决策者全然不知．因而，决...

解变量有上、下界限制的LP问题的一种新割平面法

针对变量有上、下界限制的LP问题,本文给出了求解此类问题的一种简易方法——割平面法,并以实例加以说明。

目标等值面切割定界与割平面法结合求解整数规划

把目标等值面切割定界原理与Gomory的割平面法结合起来求解整数线性规划 (ILP)问题 .首先通过目标函数等值面的平行移动来切去 (LP)可行域中含其非整数最优解但不含 (ILP)可行解的“无用部分” ;然后 ,应用Gomory的割平面在通过 (ILP)最优解的目标等值面上切割其最优解 .

求解线性二层规划的割平面法

基于线性二层规划的全局最优解可在其约束域的极点上达到这一性质,利用约束域顶点的相邻极点产生割平面,设计了一种求解上层带约束的线性二层规划的割平面法,并给出了算例。

整数规划中的割平面法与分枝定界法比较

整数规划是规划论中较新的一个分枝,它是研究决策变量取整数的一类线性规划,主要的解法有割平面法和分枝定界法两种。对它们进行介绍后,通过求解具体问题进行分析比较。

分支定价割平面法求解带时间窗和人力分配的车辆路径问题

本文研究了带时间窗和人力分配的车辆路径问题,并提出用分支定价割平面法来求其最优解。分支定价割平面法首先根据Dantzig-Wolfe分解技术将问题的数学模型分解为基于路径的主问题模型和求最短路径的子问题模型,然后利用列生成和标签算法在主问题和子问题之间进行迭代,并使用割平面法调整可行区域来求得主问题的最优松弛解,最后采用基于车辆数目和弧的分支策略获取原问题的整数解。算法中加入了两种加速策略:双向标签算法和递减搜索空间法。通过对多组算例进行测试,验证了模型和算法的准确性,并分析了患者数目和车辆数目对结果的影响,也说明了割平面法具有提高算法效率的作用。最后,对大规模算例进行测试的结果也为实际应用提供了理论依据。

非线性规划的内割平面法

本文提出了一种非线性凸规划的内割平面法(ICPM),同时说明了与Kelley外割平面法交互使用的方法。并就ICPM算法给出了一个示例。

整数规划中割平面法的研究

割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.