Search results for "Optimization problem"
showing 10 items of 281 documents
Advanced Scatter Search for the Max-Cut Problem
2009
The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity prob…
Multi-Start Methods
2006
Heuristic search procedures that aspire to find global optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory and degree of rebuild. We also present a computational comparison of these methods on solving the linear ordering problem in terms of solution quality and diversification power.
Advanced Multi-start Methods
2010
Heuristic search procedures that aspire to find globally optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory, and degree of rebuild. We also present a computational comparison of these methods on solving the maximum diversity problem in terms of solution quality and diversification power.
Fixed domain approaches in shape optimization problems
2012
This work is a review of results in the approximation of optimal design problems, defined in variable/unknown domains, based on associated optimization problems defined in a fixed ?hold-all? domain, including the family of all admissible open sets. The literature in this respect is very rich and we concentrate on three main approaches: penalization?regularization, finite element discretization on a fixed grid, controllability and control properties of elliptic systems. Comparison with other fixed domain approaches or, in general, with other methods in shape optimization is performed as well and several numerical examples are included.
On multi-objective optimal reconfiguration of MV networks in presence of different grounding
2015
The present work faces the traditional multi-objective optimal reconfiguration problem of a distribution grid including the safety issue in the objective functions. Actually, in many medium voltage networks still transformers with ungrounded neutral and with resonant grounded neutral coexist in the same area. This may be sometimes cause of problems during a single-line-to-ground fault if the ground electrodes of one or more cabins, initially designed for satisfying the safety conditions in a resonant grounded neutral network, after the reconfiguration are in a grounded neutral one or vice versa. In the paper a safety objective function is defined and the Non dominated Sorting Genetic Algori…
GRASP and path relinking for the max–min diversity problem
2010
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 p…
A comparison of different solution approaches to the vehicle scheduling problem in a practical case
2000
Abstract The Vehicle Scheduling Problem (VSP) consists in assigning a set of scheduled trips to a set of vehicles, satisfying a set of constraints and optimizing an objective function. A wide literature exists for the VSP, but usually not all the practical requirements of the real cases are taken into account. In the present paper a practical case is studied, and for it a traditional method is tailored and two innovative heuristics are developed. As the problem presents a multicriteria nature, each of the three algorithms adopts a different approach to multicriteria optimization. Scalarization of the different criteria is performed by the traditional algorithm. A lexicographic approach is f…
Hybridizing the cross-entropy method: An application to the max-cut problem
2009
Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.
A non dominated ranking Multi Objective Genetic Algorithm and electre method for unequal area facility layout problems
2013
The unequal area facility layout problem (UA-FLP) comprises a class of extremely difficult and widely applicable optimization problems arising in diverse areas and meeting the requirements for real-world applications. Genetic Algorithms (GAs) have recently proven their effectiveness in finding (sub) optimal solutions to many NP-hard problems such as UA-FLP. A main issue in such approach is related to the genetic encoding and to the evolutionary mechanism implemented, which must allow the efficient exploration of a wide solution space, preserving the feasibility of the solutions and ensuring the convergence towards the optimum. In addition, in realistic situations where several design issues…
Energy-Efficient Resource Optimization with Wireless Power Transfer for Secure NOMA Systems
2018
In this paper, we investigate resource allocation algorithm design for secure non-orthogonal multiple access (NOMA) systems empowered by wireless power transfer. With the consideration of an existing eavesdropper, the objective is to obtain secure and energy efficient transmission among multiple users by optimizing time, power and subchannel allocation. Moreover, we also take into consideration for the practical case that the statistics of the channel state information of the eavesdropper is not available. In order to address the optimization problem and its high computational complexity, we propose an iterative algorithm with guaranteed convergence to deliver a suboptimal solution for gene…