Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: J Glob Optim

Search In Journal Title:

Abbravation: Journal of Global Optimization

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1007/bf01128985

Search In DOI:

ISSN

1573-2916

Search In ISSN:
Search In Title Of Papers:

A biased randomkey genetic algorithm to maximize

Authors: Julliany S Brandão Thiago F Noronha Celso C Ribeiro
Publish Date: 2015/12/19
Volume: 65, Issue: 4, Pages: 813-835
PDF Link

Abstract

Given a set of lightpath requests the problem of routing and wavelength RWA assignment in wavelength division multiplexing WDM optical networks consists in routing a subset of these requests and assigning a wavelength to each of them such that two lightpaths that share a common link are assigned to different wavelengths There are many variants of this problem in the literature We focus in the variant in which the objective is to maximize the number of requests that may be accepted given a limited set of available wavelengths This problem is called maxRWA and it is of practical and theoretical interest because algorithms for this variant can be extended for other RWA problems that arise from the design of WDM optical networks A number of exact algorithms based on integer programming formulations have been proposed in the literature to solve maxRWA as well as algorithms to provide upper bounds to the optimal solution value However the algorithms based on the stateoftheart formulations in the literature cannot solve the largest instances to optimality For these instances only upper bounds to the value of the optimal solutions are known The literature on heuristics for maxRWA is short and focus mainly on solving small size instances with up to 27 nodes In this paper we propose new greedy constructive heuristics and a biased randomkey genetic algorithm based on the best of the proposed greedy heuristics Computational experiments showed that the new heuristic outperforms the best ones in literature Furthermore for the largest instances in the literature where only upper bounds to the value of the optimal solutions are known the average optimality gap of the best of the proposed heuristics is smaller than 4 This work was partially supported by the Brazilian National Council for Scientific and Technological Development CNPq the Foundation for Support of Research of the State of Minas Gerais FAPEMIG the Foundation for Support of Research of the State of Rio de Janeiro FAPERJ and the Coordination for the Improvement of Higher Education Personnel Brazil CAPES

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. On Slater’s condition and finite convergence of the Douglas–Rachford algorithm for solving convex feasibility problems in Euclidean spaces
  2. Iterative algorithms for variational inequality and equilibrium problems with applications
  3. Efficient Nash equilibria on semilattices
  4. Global optimal solutions to a class of quadrinomial minimization problems with one quadratic constraint
  5. Global search perspectives for multiobjective optimization
  6. Necessary optimality conditions for a set-valued fractional extremal programming problem under inclusion constraints
  7. Rigorous filtering using linear relaxations
  8. On the image space analysis for vector quasi-equilibrium problems with a variable ordering relation
  9. Low dimensional simplex evolution: a new heuristic for global optimization
  10. Variational inclusions problems with applications to Ekeland’s variational principle, fixed point and optimization problems
  11. A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraints
  12. Existence and iterative algorithm of solutions for a class of bilevel generalized mixed equilibrium problems in Banach spaces
  13. Vector equilibrium problems with elastic demands and capacity constraints
  14. Stability Index Method for Global Minimization
  15. Dynamic sample budget allocation in model-based optimization
  16. On an elliptic Kirchhoff-type problem depending on two parameters
  17. Some constraint qualifications for quasiconvex vector-valued systems
  18. Optimization methodology assessment for the inlet velocity profile of a hydraulic turbine draft tube: part II—performance evaluation of draft tube model
  19. Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation
  20. A Lagrangian search method for the P -median problem
  21. Minimum vertex cover in ball graphs through local search
  22. Approximating zeros of monotone operators by proximal point algorithms
Search Result: