Gomory割平面方法的讨论

Comory割平面法是线性整数规划的求解方法之一。本文利用单纯形和对偶单纯形迭代准则,直接给出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节点系统的数值仿真结果表明,改进算法能够正确处理最优解的各种情况,扩大了内点割平面法的应用范围.

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

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

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

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

带交易费用的投资组合模型的割平面解法(英文)

本文讨论了带交易费用的投资组合模型,因对这一类带二次约束的线性优化间题没有特殊的处理方法,我们利用割平面法使这一非线性优化间题可通过解一系列线性规划间题来求解.

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

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

割平面法的改进

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

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

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

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

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

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

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

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

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

多平面截割平面立体截交线画法研究

截交线作为形体表面交线之一,是《机械制图》教学的重点和难点,多平面截割以单平面截割为基础,是单平面截割的扩展和延伸。文章介绍了多平面截割平面立体的基本思想、画法步骤、三种有效方法及注意的问题。

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

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

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

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

投资组合模型的割平面解法的数值算例

在文献[6]中,我们提出了带交易费用的投资组合模型的割平面解法,本文对文献[6]中的结论进行了论证,并给出了数值算例。

区间上最佳一致逼近解的割平面算法

本文给出了一个求区间上最佳一致逼近解的新方法,该方法用一系列线性规划问题的最优解逼近最佳逼近解,每次迭代充分利用了前次迭代的信息,使计算量大大减少,算法具有一些良好的性质。

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

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

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

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