共查询到20条相似文献,搜索用时 62 毫秒
1.
首先给出了单背包问题的秩1半定松驰规划,然后在此基础上提出了求解该问题的半定松驰随机算法KSSD。分析结果表明:(1)当σ>0.19时,算法KSSD的近似比就会超过0.27。(2)算法KSSD中的参数θ对某种大规模情形将不起作用。 相似文献
2.
The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3. 相似文献
3.
4.
5.
本文讨论半光滑牛顿算法的基本概念与其在求解半定优化问题中的应用.特别地,该算法可用于求解线性或非线性半定互补问题.本文同时综述最近在矩阵方程,增广拉格朗日公式和半定优化稳定性方面的、源于半光滑牛顿算法的理论成果. 相似文献
6.
二次半定规划问题及其投影收缩算法 总被引:1,自引:0,他引:1
In this paper,we discuss the relations among the quadratic semi-definite programming problem,the linear semi-definite porgramming and the linearquadratic semi-definite programming problem.The duality theories are presented.After proving the equivalence of its optimality conditions and monotonous linear variational inequalities,we use the projection and contraction algorithms to solve(QSDP),We present the algorithms and its convergence analysis. 相似文献
7.
8.
9.
《数学的实践与认识》2015,(12)
在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性. 相似文献
10.
11.
Da-chuanXu Ji-yeHan 《计算数学(英文版)》2003,21(3):357-366
Using outward rotations,we obtain an approximation algorithm for Max-Bisection problem,i.e.,Partitioning the vertices of an unirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges.In many interesting cases,the algorithm performs better than the algorithms of Ye and of Halperin and Zwick .The main tool used to obtain this result is semidefinite programming. 相似文献
12.
Christian Prins Caroline Prodhon Roberto Wolfler Calvo 《Annals of Operations Research》2006,147(1):23-41
This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem.
The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual
Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several
potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many
Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover,
the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz. 相似文献
13.
稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。 相似文献
14.
Alvim Adriana C.F. Ribeiro Celso C. Glover Fred Aloise Dario J. 《Journal of Heuristics》2004,10(2):205-229
We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms. 相似文献
15.
A New Lagrangian Relaxation Based Algorithm for a Class of Multidimensional Assignment Problems 总被引:2,自引:0,他引:2
Aubrey B. Poore Alexander J. Robertson III 《Computational Optimization and Applications》1997,8(2):129-150
Large classes of data association problems in multiple targettracking applications involving both multiple and single sensorsystems can be formulated as multidimensional assignment problems.These NP-hard problems are large scale and sparse with noisyobjective function values, but must be solved inreal-time. Lagrangian relaxation methods have proven to beparticularly effective in solving these problems to the noise levelin real-time, especially for dense scenarios and for multiple scansof data from multiple sensors. This work presents a new class ofconstructive Lagrangian relaxation algorithms that circumvent some ofthe deficiencies of previous methods. The results of severalnumerical studies demonstrate the efficiency and effectiveness of thenew algorithm class. 相似文献
16.
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP
relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point
cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting
planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP
relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a
standard SDP cutting plane scheme.
Research supported in part by NSF grant numbers CCR–9901822 and DMS–0317323.
Work done as part of the first authors Ph.D. dissertation at RPI. 相似文献
17.
Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem.
We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation
and illustrate its practical value by solving large-scale instances of the p-median problem.
This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish
government, MCYT subsidy dpi2002-03330. 相似文献
18.
19.
基于改进遗传算法的集合覆盖问题 总被引:1,自引:0,他引:1
集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的. 相似文献
20.
刘铎 《数学的实践与认识》2006,36(11):123-128
从组合学的角度研究了一类随机选取集合中元素的覆盖问题,得到了重复性地、随机独立地、等概地选取某个有限集合中的元素,不遗漏地取遍所有元素所需的次数的期望,给出了理论和实验的数据结果.并且分析了该问题在现实世界中的一些实例.而且对于该问题的扩展模型—每次抽取集合中t个不同元素—进行了一些探讨. 相似文献