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.

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 .

线性双曲最优控制问题的P^(2)_(0)-P_(1)混合有限元方法的先验误差估计

针对线性双曲最优控制问题,通过非标准的P^(2)_(0)-P_(1)混合有限元方法,利用椭圆投影、标准L^(2)投影、标准L^(2)-正交投影算子等理论,其中状态和对偶状态采用P^(2)_(0)-P_(1)混合有限元逼近,控制变量采用分片常数逼近,给出问题模型中所有变量的先验误差估计.

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

LINGO语言与0-1混合整数规划选址模型的再结合

目前现有的将LINGO语言和O-1整数规划模型结合解决物流配送中心选址的理论较多,但不完善,主要表现在建模时对费用的考虑不全面、编程时所使用的变量不统一和求解时使用的是算例,数据真实性不高。针对以上问题,论文对LINGO语言与0-1混合整数规划选址模型进行再结合。首先把与配送相关的物流活动分为进货、仓储和送货三大物流环节,由此将配送中心选址中所涉及到的费用分为进货运输费用、仓储费用和送货配送费用;其次对建模所涉及到变量进行科学的规范,并成功建立O-1整数规划模型;最后以邯郸交通运输集团物流配送中心选址为实例,运用所建立的0-1混合整数规划模型,编写相应的LINGO求解程序,通过运行得出邯运集团在石家庄、北京、邯郸建立配送中心此时费用最少,最终到达LINGO语言与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多项式规划

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

基于矩阵分解的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规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现。该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性。实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高。算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解。