共查询到20条相似文献,搜索用时 0 毫秒
1.
由于单纯形域上的二次型函数往往是多峰函数,当函数形式较为复杂时难以求得全局最值.构造了两类适用于单纯形上二次型函数优化的算法,分别是单纯形上的Newton-Raphson算法与随机搜索算法.经过实例验证,这两种算法都是有效的. 相似文献
2.
Peter J. Rousseeuw 《Journal of Computational and Applied Mathematics》1983,9(3):279-286
Let X be a real random variable, distributed according to some symmetric distribution F. A searcher starts at the origin and moves with an upper bound on his speed until he finds X. Which search path does he have to choose in order to minimize the expected searching time (or equivalently, to minimize the expected path length)? By means of numerical methods the solution is calculated for the normal, Student, logistic and Laplace distributions. 相似文献
3.
Mahesh N. Dumaldar 《Optimization》2016,65(1):1-7
A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent. 相似文献
4.
D. P. Bertsekas F. Guerriero R. Musmanno 《Journal of Optimization Theory and Applications》1996,88(2):297-320
We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI. 相似文献
5.
M. C. Cheng 《Mathematical Programming》1980,19(1):230-236
The standard linear programming problem with a finite optimum value is considered. We derive new criteria which guarantee that(i) a non-basic variable of a basic feasible solution will remain a non-basic variable of an optimal basic solution; (ii) a basic variable of a basic feasible solution will remain a basic variable of an optimal basic solution. 相似文献
6.
Parallel local search 总被引:2,自引:0,他引:2
We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism
into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between
asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step
and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures
and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search
algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search. 相似文献
7.
Robert E. Tarjan 《Mathematical Programming》1997,78(2):169-177
Thedynamic tree is an abstract data type that allows the maintenance of a collection of trees subject to joining by adding edges (linking) and splitting by deleting edges (cutting), while at the same time allowing reporting of certain combinations of vertex or edge values. For many applications of dynamic
trees, values must be combined along paths. For other applications, values must be combined over entire trees. For the latter
situation, an idea used originally in parallel graph algorithms, to represent trees by Euler tours, leads to a simple implementation
with a time of O(logn) per tree operation, wheren is the number of tree vertices. We apply this representation to the implementation of two versions of the network simplex
algorithm, resulting in a time of O(logn) per pivot, wheren is the number of vertices in the problem network.
Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office
of Naval Research, Contract No. N0014-91-J-1463. Work during a visit to M.I.T. partially supported by ARPA Contract No. 14-95-1-1246. 相似文献
8.
A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log2
N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009. 相似文献
9.
Miles Lubin J. A. Julian Hall Cosmin G. Petra Mihai Anitescu 《Computational Optimization and Applications》2013,55(3):571-596
We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates. 相似文献
10.
《European Journal of Operational Research》2001,129(3):650-662
In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger. 相似文献
11.
We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively. 相似文献
12.
A. R. G. Heesterman 《Numerische Mathematik》1968,12(4):288-306
This paper describes a proposed special algorithm for a certain class of partionable linear programming problems. The matrix defining such a linear programming problem consists of a number of non-zero diagonal blocks, plus some entirely filled rows and dito columns. 相似文献
13.
This paper reports on an experimental study of the distribution of the length of simplex paths for the Optimal Assignment
Problem. We study the distribution of the pivot counts for a version of the simplex method that with essentially equal probabilities
introduces any variable with negative reduced cost into the basis.
In this situation the distribution of the pivot counts turns out to be normally distributed and independent of the actual
cost coefficients, provided these are sufficiently spread out. Further, the mean and standard deviation grow only moderately
with the size of the problem, namely asd
1.8, andd
1.5 respectively for ad×d problem, implying in particular that the pivot counts concentrate around the mean with growingd.
The usual simplex method on the other hand gives a growth ofd
1.6. Hence a large part of the favourable polynomial growth experienced on practical problems may be attributed to the fact that
the simplex paths are rather short on the average, at least for assignment problems. 相似文献
14.
In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm. 相似文献
15.
Fănică Gavril 《Discrete Mathematics》1978,23(3):211-227
Let F be a finite family of non-empty sets. An undirected graph G is an intersection graph for F if there is a one-to-one correspondence between the vertices of G and the sets of F such that two sets have a non-empty intersection exactly when the corresponding vertices are adjacent in G. If this is the case then F is said to be an intersection model for the graph G. If F is a family of paths within a tree T, then G is called a path graph. This paper proves a characterization for the path graphs and then gives a polynomial time algorithm for their recognition. If G is a path graph the algorithm constructs a path intersection model for G. 相似文献
16.
17.
In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n 5/3(loglogn)1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability. 相似文献
18.
An overview on the simplex algorithm 总被引:1,自引:0,他引:1
Hdi Nabli 《Applied mathematics and computation》2009,210(2):479-489
In this paper, the simplex algorithm and its variants are investigated. First, we define a new concept called formal tableau, which leads to derive easily the dual solution from the latest primal table; without any distinction between the original variables and the slack ones. Second, we propose a new method for initializing the simplex algorithm. Unlike the two-phase and the big-M methods, our technique does not involve artificial variables. The computational results reveal that this new method is very favorable especially when the number of artificial variables is significant. Finally, this method will be combined with the notion of formal tableau leading naturally to a second new approach. 相似文献
19.
S Kulluk 《The Journal of the Operational Research Society》2013,64(5):748-761
Neural networks (NNs) are one of the most widely used techniques for pattern classification. Owing to the most common back-propagation training algorithm of NN being extremely computationally intensive and it having some drawbacks, such as converging into local minima, many meta-heuristic algorithms have been applied to training of NNs. This paper presents a novel hybrid algorithm which is the integration of Harmony Search (HS) and Hunting Search (HuS) algorithms, called h_HS-HuS, in order to train Feed-Forward Neural Networks (FFNNs) for pattern classification. HS and HuS algorithms are recently proposed meta-heuristic algorithms inspired from the improvisation process of musicians and hunting of animals, respectively. Harmony search builds up the main structure of the hybrid algorithm, and HuS forms the pitch adjustment phase of the HS algorithm. The performance proposed algorithm is compared to conventional and meta-heuristic algorithms. Empirical tests are carried out by training NNs on nine widely used classification benchmark problems. The experimental results show that the proposed hybrid harmony-hunting algorithm is highly capable of training NNs. 相似文献
20.
I. A. Perekhod 《Journal of Mathematical Sciences》1994,72(5):3354-3358
We consider a parallel-sequential algorithm to find all the solution of a linear Diophantine equation anxn + an — 1xn — 1 + +a1x1 = b, ai, b, xi Z+ by the method of dynamic upper bounds. Parallel processing and dichotomizing search are responsible for logarithmic time complexity of the algorithm. The auxiliary table memory requirements are 3n words. The algorithm can be applied in linear integer programming problems.Simferopol' University. Translated from Dinamicheskie Sistemy, No. 10, pp. 111–117, 1992. 相似文献