Many well-known combinatorialoptimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to...
详细信息
Many well-known combinatorialoptimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency assignment problem. A study of the polytope associated withthe formulation is presented, including proofs of which constraints of the formulation are facet-defining and the introduction of new classes of valid inequalities.
In the last two decades forest planning and management has become very much focused on spatially oriented decisions, due to the introduction of spatial details, such as road building, and environmental concerns, like ...
详细信息
In the last two decades forest planning and management has become very much focused on spatially oriented decisions, due to the introduction of spatial details, such as road building, and environmental concerns, like wildlife protection, biodiversity, reducing erosion and improving water quality. this has led to modeling transformations and extensions in planning forest activities, as mixed integer decision variables are necessary to account for spatial restrictions. these new models are much harder to solve due to the added combinatorial complexity. In this paper, we discuss issues of modeling spatial criteria, as well as algorithms that have been developed to solve them, both heuristic and exact. We present these results as they have evolved in a state-of-the-art structure. (c) 2005 Elsevier B.V. All rights reserved.
Many oil wells in Brazilian onshore fields rely on artificial lift methods. Maintenance services such as cleaning, reinstatement, stimulation and others are essential to these wells. these services are performed by wo...
详细信息
Many oil wells in Brazilian onshore fields rely on artificial lift methods. Maintenance services such as cleaning, reinstatement, stimulation and others are essential to these wells. these services are performed by workover rigs, which are available on a limited number with respect to the number of wells demanding service. the decision of which workover rig should be sent to perform some maintenance service is based on factors such as the well production, the current location of the workover rig in relation to the demanding well, and the type of service to be performed. the problem of scheduling workover rigs consists in finding the best schedule for the available workover rigs, so as to minimize the production loss associated withthe wells awaiting for service. We propose a variable neighborhood search (VNS) heuristic for this problem. Computational results on real-life problems are reported and their economic impacts are evaluated. (c) 2005 Elsevier B.V. All rights reserved.
the traveling salesman problem (TSP), and the quadratic assignment problem (QAP) are two combinatorialoptimization problems with a diverse set of applications. this research paper aims to apply the adaptation of disc...
详细信息
ISBN:
(纸本)9781479970544
the traveling salesman problem (TSP), and the quadratic assignment problem (QAP) are two combinatorialoptimization problems with a diverse set of applications. this research paper aims to apply the adaptation of discrete cat swarm optimization algorithm inspired by the natural behavior of cats to solve TSP and QAP. Simulated experiments were conducted on several benchmark instances taken from the OR-library. the results show the effectiveness of the proposed adaptation to solve real applications area based on the two-studied problems.
the optimal sizing problem of a small isolated power system that contains renewable and/or conventional energy technologies belongs to the field of combinatorialoptimization. Due to the large number of available tech...
详细信息
the optimal sizing problem of a small isolated power system that contains renewable and/or conventional energy technologies belongs to the field of combinatorialoptimization. Due to the large number of available technologies and their wide range of possible technical characteristics, the solution of this problem following the traditional method of exhaustive enumeration can be extremely time-consuming. In this paper, a tabu search algorithm is proposed for the solution of the above optimal sizing problem. Tabu search is an iterative metaheuristic method that has been successfully applied mainly in combinatorialoptimization problems. the results prove the performance of the proposed method in terms of solution quality and computation time.
the proceedings contain 33 papers. the topics discussed include: extraction of the interferometric phase by Hilbert Huang transform method from a single uncarrier image;discrete novel hybrid particle swarm optimizatio...
ISBN:
(纸本)9781479970544
the proceedings contain 33 papers. the topics discussed include: extraction of the interferometric phase by Hilbert Huang transform method from a single uncarrier image;discrete novel hybrid particle swarm optimization to solve travelling salesman problem;discrete cat swarm optimization algorithm applied to combinatorialoptimization problems;on the performance of energy detection spectrum sensing for interweave cognitive radio;a comparative approach of different or-BAC extensions: application and limits;hybrid automatic repeat request protocols: turbo-codes versus cyclic low-density parity-check codes;joint mission and communication aware node placement problem in mission-specific mobile sensor networks;SMPMA: semantic multimodal profile for multimedia documents adaptation;correction of the Arabic derived words using surface patterns;a new performances analysis for MRC receiver over correlated Weibull multipath fading channels;and study and comparison of smart city dedicated platforms: case of the Kalimucho platform.
Cooperative search is a parallelization strategy for search algorithms where parallelism is obtained by concurrently executing several search programs. the solution space is implicitly decomposed according to the sear...
详细信息
ISBN:
(纸本)3540664432
Cooperative search is a parallelization strategy for search algorithms where parallelism is obtained by concurrently executing several search programs. the solution space is implicitly decomposed according to the search strategy of each program. the programs cooperate by exchanging information on previously explored regions of the solution space. In this paper we propose a new design for cooperative search algorithms which is also a new parallel problem solving paradigm for combinatorialoptimization problems. Our new design is based on an innovative approach to decompose the solution space which is inspired from the modeling of cooperative algorithms based on dynamical systems theory. Our design also gives a new purpose to the sharing of information among cooperating tasks based on principles borrowed from scatter search evolutionary algorithms. We have appliedthis paradigm to the graph partitioning problem. We describe the parallel implementation of this algorithm on a cluster of workstations and compare our results with other well known graph partitioning methods.
the Vehicle Routing Problem with Time Windows is a complex combinatorialoptimization problem which can be seen as a fusion of two well known sub-problems: the Travelling Salesman Problem and the Bin Packing Problem. ...
详细信息
ISBN:
(纸本)9783642010194
the Vehicle Routing Problem with Time Windows is a complex combinatorialoptimization problem which can be seen as a fusion of two well known sub-problems: the Travelling Salesman Problem and the Bin Packing Problem. Its main objective is to find the lowest-cost set of routes to deliver demand, using identical vehicles with limited capacity, to Customers with fixed service time windows. In this paper, we consider the minimization of the number of routes and the total cost simultaneously. Although previous evolutionary studies have considered this problem, none of them has focused on the similarity of solutions in the population. We propose a method to measure route similarity and incorporate it into an evolutionary algorithm to solve the bi-objective VRPTW. We have appliedthis algorithm to a publicly available set of benchmark instances, resulting in solutions that are competitive or better than others previously published.
暂无评论