GPU accelerated pivoting rules for the simplex algorithm

Simplex type algorithms perform successive pivoting operations (or iterations) in order to reach the optimal solution. The choice of the pivot element at each iteration is one of the most critical step in simplex type algorithms. The flexibility of the entering and leaving variable selection allows to develop various pivoting rules. In this paper, we have proposed some of the most well-known pivoting rules for the revised simplex algorithm on a CPU–GPU computing environment. All pivoting rules have been implemented in MATLAB and CUDA. Computational results on randomly generated optimal dense linear programs and on a set of benchmark problems (Netlib-optimal, Kennington, Netlib-infeasible, Mészáros) are also presented. These results showed that the proposed GPU implementations of the pivoting rules outperform the corresponding CPU implementations.     

Multiloop transportation simplex algorithm

In large-scale transportation problems (TPs), various methods have been developed to obtain an optimal solution. One of the methods is the transportation simplex algorithm (TSA), which obtains an optimal solution for TP. Various heuristic methods have been developed to find an initial basic feasible solution for transportation algorithms. These methods differ in terms of computational cost and finding good initial solution. In TSA, the better the basic feasible solution, the less the number of iterations the algorithm will run. At each step, it uses pivoting operation, where a loop involving the nonbasic variable with the largest cost reduction is determined. Then, it eliminates the entering basic variable. However, for large-scale problems, even the best basic feasible solution may result in high number of iterations. In this paper, we present a novel algorithm called multiloop transportation simplex algorithm which finds multiple independent loops during pivoting operation. This causes larger cost reductions in every iteration. We experimentally show that the average number of iterations and runtime to solve the TP are dramatically reduced.     

A Rigorous Global Filtering Algorithm for Quadratic Constraints*

This article introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.*This article is an extended version of [23].     

A differential evolution algorithm for joint replenishment problem using direct grouping and its application

There has been much work in establishing joint replenishment model and designing effective and robust algorithms. Little research has been done by direct grouping methods. In this paper, we present a differential evolution (DE) algorithm that uses direct grouping to solve joint replenishment problem (JRP). Extensive computational experiments are performed to compare the performances of the DE algorithm with results of evolutionary algorithm (GA). The experimental results indicate that the DE algorithm can find a replenishment policy that incurs a lower total cost than the GA. We also conducted a case study to test the proposed DE algorithm for the JRP. The findings suggest that the proposed model is successful in decreasing spare parts ordering costs and holding costs significantly in a power plant.     

An efficient local search for partial vertex cover problem

In this paper, an efficient local search framework, namely GRASP-PVC, is proposed to solve the minimum partial vertex cover problem. In order to speed up the convergence, a novel least-cost vertex selecting strategy is applied into GRASP-PVC. As far as we know, no heuristic algorithms have ever been reported to solve this momentous problem and we compare GRASP-PVC with a commercial integer programming solver CPLEX as well as a 2-approximation algorithm on two standard benchmark libraries called DIMACS and BHOSLIB. Experimental results evince that GRASP-PVC finds much better partial vertex covers than CPLEX and the approximation algorithm on most instances. Additional experimental results also confirm the validity of the least-cost vertex selecting strategy.

     

非线性优化方法在脑电逆问题中的应用与比较

讨论了基于单纯形法(Simplex)、阻尼最小二乘法(LM)方法、混合遗传算法(HGA)等非线性优化方法的脑电偶极子定位问题.仿真结果表明,这些算法在一定条件下均可使用,比较而言Simplex、LM法有 较快的计算速度,而HGA耗时较多.另一方面HGA 对迭代初值要求不高,而Simplex、LM则对此有一定的 要求.特别在对多偶极子源求解时,Simplex、LM有时因初值选择困难而失效,而HGA仍然是有效的.􀁱     

语义对等覆盖网中社区结构的发现和评价

最近,通过建立语义覆盖网络来提高大规模分布式网络环境中信息检索服务的性能成为对等计算领域的研究热点.目前,研究者们在语义覆盖协议和搜索算法方面已经做了大量研究,证明了语义覆盖在基于对等网络模型的内容定位应用方面极为有效.然而,分析和评价语义覆盖网络特征的研究工作确非常有限.文中通过建立数学模型和设计启发式回溯-贪婪混合算法、确认了语义覆盖网络的一种主要内在特性——社区结构特性.利用评价模型比较了SemreX语义覆盖网络和Gnutella网络的性能,实验结果显示SemreX覆盖网具有显著的社区结构特征,而Gnutella网络却没有这样的特征.另外,通过分别在两种覆盖网中仿真洪泛协议发现具有显著社区结构特征的覆盖网在内容定位方面效率更高.     

A Conjecture on Wiener Indices in Combinatorial Chemistry

Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of the molecule, and covalent bonds between atoms are represented by edges between the corresponding vertices. This polygonal shape derived from a chemical compound is often called its molecular graph, and can be a path, a tree, or in general a graph. An indicator defined over this molecular graph, the Wiener index, has been shown to be strongly correlated to various chemical properties of the compound. The Wiener index conjecture for trees states that for any integer n (except for a finite set), one can find a tree with Wiener index n. This conjecture has been open for quite some time, and many authors have presented incremental progress on this problem. In this paper we present further progress towards proving this conjecture—through the design of efficient algorithms, we show that enumerating all possible trees to verify this conjecture (as done by all the previous approaches) is not necessary, but instead searching in a small special family of trees suffices, thus achieving the first polynomial (in n) time algorithm to verify the conjecture up to integer n. More precisely, we (i) present an infinite family of trees and prove various properties of these trees, (ii) show that a large number of integers, up to at least 10⁸ (compared with the previous best 10⁴) are representable as Wiener indices of trees in this succinct family, (iii) provide several efficient algorithms for computing trees with given Wiener indices, and (iv) implement our algorithms and experimentally show that their performance is asymptotically much better than their theoretical worst-case upper bound.     

A Simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design

The network design is a well-known problem, both of practical and theoretical significance. Network design models are extensively used to represent a wide range of planning and operations management issues in transportation, telecommunications, logistics, production and distribution. This paper presents a solution method for node-arc formulation of capacitated fixed-charge multicommodity network design problems. The proposed method is a hybrid algorithm of Simplex method and simulated annealing metaheuristic. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method is used to evaluate, select and implement the moves. In the proposed algorithm, the neighborhood structure is pivoting rules of the Simplex method that provide an efficient way to reach the neighbors of current solution. To evaluate the proposed algorithm, the standard problems with different sizes are used. The algorithm parameters are tuned by design of experiments approach and the most appropriate values for the parameters are adjusted. The performance of the proposed algorithm is evaluated by statistical analysis. The results show high efficiency and effectiveness of the proposed algorithm.     

多目标微粒群优化算法及其应用研究进展*

多目标微粒群优化(MOPSO)算法是一类基于群体智能的新型全局多目标优化方法,已受到广泛关注,并在许多领域得到应用。针对近几年来MOPSO算法及其应用的进展进行了综述和评论。首先描述了MOPSO算法的基本框架;接着对MOPSO算法进行了分类和分析,并给出了MOPSO算法的一些改进策略;然后介绍了MOPSO算法的应用进展;最后,展望了MOPSO算法值得进一步研究的方向。     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

Acceleration of sweep-line technique by employing smart quicksort

Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm ‘vertex sort’. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertex sort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (in linear time) than random cases. We have named the combined algorithm ‘smart quicksort’ because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.     

A hybrid ant colony optimization algorithm for optimal multiuser detection in DS-UWB system

A hybrid ant colony optimization algorithm is proposed by introducing extremal optimization local-search algorithm to the ant colony optimization (ACO) algorithm, and is applied to multiuser detection in direct sequence ultra wideband (DS-UWB) communication system in this paper. ACO algorithms have already successfully been applied to combinatorial optimization; however, as the pheromone accumulates, we may not get a global optimum because it can get stuck in a local minimum resulting in a bad steady state. Extremal optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of optimization problems. Hence in this paper, a hybrid ACO algorithm, named ACO-EO algorithm, is proposed by introducing EO to ACO to improve the local-search ability of the algorithm. The ACO-EO algorithm is applied to multiuser detection in DS-UWB communication system, and via computer simulations it is shown that the proposed hybrid ACO algorithm has much better performance than other ACO algorithms and even equal to the optimal multiuser detector.     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

Using partial evaluation in holistic subgraph search

Because of its wide application, the subgraph matching problem has been studied extensively during the past decade. However, most existing solutions assume that a data graph is a vertex/edge-labeled graph (i.e., each vertex/edge has a simple label). These solutions build structural indices by considering the vertex labels. However, some real graphs contain rich-content vertices such as user profiles in social networks and HTML pages on the World Wide Web. In this study, we consider the problem of subgraph matching using a more general scenario. We build a structural index that does not depend on any vertex content. Based on the index, we design a holistic subgraph matching algorithm that considers the query graph as a whole and finds one match at a time. In order to further improve efficiency, we propose a “partial evaluation and assembly” framework to find subgraph matches over large graphs. Last but not least, our index has light maintenance overhead. Therefore, our method can work well on dynamic graphs. Extensive experiments on real graphs show that our method outperforms the state-of-the-art algorithms.     

结合用户信任模型的协同过滤推荐方法研究

协同过滤推荐是当前最成功的推荐技术之一,在电子商务推荐服务中得到了广泛的应用,它根据和目标用户具有相似行为的用户对项目的评价来进行推荐。鉴于传统的协同过滤推荐算法过于强调相似性的作用,并且和用户的认知习惯矛盾,引入了社会学中较成熟的信任机制来改进传统算法。实验结果表明,改进方法是有效的,它和传统的协同过滤推荐算法相比有更好的推荐质量。     

基于节点相似度的网络社团检测算法研究

社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SUN,相比传统的基于边界数(betweenness)的节点分裂算法GN, SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。     

Localized Operations for Distributed Minimum Energy Multicast Algorithm in Mobile Ad Hoc Networks

To explore the advantages of power saving offered by the wireless multicast advantage property, we consider the case of source-initiated multicast traffic. Current research activity for the minimum energy multicast (MEM) problem has been focused on devising efficient centralized greedy algorithms for static ad hoc networks. In this paper, we consider mobile ad hoc networks (MANETs) that use omnidirectional antennas and have limited energy resources. We propose the design and initial evaluation of the distributed minimum energy multicast (DMEM) algorithm for MANETs that attempts to reduce as much as possible the total RF energy required by the multicast communication. Several localized operations are presented for the DMEM algorithm, in which each node requires only the knowledge of and distances to all neighboring tree nodes. Through extensive simulation studies, we show that these operations are very efficient both in terms of energy saving and operation overhead     

一种基于网格地理哈希表的无线传感器网络数据分发算法

无线传感器网络是一种新型数据监测网络，其重要特性是传感器节点的能量有限，一般依靠电池驱动，能量效率是传感器网络设计最重要的考虑因素。GHT-DCS是一种新型能量高效的数据分发方式，能在数据的查询和存储之间取得一种平衡。但是，采用GHT-DCS机制的能量效率仍然有改进的空间。本文提出了一种基于网格GHT的数据分发算法，也是一种以数据为中心的存储，并在此算法的基础上提出了一种基于索引存储的网格GHT数据分发算法，能更进一步提高能量效率。本文对这两种算法进行了性能分析，与原有的GHT算法进行了性能对比。分析表明，这两种算法在性能上都比原GHT算法有很大改进，而复杂度增加较少，是能量更加高效的数据分发算法。     

Local search with edge weighting and configuration checking heuristics for minimum vertex cover

The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution.A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms.