Search results for " Computer Science"
showing 10 items of 3983 documents
Variable neighborhood search for the linear ordering problem
2006
Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is cou…
Adaptive memory programming for constrained global optimization
2010
The problem of finding a global optimum of a constrained multimodal function has been the subject of intensive study in recent years. Several effective global optimization algorithms for constrained problems have been developed; among them, the multi-start procedures discussed in Ugray et al. [1] are the most effective. We present some new multi-start methods based on the framework of adaptive memory programming (AMP), which involve memory structures that are superimposed on a local optimizer. Computational comparisons involving widely used gradient-based local solvers, such as Conopt and OQNLP, are performed on a testbed of 41 problems that have been used to calibrate the performance of su…
A Local Selection Algorithm for Switching Function Minimization
1984
The minimization algorithms which do not require any preliminary generation of all the prime implicants (PI's) of a function are the most efficient. In this work a new algorithm is described which follows such an approach. It is based on a local selection of PI's carried out by examining a set of vertices whose number is never greater than the number of PI's of a minimum cost cover. This algorithm takes advantage of a technique which uses numerical equivalents of the function vertices as pointers. For this reason it is well suited for implementation by computer. To illustrate the features of this algorithm a few examples are reported.
An Island Strategy for Memetic Discrete Tomography Reconstruction
2014
In this paper we present a parallel island model memetic algorithm for binary discrete tomography reconstruction that uses only four projections without any further a priori information. The underlying combination strategy consists in separated populations of agents that evolve by means of different processes. Agents progress towards a possible solution by using genetic operators, switch and a particular compactness operator. A guided migration scheme is applied to select suitable migrants by considering both their own and their sub-population fitness. That is, from time to time, we allow some individuals to transfer to different subpopulations. The benefits of this paradigm were tested in …
An exact algorithm for the fuzzy p-median problem
1999
In this paper we propose a fuzzy version of the classical p-median problem. We consider a fuzzy set of constraints so that the decision-maker will be able to take into account solutions which provide significantly lower costs by leaving a part of the demand uncovered. We propose an algorithm for solving the problem which is based on Hakimi's works and we compare the crisp and the fuzzy approach by means of an example.
On the equivalence of two optimization methods for fuzzy linear programming problems
2000
Abstract The paper analyses the linear programming problem with fuzzy coefficients in the objective function. The set of nondominated (ND) solutions with respect to an assumed fuzzy preference relation, according to Orlovsky's concept, is supposed to be the solution of the problem. Special attention is paid to unfuzzy nondominated (UND) solutions (the solutions which are nondominated to the degree one). The main results of the paper are sufficient conditions on a fuzzy preference relation allowing to reduce the problem of determining UND solutions to that of determining the optimal solutions of a classical linear programming problem. These solutions can thus be determined by means of classi…
Viability of infeasible portfolio selection problems: A fuzzy approach
2002
Abstract This paper deals with fuzzy optimization schemes for managing a portfolio in the framework of risk–return trade-off. Different models coexist to select the best portfolio according to their respective objective functions and many of them are linearly constrained. We are concerned with the infeasible instances of such models. This infeasibility, usually provoked by the conflict between the desired return and the diversification requirements proposed by the investor, can be satisfactorily avoided by using fuzzy linear programming techniques. We propose an algorithm to repair infeasibility and we illustrate its performance on a numerical example.
The fuzzy p-median problem: A global analysis of the solutions
2001
Abstract We apply fuzzy techniques to incorporate external data into p-median problems. So we can detect certain solutions that would be discarded by usual crisp and fuzzy algorithms but that contrasted with this additional information can be advantageous. This usually reveals a pathology of the model and hence our methods provide some fuzzy validation criteria for p-median models.
Reducing the bandwidth of a sparse matrix with tabu search
2001
The bandwidth of a matrix { } ij a A = is defined as the maximum absolute difference between i and j for which 0 ≠ ij a . The problem of reducing the bandwidth of a matrix consists of finding a permutation of the rows and columns that keeps the nonzero elements in a band that is as close as possible to the main diagonal of the matrix. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the nonzero elements of the corresponding symmetrical matrix. Many bandwidth reduction algorithms have been developed since the 1960s and applied to structural engineering, fluid dynamics and network analysis. For the most part, these procedures do not incorpo…
A branch and bound algorithm for the maximum diversity problem
2010
This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous line…