首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
1 ,E2,..., such that ⋃i≤τEi optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all Ei are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999  相似文献   

2.
This paper investigates the use of multi-objective methods to guide the search when solving single-objective optimisation problems with genetic algorithms. Using the job shop scheduling and travelling salesman problems as examples, experiments demonstrate that the use of helper-objectives (additional objectives guiding the search) significantly improves the average performance of a standard GA. The helper-objectives guide the search towards solutions containing good building blocks and help the algorithm escape local optima. The experiments reveal that the approach works if the number of simultaneously used helper-objectives is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically. The experiments reveal that for the majority of problem instances studied, the proposed approach significantly outperforms a traditional GA.The experiments also demonstrate that controlling the proportion of non-dominated solutions in the population is very important when using helper-objectives, since the presence of too many non-dominated solutions removes the selection pressure in the algorithm.  相似文献   

3.
Hesitant adaptive search is a stochastic optimisation procedure which accommodates hesitation, or pausing, at objective function values. It lies between pure adaptive search (which strictly improves at each iteration) and simulated annealing with constant temperature (which allows backtracking, or the acceptance of worse function values). In this paper we build on an earlier work and make two contributions; first, we link hesitant adaptive search to standard counting process theory, and second, we use this to derive the exact distribution of the number of iterations of hesitant adaptive search to termination. Received: November 17, 1997 / Accepted: July 9, 1999?Published online December 15, 2000  相似文献   

4.
Negative-cycle detection algorithms   总被引:2,自引:0,他引:2  
Received June 14, 1996 / Revised version received June 22, 1998 Published online January 20, 1999  相似文献   

5.
Feasible descent algorithms for mixed complementarity problems   总被引:6,自引:0,他引:6  
In this paper we consider a general algorithmic framework for solving nonlinear mixed complementarity problems. The main features of this framework are: (a) it is well-defined for an arbitrary mixed complementarity problem, (b) it generates only feasible iterates, (c) it has a strong global convergence theory, and (d) it is locally fast convergent under standard regularity assumptions. This framework is applied to the PATH solver in order to show viability of the approach. Numerical results for an appropriate modification of the PATH solver indicate that this framework leads to substantial computational improvements. Received April 9, 1998 / Revised version received November 23, 1998?Published online March 16, 1999  相似文献   

6.
Using a simple analytical example, we demonstrate that a class of interior point methods for general nonlinear programming, including some current methods, is not globally convergent. It is shown that those algorithms produce limit points that are neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed problem. Received: December 1999 / Accepted: May 2000?Published online August 18, 2000  相似文献   

7.
Received October 26, 1996 / Revised version received October 1, 1997 Published online October 9, 1998  相似文献   

8.
For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which the best known solution is improved.  相似文献   

9.
10.
This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000  相似文献   

11.
A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.  相似文献   

12.
We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ 2n satisfying y=f(x) and x i y i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ n to ℝ n . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ 3n which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ 2n in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999  相似文献   

13.
The hedging of contingent claims in the discrete time, discrete state case is analyzed from the perspective of modeling the hedging problem as a stochastic program. Application of conjugate duality leads to the arbitrage pricing theorems of financial mathematics, namely the equivalence of absence of arbitrage and the existence of a probability measure that makes the price process into a martingale. The model easily extends to the analysis of options pricing when modeling risk management concerns and the impact of spreads and margin requirements for writers of contingent claims. However, we find that arbitrage pricing in incomplete markets fails to model incentives to buy or sell options. An extension of the model to incorporate pre-existing liabilities and endowments reveals the reasons why buyers and sellers trade in options. The model also indicates the importance of financial equilibrium analysis for the understanding of options prices in incomplete markets. Received: June 5, 2000 / Accepted: July 12, 2001?Published online December 6, 2001  相似文献   

14.
We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.  相似文献   

15.
We prove an a priori estimate and a universal bound for any global solution of the nonlinear degenerate reaction-diffusion equation u t u m +u p in a bounded domain with zero Dirichlet boundary conditions. Received: October 1, 2001?Published online: July 9, 2002  相似文献   

16.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999  相似文献   

17.
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000  相似文献   

18.
Smooth methods of multipliers for complementarity problems   总被引:2,自引:0,他引:2  
This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems. Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999  相似文献   

19.
We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods. By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing parameter and establish the global linear convergence of this method. Some preliminary computational results are reported. Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000  相似文献   

20.
This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号