带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对其他顾客的服务质量.研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题.该问题是无容量设施选址问题的推广.问题可描述如下:给定设施集合、顾客集,以及设施开设费用和顾客...     

带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

随机容错设施布局问题的近似算法

在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.     

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

带惩罚的动态设施选址问题的近似算法

本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第-个近似比为1.8526的原始对偶(组合)算法.     

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有$k$种不同的产品,每一客户均需要$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有$k$个设施来为其提供$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于$k$-种产品设施选址问题,我们通常简写为$k$-PUFLP,其中,当所有设施建设费用为0时,记为$k$-PUFLPN。本文对$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当$k\geq 3$时分析算法将$k$-PUFLPN的近似比从$\frac{3k}{2}-1$提升到了$\frac{3k}{2}-\frac{3}{2}$。鲁棒$k$-种产品设施选址问题是指在该问题中,最多有$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒$k$-种产品选址问题建立模型,当$k\geq 3$,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用$k$-PUFLPN中最优整数解与最优分数解的关系,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

设施选址问题的近似算法综述

设施选址问题是运筹学和理论计算机科学中的经典问题之一.本文介绍设施选址问题及其变形的近似算法设计与分析思想,并总结设施选址问题的研究中若干未解决的重要问题.     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

软容量约束的动态设施选址问题的近似算法

考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.     

稠密平分子图与表压缩问题的近似算法

给出两个NP问题(稠密平分子图和表压缩)的改进的近似算法. 基于半定规划(SDP)松弛和巧妙的舍入技巧, 首先给出稠密平分子图问题(DSP)的0.5982-近似算法, 表压缩问题(TCP)的0.5970-近似算法. 然后, 通过增加三角不等式得到更紧的SDP松弛, 把前面的比值分别改进到0.6243和0.6708. 针对TCP得到的结果改进了简单贪婪算法的0.5近似比, 因此回答了Anderson提出的未解决问题.     

两阶段选址优化问题研究

本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。     

Pm‖Cmax问题的算法AKK的一个改进的最坏情况性能比

本文考虑的是平行机排序问题Pm‖Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1＋1-1/m/1＋｜k/m｜,而且当k≡0（modm）时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比： 1＋max{1-1/m/1＋k1＋1/m,1-1/m-k2/1＋k1},其中k1和k2为非负整数且k1m＋k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.     

Pm||C_(max)问题的算法A_(KK)的一个改进的最坏情况性能比(英文)

本文考虑的是平行机排序问题Pm||Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1 (1-1/m/1 |k/m|),而且当k(?)0(modm)时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比:1 max{1-1/m/1 k1 1/m,1-1/m-k2/1 k1},其中k1和k2为非负整数且k1m k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.     

排序问题的线性规划松弛方法

本文研究排序问题的线性规划松弛方法，对单台机器排序问题1｜prec｜∑wjCj介绍基于三个确定性线性规划松弛的2一近似算法，对平行机排序问题R｜rij｜（wjCj）介绍基于随机线性规划松弛的2-近似算法。这后一个算法对排序问题R｜（wjCj｜是3／2-近似算法．     

一类混合0-1非凸二次约束二次规划问题的近似算法

研究一类混合0-1非凸二次约束二次规划问题的近似算法.该问题是在M个非凸二次约束与一个基数约束下,求解一个n维向量的极小范数,变量包含M个0-1变量与一个n维连续向量.该问题是NP-难的.在求解其半正定规划(SDP)松弛问题的基础上,提出了一种随机舍入算法,能够得到原始的问题的一个可行解.数值仿真实验结果表明该方法是十分有效的.