An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments

We present an exact and efficient branch-and-bound algorithm MCR for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular type of graph. It employs approximate coloring to obtain an upper bound on the size of a maximum clique along with an improved appropriate sorting of vertices. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that in general, our algorithm decidedly outperforms other existing algorithms. The algorithm has been successfully applied to interesting problems in bioinformatics, image processing, design of quantum circuits, and design of DNA and RNA sequences for biomolecular computation.     

On an optimal control problem involving first order hyperbolic systems with boundary controls

In this paper, we consider an optimal control problem involving a class of first order hyperbolic systems with boundary controls. A computational algorithm which generates minimizing sequences of controls is devised and the convergence properties of the algorithm are investigated. Moreover, a necessary and sufficient condition for optimality is derived and a result on the existence of optimal controls is obtained.     

一种求模糊矩阵传递闭包的基于幂序列单增矩阵构造的新算法

引入幂序列单增模糊矩阵的概念并讨论它的性质, 给出一种基于幂序列单增模糊矩阵构造的求模糊关系矩阵传递闭包的新算法; 并通过与现有的两种传递闭包求解算法的比较分析, 借助实例说明了算法的有效性和简洁性.     

m个对角元有正增量的对称正定方程组的解

1　引　　言某些问题的数值求解要作迭代计算 ,每次迭代需求解一个系数矩阵仅有少量变化的线性方程组 .如何减少求解该方程组的计算量 ,便成为提高总体计算效率的关键之一 .这类问题往往在一些优化问题的求解过程中遇到[1] ,因此值得研究 .为此考虑如下的问题Ⅰ .问题Ⅰ　设某问题的数值求解过程要作迭代计算 ,每次迭代需求解一个线性方程组(Ａ+Ｄ)Ｘ =ｂ ( 1 .1 )其中Ａ为ｎ阶对称正定矩阵 ,ｂ为已知向量 ,Ｄ =ｄｉａｇ(ｄ1,ｄ2 ,… ,ｄｎ) ,( 1 .2 )且Ｄ的对角元ｄｉｋ>0 ,ｋ =1 ,2 ,… ,ｍ ,1≤ｉ1<ｉ2 <… <ｉｍ ≤ｎ ,ｄｉｋ及其位置和…     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

The computation of a general equilibrium in a public goods economy

This paper presents an algorithm for computing approximations to a certain subset of Pareto optimal allocations in a public goods economy. Consumers are partitioned into a number of exogenous governmental jurisdictions, which provide public goods locally and raise revenue to cover their costs by means of a proportional wealth tax. The Pareto optimal allocations studied are consistent with profit maximization on the part of producers, and utility maximization over private goods bundles subject to after-tax budget constraints by consumers. The computational routine is based on the Scarf algorithm for computing fixed points.The origins of this research date back to the Dartmouth Workshop on Applications to economics of new methods of computing fixed points, held during the summer of 1972 under the direction of H. Scarf. The author wishes to thank the participants in this workshop for many stimulating discussions. Also the provision of computer time by the Computer Research Center of the National Bureau of Economic Research is gratefully acknowledged. FIXPOINT, an interactive computer system developed at the Computer Research Center, was used in performing the numerical computations presented in the paper.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

An efficient simplicial algorithm for computing a zero of a convex union of smooth functions

We present an efficient simplicial algorithm for computing a zero of a point-to-set mapping that is formed by piecing together smooth functions. Such mappings arise in nonlinear programming and economic equilibrium problems. Our algorithm, under suitable regularity conditions on the problem, generates a sequence converging at least Q-superlinearly to a zero of the mapping. Asymptotically, it operates in a space of reduced dimension, analogous to an active set strategy in the optimization setting, but it switches active sets automatically. Results of computational experiments are given. Research of this author was supported by a Fellowship from the Rockeffeller Foundation. Research of this author was partially supported by a fellowhip from the John Simon Guggenheim Memorial Foundation and by National Science Foundation Grant ECS-7921279.     

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

On the rotating Navier-Stokes equations with mixed boundary conditions

The stationary and nonstationary rotating Navier-Stokes equations with mixed boundary conditions are investigated in this paper. The existence and uniqueness of the solutions are obtained by the Galerkin approximation method. Next, θ-scheme of operator splitting algorithm is applied to rotating Navier-Stokes equations and two subproblems are derived. Finally, the computational algorithms for these subproblems are provided.     

A new linesearch algorithm for nonlinear least squares problems

A linesearch (steplength) algorithm for unconstrained nonlinear least squares problems is described. To estimate the steplength inside the linesearch algorithm a new method that interpolates the residual vector is used together with a standards method that interpolates the sums of squares. Numerical results are reported that point out the advantage with the new steplength estimation method.     

A Greedy Algorithm for Capacitated Lot-Sizing Problems

We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O ( n ) time.     

A parametric linear complementarity technique for the computation of equilibrium prices in a single commodity spatial model

This paper presents a parametric linear complementarity technique for the computation of equilibrium prices in a single commodity spatial model. We first reformulate the model as a linear complementarity problem and then apply the parametric principal pivoting algorithm for its solution. This reformulation leads to the study of an arc—arc weighted adjacency matrix associated with a simple digraph having weights on the nodes. Several basic properties of such a matrix are derived. Using these properties, we show how the parametric principal pivoting algorithm can be greatly simplified in this application. Finally, we report some computational experience with the proposed technique for solving some large problems.     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。     

The Markov Model Based Algorithm to Predict Networking Load on the Computational Grid

The computational Grid is currently gaining in popularity, and it enables computers scattered all over the world to be connected by the Internet as if they are part of a large computational infrastructure. While the computational Grid gathers more and more computational resources and the number of the applications for the computational Grid is increasing, load balancing for the computational Grid is still not effective enough. Because the computers are connected by a wide area network on the computational Grid, the significant communication latency and the frequency of large wave throughputs make it difficult to achieve effective load balancing. Thus, in this paper, we propose an algorithm to predict networking loads on the computational Grid to make the use of computational resources more efficient. The proposed algorithm based on the Markov model is evaluated using an actual networking load. As a result, the Markov model based algorithm offers the most accurate predictions compared with the related work. This revised version was published online in July 2006 with corrections to the Cover Date.     

A simple fast hybrid pattern-matching algorithm

The Knuth–Morris–Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the Boyer–Moore (BM) algorithm provides near-optimal average-case and best-case behaviour, as well as executing very fast in practice. We describe a simple algorithm that employs the main ideas of KMP and BM (with a little help from Sunday) in an effort to combine these desirable features. Experiments indicate that in practice the new algorithm is among the fastest exact pattern-matching algorithms discovered to date, apparently dominant for alphabet size above 15–20.     

Sequencing by hybridization: an enhanced crossover operator for a hybrid genetic algorithm

This paper presents a genetic algorithm for an important computational biology problem. The problem appears in the computational part of a new proposal for DNA sequencing denominated sequencing by hybridization. The general usage of this method for real sequencing purposes depends mainly on the development of good algorithmic procedures for solving its computational phase. The proposed genetic algorithm is a modified version of a previously proposed hybrid genetic algorithm for the same problem. It is compared with two well suited meta-heuristic approaches reported in the literature: the hybrid genetic algorithm, which is the origin of our proposed variant, and a tabu-scatter search algorithm. Experimental results carried out on real DNA data show the advantages of using the proposed algorithm. Furthermore, statistical tests confirm the superiority of the proposed variant over the state-of-the-art heuristics.     

Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach

In computational biology, genome rearrangements is a field in which we investigate the combinatorial problem of sorting by transpositions. This problem consists in finding the minimum number of transpositions (mutational event) that transform a chromosome into another. Bafna and Pevzner [SIAM J. 11 (2) (1998) 224–240] proposed a 1.5-approximation algorithm to solve this problem, using a structure called cycle graph. In this work, we first present results that allowed us to implement their algorithm, maintaining the 1.5-approximation ratio. The present implementation runs in O(n³) time complexity, noting that we created a data structure to store the cycle graph in memory in O(n) time complexity. The results obtained from the program allowed us to propose heuristics, that further improved the performance of the original algorithm. Comparing our experimental results with the best results published so far, we achieved better performance. Besides, we developed a program to visualize the cycle graphs and the transpositions indicated by the algorithm. This work targets to contribute for discovering the complexity of the problem of sorting by transpositions, which remains open.