共查询到20条相似文献,搜索用时 31 毫秒
1.
Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem
The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances. 相似文献
2.
This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been developed to solve it. We suggest very efficient, yet simple, heuristic algorithms for the RWA problem developed by applying classical bin packing algorithms. The heuristics were tested on a series of large random networks and compared with an efficient existing algorithm for the same problem. Results indicate that the proposed algorithms yield solutions significantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths. Comparison with lower bounds shows that the proposed heuristics obtain optimal or near optimal solutions in many cases. 相似文献
3.
We consider here a NP-hard problem related to the Routing and Wavelength Assignment (RWA) problem in optical networks, dealing with Scheduled Lightpath Demands (SLDs). An SLD is a connection demand between two nodes of the network, during a certain time. Given a set of SLDs, we want to assign a lightpath, i.e. a routing path and a wavelength, to each SLD, so that the total number of required wavelengths is minimized. The constraints are the following: a same wavelength must be assigned all along the edges of the routing path of any SLD; at any time, a given wavelength on a given edge of the network cannot be used to satisfy more than one SLD. To solve this problem, we design a post-optimization method improving the solutions provided by a heuristic. The experimental results show that this post-optimization method is quite efficient to reduce the number of necessary wavelengths. 相似文献
4.
Recent advances in the solution of quadratic assignment problems 总被引:6,自引:0,他引:6
Kurt M. Anstreicher 《Mathematical Programming》2003,97(1-2):27-42
The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number
of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality
for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe
these developments, as well as recent work which is likely to result in the solution of even more difficult instances.
Received: February 13, 2003 / Accepted: April 22, 2003
Published online: May 28, 2003
Key Words. quadratic assignment problem – discrete optimization – branch and bound
Mathematics Subject Classification (1991): 90C27, 90C09, 90C20 相似文献
5.
Thiago F. Noronha Mauricio G. C. Resende Celso C. Ribeiro 《Journal of Global Optimization》2011,50(3):503-518
The problem of routing and wavelength assignment in wavelength division multiplexing optical networks consists in routing
a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are
assigned different wavelengths. This problem was shown to be NP-hard when the objective is to minimize the total number of
wavelengths used. We propose a genetic algorithm with random keys for routing and wavelength assignment with the goal of minimizing
the number of different wavelengths used in the assignment. This algorithm extends the best heuristic in the literature by
embedding it into an evolutionary framework. Computational results show that the new heuristic improves the state-of-the-art
algorithms in the literature. 相似文献
6.
0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving
particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances
of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two
methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the
scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods
on the set partitioning problem. 相似文献
7.
《European Journal of Operational Research》2006,171(3):797-810
The problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition colouring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition colouring problem, which may be viewed as an extension of the graph colouring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition colouring by approximately 20% in the average and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem. 相似文献
8.
We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry
in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment
problems from the problem library: (Burkard et al. in J Global Optim 10:291–403, 1997). 相似文献
9.
John A. Ford Yasushi Narushima Hiroshi Yabe 《Computational Optimization and Applications》2008,40(2):191-216
Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of
matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput.
Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step
secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent
under certain assumptions. Numerical results are reported. 相似文献
10.
The modulational stability of travelling waves in 2D anisotropic systems is investigated. We consider normal travelling waves,
which are described by solutions of a globally coupled Ginzburg–Landau system for two envelopes of left- and right-travelling
waves, and oblique travelling waves, which are described by solutions of a globally coupled Ginzburg–Landau system for four
envelopes associated with two counterpropagating pairs of travelling waves in two oblique directions. The Eckhaus stability
boundary for these waves in the plane of wave numbers is computed from the linearized Ginzburg–Landau systems. We identify
longitudinal long and finite wavelength instabilities as well as transverse long wavelength instabilities. The results of
the stability calculations are confirmed through numerical simulations. In these simulations we observe a rich variety of
behaviors, including defect chaos, elongated localized structures superimposed to travelling waves, and moving grain boundaries
separating travelling waves in different oblique directions. The stability classification is applied to a reaction–diffusion
system and to the weak electrolyte model for electroconvection in nematic liquid crystals.
相似文献
11.
Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance
ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating
the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We
prove that the Max-Regret heuristic introduced by Balas and Saltzman (Oper. Res. 39:150–161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s≥3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic
(for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination
numbers for the s-dimensional (s≥3) assignment problem. 相似文献
12.
Adam Ouorou 《Computational Management Science》2006,3(4):285-305
In telecommunications, the demand is a key data that drives network planning. The demand exhibits considerable variability, due to customers movement and introduction of new services and products in the present competitive markets. To deal with this uncertainty, we consider capacity assignment problem in telecommunications in the framework of robust optimization proposed in Ben-Tal and Nemcrovski (Math Oper Res 23(4):769–805, 1998, MPS-SIAM
series on optimization, 2001) and Kouvelis and Yu. We propose a decomposition scheme based on cutting plane methods. Some preliminary computational experiments indicate that the Elzinga–Moore cutting plane method (Elzinga and Moore in Math Program 8:134–145, 1975) can be a valuable choice. Since in some situations different possible uncertainty sets may exist, we propose a generalization of these models to cope at a time with a finite number of plausible uncertainty sets. A weight is associated with each uncertainty set to determine its relative importance or worth against another. 相似文献
13.
14.
Alicia Cordero José L. Hueso Eulalia Martínez Juan R. Torregrosa 《Numerical Algorithms》2010,53(4):485-495
In this paper, we present two new three-step iterative methods for solving nonlinear equations with sixth convergence order.
The new methods are obtained by composing known methods of third order of convergence with Newton’s method and using an adequate
approximation for the derivative, that provides high order of convergence and reduces the required number of functional evaluations
per step. The first method is obtained from Potra-Pták’s method and the second one, from Homeier’s method, both reaching an
efficiency index of 1.5651. Our methods are comparable with the method of Parhi and Gupta (Appl Math Comput 203:50–55, 2008). Methods proposed by Kou and Li (Appl Math Comput 189:1816–1821, 2007), Wang et al. (Appl Math Comput 204:14–19, 2008) and Chun (Appl Math Comput 190:1432–1437, 2007) reach the same efficiency index, although they start from a fourth order method while we use third order methods and simpler
arithmetics. We prove the convergence results and check them with several numerical tests that allow us to compare the convergence
order, the computational cost and the efficiency order of our methods with those of the original methods. 相似文献
15.
Silvano Martello 《Central European Journal of Operations Research》2010,18(1):47-58
We discuss some relevant results obtained by Egerváry in the early Thirties, whose importance has been recognized several
years later. We start with a quite well-known historical fact: the first modern polynomial-time algorithm for the assignment
problem, invented by Harold W. Kuhn half a century ago, was christened the “Hungarian method” to highlight that it derives
from two older results, by Kőnig (Math Ann 77:453–465, 1916) and Egerváry (Mat Fiz Lapok 38:16–28, 1931) (A recently discovered
posthumous paper by Jacobi (1804–1851) contains however a solution method that appears to be equivalent to the Hungarian algorithm).
Our second topic concerns a combinatorial optimization problem, independently defined in satellite communication and in scheduling
theory, for which the same polynomial-time algorithm was independently published 30 years ago by various authors. It can be
shown that such algorithm directly implements another result contained in the same 1931 paper by Egerváry. We finally observe
that the latter result also implies the famous Birkhoff-von Neumann theorem on doubly stochastic matrices. 相似文献
16.
Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function 总被引:3,自引:0,他引:3
We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained
optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity
independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class
of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease
condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease
conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior
comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic
local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach.
Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002
Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints
– local convergence – large-scale optimization
Mathematics Subject Classification (2000): 65K05, 90C30 相似文献
17.
Andreas Rößler 《BIT Numerical Mathematics》2007,47(3):657-680
The weak approximation of the solution of a system of Stratonovich stochastic differential equations with a m–dimensional Wiener process is studied. Therefore, a new class of stochastic Runge–Kutta methods is introduced. As the main
novelty, the number of stages does not depend on the dimension m of the driving Wiener process which reduces the computational effort significantly. The colored rooted tree analysis due
to the author is applied to determine order conditions for the new stochastic Runge–Kutta methods assuring convergence with
order two in the weak sense. Further, some coefficients for second order stochastic Runge–Kutta schemes are calculated explicitly.
AMS subject classification (2000) 65C30, 65L06, 60H35, 60H10 相似文献
18.
Renato. D. C. Monteiro 《Mathematical Programming》2003,97(1-2):209-244
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first
concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming,
putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed
for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following
IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion
of matrix completion to exploit data sparsity.
Received: December 16, 2002 / Accepted: May 5, 2003
Published online: May 28, 2003
Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods
– nonlinear programming – Newton method – first-order methods – bundle method – matrix completion
The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084,
CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401.
Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51 相似文献
19.
李寿佛 《中国科学A辑(英文版)》2002,45(10):1276-1290
A class of efficient parallel multivalue hybrid methods for stiff differential equations are presented, which are all extremely
stable at infinity,A-stable for orders 1–3 and A(α)-stable for orders 4–8. Each method of the class can be performed parallelly using two processors
with each processor having almost the same computational amount per integration step as a backward differentiation formula
(BDF) of the same order with the same stepsize performed in serial, whereas the former has not only much better stability
properties but also a computational accuracy higher than the corresponding BDF. Theoretical analysis and numerical experiments
show that the methods constructed in this paper are superior in many respects not only to BDFs but also to some other commonly
used methods. 相似文献
20.
This paper systematically studies numerical solution of fourth order problems in any dimensions by use of the Morley–Wang–Xu
(MWX) element discretization combined with two-grid methods (Xu and Zhou (Math Comp 69:881–909, 1999)). Since the coarse and fine finite element spaces are nonnested, two intergrid transfer operators are first constructed
in any dimensions technically, based on which two classes of local and parallel algorithms are then devised for solving such
problems. Following some ideas in (Xu and Zhou (Math Comp 69:881–909, 1999)), the intrinsic derivation of error analysis for nonconforming finite element methods of fourth order problems (Huang et al.
(Appl Numer Math 37:519–533, 2001); Huang et al. (Sci China Ser A 49:109–120, 2006)), and the error estimates for the intergrid transfer operators, we prove that the discrete energy errors of the two classes
of methods are of the sizes O(h + H
2) and O(h + H
2(H/h)(d−1)/2), respectively. Here, H and h denote respectively the mesh sizes of the coarse and fine finite element triangulations, and d indicates the space dimension of the solution region. Numerical results are performed to support the theory obtained and
to compare the numerical performance of several local and parallel algorithms using different intergrid transfer operators. 相似文献