180 Park Ave - Building 103
Florham Park, NJ
Hybridizations of GRASP with path-relinking
Mauricio Resende
This will be chapter in the book "Hybrid Metaheuristics" edited by E.G. Talbi and to be publ,
2012.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in the book "Hybrid Metaheuristics" edited by E.G. Talbi. , 2012-06-30, http://rd.springer.com/chapter/10.1007%2F978-3-642-30671-6_5
{A greedy randomized adaptive search procedure (GRASP) is a metaheuristic
for combinatorial optimization. GRASP heuristics are multistart procedures
which apply local search to a set of starting solutions generated with
a randomized greedy algorithm or semi-greedy method. The best local
optimum found over the iterations is returned as the heuristic solution.
Path-relinking is a search intensification procedure that explores paths
in the neighborhood solution space connecting two good-quality solutions.
A local search procedure is applied to the best solution found in the path
and the local optimum found is returned as the solution of path-relinking.
The hybridization of path-relinking and GRASP adds memory mechanisms
to GRASP. This paper describes basic concepts of GRASP, path-relinking,
and the hybridization of GRASP with path-relinking.
}
Fast local search for the maximum independent set problem
Mauricio Resende, Google Diego V. Andrade, Renato F. Werneck
Journal of Heuristics,
2012.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Ambient Intelligence Perspectives . , 2012-02-25
{Given a graph G = (V,E), the independent set problem is that of finding
a maximum-cardinality subset S of V such that no two vertices in
S are adjacent. We introduce two fast local search routines for this
problem. The first can determine in linear time whether a maximal solution
can be improved by replacing a single vertex with two others. The second
routine can determine in O(m D)$ time (where D is the highest
degree in the graph) whether there are two solution vertices than can be
replaced by a set of three. We also present a more elaborate heuristic
that successfully applies local search to find near-optimum solutions
to a wide variety of instances. We test our algorithms on instances from
the literature as well as on new ones proposed in this paper.
}
A SURVEY OF MULTI-START METHODS FOR COMBINATORIAL OPTIMIZATION
Mauricio Resende, R. Martí, C. C. Ribeiro
European J. of Operational Research,
2012.
[PDF]
[BIB]
Elsevier Copyright
The definitive version was published in 2012. , Volume 226, Issue 1, 2012-12-31, http://www.sciencedirect.com/science/article/pii/S0377221712007394
{Multi-start methods strategically sample the solution space of
an optimization problem. The most successful of these methods
have two phases that are alternated for a certain number of global
iterations. The first phase generates a solution and the second seeks
to improve the outcome. Each global iteration produces a solution
that is typically a local optimum, and the best overall solution is
the output of the algorithm. The interaction between the two phases
creates a balance between search diversification (structural variation)
and search intensification (improvement), to yield an effective means for
generating high-quality solutions. This survey briefly sketches historical
developments that have motivated the field, and then focuses on modern
contributions that define the current state-of-the-art. We consider
two categories of multi-start methods: memory-based and memoryless
procedures. The former are based on identifying and recording specific
types of information (attributes) to exploit in future constructions. The
latter are based on order statistics of sampling and generate unconnected
solutions. An interplay between the features of these two categories
provides an inviting area for future exploration.
}
Parallel hybrid heuristics for the permutation flow shop problem
Mauricio Resende, Fed. U. of Minas Gerais Martin G. Ravetti, U. of Newcastle Carlos Riveros, U. of Newcastle Alexandre Mendes, Panos M. Pardalos
Annals of Operations Research,
2011.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Annals of Operations Research (Springer). , 2011-12-31, http://rd.springer.com/article/10.1007%2Fs10479-011-1056-3
{This paper addresses the Permutation Flowshop Problem with minimization of
makespan, which is denoted by F|prmu|Cmax. In the permutational
scenario, the sequence of jobs has to remain the same in all machines. The
Flowshop Problem (FSP) is known to be NP-hard when more than three
machines are considered. Thus, for medium and large scale instances,
high-quality heuristics are needed to find good solutions in reasonable
time. We propose and analyse parallel hybrid search methods that fully
use the computational power of current multi-core machines. The parallel
methods combine a memetic algorithm (MA) and several iterated greedy
algorithms (IG) running concurrently. Two test scenarios were included,
with short and long CPU times. The tests were conducted on the set of
benchmark instances introduced by Taillard in 1993, commonly used to
assess the performance of new methods. Results indicate that the use
of the MA to manage a pool of solutions is highly effective, allowing
the improvement of the best known upper bound for one of the instances.
~ }
GRASP with path-relinking for the generalized quadratic assignment problem
Mauricio Resende, Geraldo R. Mateus, Ricardo M. A. Silva
Journal of Heuristics,
2011.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Journal of Heuristics. , Volume 17, Issue 5, 2011-10-01
{The generalized quadratic assignment problem (GQAP) is a generalization
of the NP-hard quadratic assignment problem (QAP) that allows multiple
facilities to be assigned to a single location as long as the capacity
of the location allows. The GQAP has numerous applications, including
facility design, scheduling, and network design. In this paper, we
propose several GRASP with path-relinking heuristics for the GQAP using
different construction, local search, and path-relinking procedures.
We introduce a novel approximate local search scheme, as well as a new
variant of path-relinking that deals with infeasibilities. Extensive
experiments on a large set of test instances show that the best of the
proposed variants is both effective and efficient.
}
GRASP with path-relinking for data clustering: A case study for biological data
Mauricio Resende, Rafael M. D. Frinhani, Ricardo M. A. Silva, Geraldo R. Mateus, Paola Festa
Lecture Notes in Computer Science,
2011.
[PDF]
[BIB]
Springer-Verlag Copyright
The definitive version was published in Lecture Notes in Computer Science. , Volume 6630, 2011-05-05
{Cluster analysis has been applied to several domains with numerous
applications. In this paper, we propose several GRASP with path-relinking
heuristics for data clustering problems using as case study biological
datasets. All these variants are based on the construction and local
search procedures introduced by Nascimento et al. (2010). hybridized the
GRASP proposed by Nascimento et al. (2010) with four alternatives for
relinking method: forward, backward, mixed, and randomized. To our
knowledge, GRASP with path-relinking has never been applied to cluster
biological datasets. Extensive comparative experiments with other
algorithms on a large set of test instances, according to different
distance metrics (Euclidean, city block, cosine, and Pearson), show that
the best of the proposed variants is both effective and efficient.
}
Correspondence of projected 3D points and lines using a continuous GRASP
Mauricio Resende, Raytheon M. J. Hirsch, P. M. Pardalos
International Transactions in Operational Research,
2011.
[PDF]
[BIB]
Wiley Copyright
The definitive version was published in International Transactions in Operational Research. , Volume 18, Issue 4, 2011-07-01
{The field of computer vision has experienced rapid growth over the
past fifty years. Many computer vision problems have been solved
using theory and ideas from algebraic projective geometry. In this
research, we look at a previously unsolved problem from object
recognition, namely object recognition when the correspondences
between the object and image data is not known a priori. We
formulate this problem as a mixed-integer nonlinear optimization
problem in terms of the unknown projection relating the object and
image, as well as the unknown assignments of object points and lines
to those in the image. The global optimum of this problem recovers
the relationship between the object points and lines with those in
the image. When certain assumptions are enforced on the allowable
projections mapping the object into the image, a proof is provided
which permits one to solve the optimization problem via a simple
decomposition. We illustrate this decomposition approach on some
example scenarios.
}
An iterative refinement algorithm for the minimum branch vertices problem
Mauricio Resende, Diego M. Silva, Ricardo M. A. Silva, Geraldo R. Mateus, José Gonçalves, Paola Festa
Lecture Notes in Computer Science,
2011.
[PDF]
[BIB]
Springer-Verlag Copyright
The definitive version was published in Lecture Notes in Computer Science. , Volume 6630, 2011-05-05
{This paper presents a new approach to solve the NP-complete minimum
branch vertices problem (MBV) introduced by Gargano et al. (2002).
In spite of being a recently proposed problem in the network optimization
literature, there are some heuristics to solve it (Cerulli et al.,
2002). The main contribution of this paper consists in a new heuristic
based on the iter- ative refinement approach proposed by Deo and Kumar
(1997). The experimental results suggest that this approach is capable of
finding solutions that are better than the best known in the literature.
In this work, for instance, the proposed heuristic found better solutions
for 78% of the instances tested. The heuristic looks very promising for
the solution of problems related with constrained spanning trees.
}
A parallel multi-population biased random-key genetic algorithm for a container loading problem
Mauricio Resende, José F. Gonçalves
Computers and Operations Research ,
2011.
[PDF]
[BIB]
Elsevier Copyright
The definitive version was published in Computers and Operations Research (Elsevier). , Volume 29, 2011-12-01, :10.1016/j.cor.2011.03.009
{This paper presents a multi-population biased random-key genetic algorithm
(BRKGA) for the Single Container Loading Problem (CLP) where several
rectangular boxes of different sizes are loaded into a single rectangular
container. The approach uses a maximal-space representation to manage
the free spaces in the container. The proposed algorithm hybridizes a
novel placement procedure with a multi-population genetic algorithm based
on random keys. The BRKGA is used to evolve the order in which the box
types are loaded into the container and the corresponding type of layer
used in the placement procedure. A heuristic is used to determine the
maximal space where each box is placed. A novel procedure is developed
for joining free spaces in the case where full support from below is
required. The approach is extensively tested on the complete set of test
problem instances of Bischoff and Ratcliff (1995) and Davies and Bischoff
(1999) and is compared with other approaches. The test set consists of
weakly to strongly heterogeneous instances. The experimental results
validate the high quality of the solutions as well as the effectiveness
of the proposed heuristic.
}
A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering
Mauricio Resende, Fed. U. of R. Grande do Norte Luciana S. Pessoa, Fed. Fluminense U. Celso C. Ribeiro
Computers & Operations Research,
2011.
[BIB]
Elsevier Copyright
The definitive version was published in Computers & Operations Research (Elsevier). , 2011-12-31, http://www.sciencedirect.com/science/article/pii/S0305054811003431
{The set multicovering or set K-covering problem is an extension of the
classical set covering problem, in which each object is required to be
covered at least K times. The problem finds applications in the design
of communication networks and in computational biology. We describe a
GRASP with path-relinking heuristic for the set K-covering problem,
as well as the template of a family of Lagrangean heuristics. The
hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking
heuristic using modified costs to obtain solutions for the Lagrangean
relaxation problem. Computational experiments carried out on 135 test
instances show experimentally that the Lagrangean heuristics performed
consistently better than GRASP. By properly tuning the parameters
of the GRASP Lagrangean heuristic, it is possible to obtain a good
trade-off between solution quality and running times. Furthermore, the
GRASP Lagrangean heuristic makes better use of the dual information
provided by subgradient optimization and is able to discover better
solutions and to escape from locally optimal solutions even after the
stabilization of the lower bounds, when other strategies fail to find
new improving solutions.
}
A biased random-key genetic algorithm for the Steiner triple covering problem
Mauricio Resende, Rodrigo F. Toso, José F. Gonçalves, Ricardo M. A. Silva
Optimization Letters,
2011.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Optimization Letters , 2011-12-31, 10.1007/s11590-011-0285-3
{We present a biased random-key genetic algorithm (BRKGA) for finding small
covers of computationally difficult set covering problems that arise in
computing the 1-width of incidence matrices of Steiner triple systems.
Using a parallel implementation of the BRKGA, we compute improved covers
for the two largest instances in a standard set of test problems used
to evaluate solution procedures for this problem. The new covers for
instances A405 and A729 have sizes 335 and 617, respectively. On all
other smaller instances our algorithm consistently produces covers of
optimal size.
}
A Python/C library for bound-constrained global optimization with continuous GRASP
Mauricio Resende, Fed. U. of Pernambuco Ricardo Silva, Panos M. Pardalos, Michael Hirsch
Optimization Letters,
2011.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Springer. , 2011-12-31, http://rd.springer.com/article/10.1007%2Fs11590-012-0475-7
{This paper describes libcgrpp, a GNU-style dynamic shared Python/C library
of the continuous greedy randomized adaptive search procedure (C-GRASP)
for bound constrained global optimization. C-GRASP is an extension
of the GRASP metaheuristic (Feo and Resende, 1989). After a brief
introduction to C-GRASP, we show how to download, install, configure,
and use the library through an illustrative example.
}
SOLVING SCALARIZED MULTI-OBJECTIVE NETWORK FLOW PROBLEMS WITH AN INTERIOR POINT METHOD
Mauricio Resende, INESC-Coimbra Margarida Fonseca
International Transactions in Operational Research,
2010.
[BIB]
GRASP with path relinking heuristics for the antibandwidth problem
Mauricio Resende, Abraham Duarte, Ricardo M. A. Silva, Rafael Martí
Networks,
2010.
[PDF]
[BIB]
Wiley-Blackwwell Copyright
The definitive version was published in Networks
(Wiley-Blackwell). , 2010-12-22, and is available at http://onlinelibrary.wiley.com.
{This paper proposes a linear integer programming formulation and several
heuristics based on GRASP and path relinking for the antibandwidth
problem. In the antibandwidth problem, one is given an undirected graph
with N nodes and must label the nodes in a way that each node receives a
unique label from the set { 1, 2, ..., N }, such that, among all adjacent
node pairs, the minimum difference between the node labels is maximized.
Computational results show that only small instances of this problem can
be solved exactly (to optimality) with a commercial integer programming
solver and that the heuristics find high-quality solutions in much less
time than the commercial solver.
}
Biased random-key genetic algorithms for combinatorial optimization
Mauricio Resende, José Gonçalves
Journal of Heuristics,
2010.
[BIB]
{Random-key genetic algorithms were introduced by Bean (1994) for solving
sequencing problems in combinatorial optimization. Since then, they
have been extended to handle a wide class of combinatorial optimization
problems. This paper presents a tutorial on the implementation and
use of biased random-key genetic algorithms for solving combinatorial
optimization problems. Biased random-key genetic algorithms are a
variant of random-key genetic algorithms, where one of the parents
used for mating is biased to be of higher fitness than the other parent.
After introducing the basics of biased random-key genetic algorithms,
the paper discusses in some detail implementation issues, illustrating
the ease in which sequential and parallel heuristics based on biased
random-key genetic algorithms can be developed. A survey of applications
that have recently appeared in the literature is also given.
}
A biased random-key genetic algorithm for road congestion minimization
Mauricio Resende, Luciana S. Buriol, Raytheon Michael J. Hirsch, Panos M. Pardalos, Tania Querido, Marcus Ritt
Optimization Letters (Springer),
2010.
[PDF]
[BIB]
Springer Copyright
The definitive version was published in Optimization Letters . , 2010-12-15, http://dx.doi.org/10.1007/s11590-010-0226-6
{One of the main goals in transportation planning is to achieve solutions
for two classical problems, the traffic assignment and toll pricing
problems. The traffic assignment problem aims to minimize total travel
delay among all travelers. Based on data derived from the first problem,
the toll pricing problem determines the set of tolls and corresponding
tariffs that would collectively benefit all travelers and would lead to
a user equilibrium solution. Obtaining high-quality solutions for this
framework is a challenge for large networks. In this paper, we propose
an approach to solve the two problems jointly, making use of a biased
random-key genetic algorithm for the optimization of transportation
network performance by strategically allocating tolls on some of the
links of the road network. Since a transportation network may have
thousands of intersections and hundreds of road segments, our algorithm
takes advantage of mechanisms for speeding up shortest-path algorithms.
}
A Biased Random-Key Genetic Algorithm with Forward-Backward Improvement for the Resource Constrained Project Scheduling Problem
Mauricio Resende, José Gonçalves, Jorge Mendes
2010.
[PDF]
[BIB]
{This paper presents a biased random-keys genetic algorithm for the Resource Constrained Project Scheduling Problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm. }
Solving scalarized multi-objective network flow problems with an interior point method
Mauricio Resende, Margarida Fonseca, Jo?e Figueira
2009.
[PDF]
[BIB]
{In this paper we present a primal-dual interior-point algorithm to solve a class of multi-objective network flow problems. More precisely, our algorithm is an extension of the single-objective primal infeasible dual feasible inexact interior point method for multi-objective linear network flow problems. Our algorithm is contrasted with standard interior point methods and experimental results on bi-objective instances are reported. The multi-objective instances are converted into single objective problems with the aid of an achievement function, which is particularly adequate for interactive decision-making methods. }
GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem
Mauricio Resende, Mariá Nascimento, Franklina Toledo
2008.
[PDF]
[BIB]
{-----Original Message----- From: RESENDE, MAURICIO G (ATTLABS) Sent: Wednesday, June 11, 2008 3:20 PM To: ALCORN, LAURINDA J (LAURINDA J) Cc: RESENDE, MAURICIO G (ATTLABS) Subject: title change in TD-7B46YC }
GRASP and path relinking for the max-min diversity problem
Mauricio Resende, Rafael Martí, Micael Gallego, Abraham Duarte
2008.
[PDF]
[BIB]
{The Max-Min Diversity Problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method - based on the GRASP and path relinking methodologies - for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary path relinking. Empirical results indicate that the proposed hybrid implementations compare favorably to previous metaheuristics, such as tabu search and simulated annealing. }
A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem
Mauricio Resende, José Gonçalves
2008.
[PDF]
[BIB]
{This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be paced into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm. }
A random key based genetic algorithm for the resource constrained project scheduling problem
Mauricio Resende, Jorge Mendes, José Gonçalves
2006.
[PDF]
[BIB]
{Debra Gardner, Secretary This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm. ~ }
A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem
Mauricio Resende, José Gonçalves
2006.
[PDF]
[BIB]
{This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm. }
Power Transmission Network Design by Greedy Randomized Adaptive Path Relinking
Mauricio Resende, Haroldo Faria Jr., Silvio Binato, Djalma M. Falcão
2004.
[PDF]
[BIB]
{This paper illusrates results obtained by a new metaheuristic approach, Greedy Randomized Adaptive Path Relinking, applied to solve static power transmission network design problems. This new approach consists of a generalization of GRASP concepts to explore different trajectories between two "high-quality" solutions. The results were obtained from two real-world cases studies from Brazilian systems. This paper illusrates results obtained by a new metaheuristic approach, Greedy Randomized Adaptive Path Relinking, applied to solve static power transmission network design problems. This new approach consists of a generalization of GRASP concepts to explore different trajectories between two "high-quality" solutions. The results were obtained from two real-world cases studies from Brazilian systems. }
Fortran subroutines for network flow optimization using an interior point algorithm
Mauricio Resende, João Patrício, Luis Portugal, Geraldo Veiga, Joaquim Judice
2004.
[PDF]
[BIB]
{We describe FORTRAN subroutines for network flow optimization using an interior point network flow algorithm. We provide FORTRAN and C language drivers, as well as C language functions that, together with the subroutines, make up PDNET (Portugal, Resende, Veiga, and Júdice, 2000). The algorithm is described in detail and its implementation is outlined. Usage of the package is described and some computational experiments are reported. Source code for the software can be downloaded at http://www.research.att.com/~mgcr/pdnet. Springer: Mathematical Programming }
A genetic algorithm for the resource constrained multi-project scheduling problem
Mauricio Resende, José Gonçalves, Jorge Mendes
2004.
[PDF]
[BIB]
{This paper presents a genetic algorithm for the Resource Constrained Multi-Project Scheduling Problem (RCMPSP). The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm. }
Hybrid genetic algorithm for the job shop scheduling problem
Mauricio Resende, José Gonçalves, José Gonçalves, Jorge José Mendes
European Journal of Operational Research,
2002.
[BIB]
{This paper presents a hybrid genetic algorithm for the Job Shop Scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm. }
Hybrid genetic algorithm for manufacturing cell formation
Mauricio Resende, José Gonçalves
2002.
[PDF]
[BIB]
{Cellular manufacturing emerged as a production strategy capable of solving the problems of complexity and long manufacturing lead times in batch production. The fundamental problem in cellular manufacturing is the formation of product families and machine cells. This paper presents a new approach for obtaining machine cells and product families. The approach combines a local search heuristic with a genetic algorithm. Computational experience with the algorithm on a set of group technology problems available in the literature is also presented. The approach produced solutions with a grouping efficacy that is at least as good as any results previously reported in literature and improved the grouping efficacy for 59 % of the problems. }
Maximizing Diversity In A Subset Of Elements Utilizing Grasp With Path Relinking,
Tue May 22 16:10:29 EDT 2012
Methods, systems, and computer-readable media for maximizing diversity in a subset of elements selected from a set of elements are provided. An algorithm that combines the GRASP and path relinking heuristics is utilized to find an approximate solution to a max-min diversity problem modeled from the set of elements. The GRASP heuristic is applied to the set of elements for a number of iterations to generate a set of feasible solutions, and a best solution is determined from the set. The path relinking heuristic is then applied between a pair of solutions in the set of feasible solutions to generate a candidate solution. If the candidate solution is better than the best solution, then the best solution is replaced with the candidate solution, and the process is repeated until the path relinking heuristic has been applied between each pair of solutions in the set of feasible solutions.
Method And System For Network Migration Scheduling,
Tue Mar 20 16:09:35 EDT 2012
A method of transforming an ordered list of nodes of a network into one of a plurality of elite ordered lists, the ordered list corresponding to a deloading sequence, the deloading sequence including a temporary capacity requirement, each of the elite ordered lists corresponding to an elite deloading sequence including an elite temporary capacity requirement by generating at least one intermediate ordered list corresponding to an intermediate deloading sequence including an intermediate temporary capacity requirement, selecting one of the intermediate ordered list and the ordered list based on a comparison of the intermediate temporary capacity requirement and the temporary capacity requirement and replacing one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if a value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a lowest value of the elite temporary capacity requirements.
Method And Apparatus For Providing Composite Link Assignment In Network Design,
Tue Jan 17 16:09:03 EST 2012
A method and apparatus for composite link assignment are provided such that network capacity is sufficient to handle all the traffic (e.g., load) while an objective function, e.g., the total cost of the capacity is minimized. The present method receives a plurality of weights for a plurality of arcs and a load for the network. An objective function is selected for minimization, where the present method then determines the composite link assignment to handle the load while the objective function is minimized. In one embodiment, the composite link assignment comprises a plurality of different link types for the plurality of arcs.
Method For Network Design To Maximize Difference Of Revenue And Network Cost,
Tue Jul 12 16:05:41 EDT 2011
A method determines an optimal or near-optimal conveyance network layout in which revenue from serviced customer locations is maximized while the cost of installing and/or maintaining the conveyance is minimized. The conveyance may, for example, be a fiber optic telecommunications cable or a power or utility distribution system. Algorithms in the method generate primal and dual bounds in a Prize-Collecting Steiner Tree Problem in Graphs (PCSPG). Those algorithms originate from a Lagrangian Non-Delayed Relax-and-Cut (NDRC) based approach and incorporate ingredients such as a new PCSPG reduction test, an effective Local Search procedure and a modification in the NDRC framework that allows additional reductions in duality gaps to be attained.
Sensor Registration By Global Optimization Procedures,
Tue Jul 05 16:05:40 EDT 2011
Disclosed are method and apparatus for registering multiple sensors collecting data from multiple objects. Sensor registration is decomposed into a two-step procedure. The first step corrects systematic errors. The second step assigns objects measured by one sensor to objects measured by a second sensor. Systematic errors are corrected by generating the global minimum of a systematic error function. One embodiment for generating the global minimum uses a Continuous Greedy Randomized Adaptive Search Procedure.
Determining A Minimum Cost Solution For Resolving Covering-By-Pairs Problem,
Tue Apr 12 16:04:50 EDT 2011
In one method for determining a minimum cost solution for resolving a covering-by-pairs problem, a plurality of covering nodes, a plurality of branch nodes, and a plurality of edges connecting the covering nodes and the branch nodes are given. A plurality of vectors are generated. For each vector in the plurality of vectors, it is determined whether the selected covering nodes cover the branch nodes. Responsive to determining that the selected covering nodes do not cover the branch nodes, each vector is completed so that the selected covering nodes cover the branch nodes. Responsive to determining that selected covering nodes cover the branch nodes or to completing the vector, redundant covering nodes are removed from each vector. The vectors are inserted into a current population. A new population is generated by evolving the current population for at least one generation.
Traffic Engineering Method With Tunable Inter-Domain Egress Selection,
Tue Mar 08 16:04:39 EST 2011
A flexible mechanism for routers to select the egress point for each destination prefix, herein referred to as tunable inter-domain egress (TIE) selection, comprises the step of ranking possible points of egress according to a metric, allowing network administrators to satisfy diverse goals, such as traffic engineering and robustness to equipment failures. A weighting function is discussed whereby known hot potato routing can be weighted against a fixed ranking scheme. TIE has been applied to data of two different autonomous systems posing different problems solved using integer-programming and multi-commodity flow techniques, respectively, to tune the TIE according to the weighting function to satisfy network-wide objectives. Experiments with traffic, topology and routing data from two different backbone networks demonstrate that TIE is both simple (for the routers) and expressive (for the network administrators) and can be practically applied in traffic engineering.
Devices, Systems, And Methods For Migration Scheduling,
Tue Nov 02 15:04:56 EDT 2010
Certain exemplary embodiments can comprise a method that can comprise automatically modifying a schedule of a transfer of a plurality of groups of units from a first system to a second system. The method can comprise performing one or more recursive neighborhood searches on the schedule. The schedule can be determined initially via iterative determinations of a next unit to be transferred as a unit with a relatively low determined value of an objective function.
Sensor Registration By Global Optimization Procedures,
Tue Jan 26 15:03:18 EST 2010
Disclosed are method and apparatus for registering multiple sensors collecting data from multiple objects. Sensor registration is decomposed into a two-step procedure. The first step corrects systematic errors. The second step assigns objects measured by one sensor to objects measured by a second sensor. Systematic errors are corrected by generating the global minimum of a systematic error function. One embodiment for generating the global minimum uses a Continuous Greedy Randomized Adaptive Search Procedure.
Method And Apparatus For Updating A Shortest Path Graph,
Tue Sep 22 16:08:04 EDT 2009
A method and apparatus for updating a shortest path graph or a shortest path tree are disclosed. For example, an arc weight is changed for an arc in the network, where a plurality of affected nodes in the network is determined. The distance of each of the affected nodes is determined, where a subset of the plurality of affected nodes is then placed in a heap. One aspect of the present invention is that not all the affected nodes are placed in the heap. In one embodiment, the present reduced heap approach only applies the Dijkstra's algorithm to those affected nodes whose distances change in a smaller amount that the change in the arc weight. In turn, the shortest path graph or the shortest path tree is updated in accordance with the affected nodes placed in the heap.
Method For Tunable Inter-Domain Egress Selection,
Tue Aug 25 16:07:50 EDT 2009
A flexible mechanism and method for routers to select the egress point for each destination comprises identifying a plurality of points of egress from an autonomous system, ranking the plurality of points of egress according to a metric having variable and fixed terms, selecting a point of egress having the smallest rank, and transmitting packets from a point of ingress via a path to the selected point of egress. The metric is across a plurality of destinations and respective possible points of egress from the autonomous system and the metric is m(i, p, e) equaling .alpha.(i, p, e)d(G,i,e)+.beta.(i, p, e) where a and .beta. are configurable values, i is the identity of the router, p is the destination, G is an undirected weighted graph, the d function is the interior gateway protocol distance and e is a point of egress.
