A Tabu Search Algorithm for Quadratic 0-1 Programming Problem

In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .

Global optimality conditions for quadratic 0-1 programming with inequality constraints

Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.

基于混合变量的0-1线性规划模型及应用

通过模型对混合的0-1线性规划问题进行求解,并通过具体的实例与传统的排序法、隐枚举法等进行对比,相比较于传统方法只能处理数据较少的整数的简单运算,优化的模型则能够对于计算量繁多且带有小数的数据进行有效且快速的运算处理。文中的模型简单便捷,融合性很高,只需输入相应数据,即可进行优化。

考虑观测冗余度最大的0-1线性规划电力系统PMU最优配置

提出一种0-1线性规划PMU优化配置模型。该模型通过求解单目标规划问题实现了PMU设备数量和系统观测冗余度2个目标同时达到最优,简化了计算过程,保证了解的全局最优性。该模型的严谨性得到了严格的数学证明。对118节点、300节点等IEEE标准系统的仿真验证了该模型的有效性。文中PMU优化结果与其它文献结果的对比体现了该模型的优越性。最后将该算法应用于三华电网系统,证明了该模型的实用性。

基于点-弧结构的路网单组列车编组计划优化线性0-1规划模型

合理编制和执行货物列车编组计划,是提高铁路网车流组织效率和运输服务质量的重要保证。研究路网单组列车编组计划优化问题,基于多商品网络流点-弧模型的建模框架,设置每支列流的径路选择和每支车流的改编决策都为0-1变量。以列车集结耗费和车流改编耗费总和最小为目标,考虑车站改编能力和调车线数约束,引入辅助变量和线性约束刻画接续归并原则,建立线性0-1规划模型。对于19个站、23条边、314支车流的小规模算例,CPLEX在1 s内求到最优,验证模型的正确性。对于83个站、158条边、平均5700支车流的大规模算例,相比既有模型与算法,本文模型在相同时间限制内均能求得高质量解,且该模型线性松弛平均14 min求到最优,提供更紧的下界,验证模型的有效性。

基于0-1整数线性规划的军事空运装载优化算法

为了高效地制定军事空运装载方案,在分析空运物资和载机货舱特点的基础上,构建了6种待装物资类型模式和6种承载空间物资布局模式,将三维空运装载问题转化为二维装载问题,建立了军事空运装载问题的数学模型.通过构建空间布局转化模式,将空间布局约束转换成0-1整数线性约束,实现了对0-1整数线性规划空运装载问题的求解.仿真结果表明:该算法运算时间不超过1 s,装载方案平均载重率达38.8%,平均有效空间利用率达59.7%.

优化列车编组计划的0-1规划法

首先对文献[1]所建立的整数规划模型作了改进,把列车编组计划问题描述为一个线性0-1规划模型,并与现有模型进行了比较。然后,以文献[2]提出的求解0-1规划的有序组合树法为基础,根据问题的特殊性质作了一些特殊处理,从而大大压缩了计算范围。同时提出一种分解技术,大幅度节省了存贮空间,并为并行算法的设计提供了条件。最后介绍了利用微机计算的初步结果。

0-1线性规划的连续化求解方法

针对0-1线性规划的优化问题,提出一种惩罚函数方法。考虑到0-1线性规划的最优值特征,通过在目标函数中加上惩罚函数,将0-1离散线性规划模型连续化成非线性规划模型,并使用Matlab的Fmincon函数进行求解。经对多个算例的计算,并和其他算法比较,结果表明惩罚函数法的可行性和有效性。将该方法应用于实际的飞机排班问题上,取得比较满意的结果。

铁路网上技术直达列车编组计划优化的二次0-1规划法

以文献[1]的构模原理为基础,构造了任意结构的路网上双方向技术直达列车编组计划综合优化的二次0-1规划模型,然后给出了这类模型的若干理论结果,并在此基础上介绍了模型的解法、计算试验结果及分析。

一种求解多目标0-1规划问题的自适应粒子群算法

对于带有线性约束的多目标0-1规划问题,给出了一种自适应的粒子群优化算法。该算法利用变换来控制模型的线性约束,并通过对各目标函数进行自适应加权的方式形成适应度函数。数值结果表明该算法是有效的,可以求解实际应用中的一些模型。

线性0-1规划模型的排序解法

针对 0 1规划模型提出了一种新的解法 ,即排序法。它利用目标函数变量系数绝对值大小的相对关系 ,对无约束条件解进行排序 ,在最小解集中寻找最优解 ,以加快收敛速度。

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法,分枝的过程是普通的0-1变量分枝,用简单的取整启发式法确定更好的可行解;而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近,由此得到最优值的一个下界.数值结果表明所提出的算法是有效的,可以求解中等规模的问题.

多核集群任务分配问题的0-1整数规划求解模型

研究了典型多核集群任务分配中的节点内通讯特性。基于0-1整数非线性规划模型和线性松弛技术,给出了一种0-1整数线性规划任务分配问题求解优化模型。由于节点内的通讯量与通讯延迟较大,以最小化计算代价和节点间通讯代价为研究目标的传统求解模型具有严重的局限性,而该求解模型考虑了节点内通讯代价,并采用了线性规划松弛技术,其目标是最小化计算代价、节点间通讯代价和节点内通讯代价。计算结果验证了提出的模型的有效性。

0-1线性规划问题的分类隐数搜寻

针对0-1线性规划问题,提出一种新的分类隐数搜寻方法.该算法将所有的0-1整数点分类,并产生一个描述性的线性方程,由此构造了一组非常好的隐数条件和隐数准则,这样可以排除大量不可行解的列举,大大加快了隐数搜寻过程,并通过几个经典算例的计算结果及与Balas算法的计算结果比较,证实了本算法的高效性.

基于矩阵分解的0-1二次规划的SDP松弛

0-1二次规划是整数规划中一类重要的最优化问题,广泛应用于工程、经济管理、金融和管理科学等许多重要领域.利用矩阵分解方法,给出了带线性约束的0-1二次规划的一个紧的SDP松弛.通过目标函数的矩阵分解并利用二次项的片段线性逼近技术,得到了原问题的一个凸松弛.再利用锥优化对偶性,证明了寻找凸松弛中的最优参数问题可以归结为求解一个SDP问题,数值结果也表明该SDP松弛能提供原问题的一个更紧的下界.

鲁棒混合0-1多项式规划

针对含误差数据的混合0-1多项式优化问题,给出一种鲁棒优化方法,以提高其最优解的鲁棒性。该方法先将原问题转化为混合0-1线性规划,并在最坏情况下给出混合0-1线性规划的鲁棒对应模型,随后利用该鲁棒对应模型求解原优化问题。数值试验表明,该方法所求出的最优解具有良好的鲁棒性。

一种求解0-1背包问题的置信传播算法

针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包问题的置信传播算法。当算法收敛时,计算每个物体节点的置信度,以确定该物体的装包概率,从而高概率地给出0-1背包问题的解。与其他启发式算法进行了比较,结果表明,该算法具有较好的全局搜索能力。

0-1整数规划问题的稀疏解求解模型研究

本文研究了0-1整数规划问题的稀疏解的求解模型,运用线性互补约束得到了该问题的连续优化模型,并运用最优性条件考虑了两个模型解之间的关系,为模型的进一步求解和算法设计提供了理论的基础和保证.

解0-1线性规划问题的最小部分系数和法

本文提出一种新的求解 0 - 1线性规划问题的方法———最小部分系数和法 ,用它来求解 0 - 1线性规划问题比现行的隐枚举法往往要便捷得多。

乌鲁木齐市城建系统1999～2003年投资优化模型的研究

根据乌鲁木齐市近几年的城市设施水平、2 0 0 0年规划、2 0 10年远景目标 ,制定了 1999～2 0 0 3年阶段性目标 .对实现阶段性目标所需投资、这五年的城市设施建设财政拨款做了概算 .在拨款不足的条件限制下 ,运用 0 - 1规划优化模型 ,探讨如何使有限的财政拔款 ,发挥尽可能大的社会、经济和环境效益 .