Encontrados 17 documentos, a visualizar página 1 de 2
Quantum and Digital Annealing for the Quadratic Assignment Problem
Codognet, Philippe; Diaz, Daniel; Abreu, SalvadorThe Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware so...
Parallel Local Search
Codognet, Philippe; Munera, Danny; Diaz, Daniel; Abreu, SalvadorLocal search metaheuristics are a recognized means of solving hard com- binatorial problems. Over the last couple of decades, significant advances have been made in terms of the formalization, applicability and performance of these methods. Key to the performance aspect is the increased availability of parallel hardware, which turns out to be largely exploitable by this class of procedures. As real-life cases o...
Large-scale parallelism for constraint-based local search: the costas array cas...
Caniou, Yves; Codognet, Philippe; Richoux, Florian; Diaz, Daniel; Abreu, SalvadorWe present the parallel implementation of a constraint-based Local Search algorithm and investigate its performance on several hardware platforms with several hundreds or thousands of cores. We chose as the basis for these experiments the Adaptive Search method, an efficient sequential Local Search method for Constraint Satisfaction Problems (CSP). After preliminary experiments on some CSPLib benchmarks, we det...
Solving Hard Stable Matching Problems via Local Search and Cooperative Parallel...
Munera, Danny; Diaz, Daniel; Abreu, Salvador; Rossi, Francesca; Saraswat, Vijay; Codognet, PhilippeStable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parall...
A Local Search Algorithm for SMTI and its extension to HRT Problems
Munera, Danny; Diaz, Daniel; Abreu, Salvador; Rossi, Francesca; Saraswat, Vijay; Codognet, PhilippeHospitals/Residents with Ties (HRT) forms a class of problems with many applications, some of which are of considerable size. Solving these problems has been shown to be NP-hard. In previous work, we developed a local search algorithm which displays very high performance in solving Stable Matching with Ties and Incomplete lists (SMTI) problems. In this paper, we propose a method to tackle HRT problems with a sl...
A parametric framework for cooperative parallel local search
Munera, Danny; Diaz, Daniel; Abreu, Salvador; Codognet, PhilippeAbstract In this paper we address the problem of parallelizing local search. We propose a general framework where different local search engines cooperate (through communication) in the quest for a solution. Several parameters allow the user to instantiate and customize the framework, like the degree of intensification and diversification. We implemented a prototype in the X10 programming language based on the ...
Flexible cooperation in parallel local search
Munera, Danny; Diaz, Daniel; Abreu, Salvador; Codognet, PhilippeAbstract Constraint-Based Local Search (CBLS) consist in using Local Search methods [4] for solving Constraint Satisfaction Problems (CSP). In order to further improve the performance of Local Search, one possible option is to take advantage of the increasing availability of parallel computational resources. Parallel implementation of local search meta- heuristics has been studied since the early 90's, when mul...
On the Implementation of GNU Prolog
Diaz, Daniel; Abreu, Salvador; Codognet, PhilippeGNU Prolog is a general-purpose implementation of the Prolog language, which distinguishes itself from most other systems by being, above all else, a native-code compiler which produces stand-alone executables which do not rely on any bytecode emulator or meta-interpreter. Other aspects which stand out include the explicit organization of the Prolog system as a multipass compiler, where intermediate representat...
Targeting the Cell Broadband Engine for constraint-based local search
Diaz, Daniel; Abreu, Salvador; Codognet, PhilippeWe investigated the use of the Cell Broadband Engine (Cell/BE) for constraint-based local search and combinatorial optimization applications. We presented a parallel version of a constraint-based local search algorithm that was chosen because it fits very well the Cell/BE architecture because it requires neither shared memory nor communication among processors. The performance study on several large optimizatio...
Performance Analysis of Parallel Constraint-Based Local Search
Abreu, Salvador; Caniou, Yves; Codognet, Philippe; Diaz, Daniel; Richoux, FlorialWe present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hard- ware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the ”adaptive search” method, an efficient sequential local search method for Constraint Satisfaction Problems. The implemented algorithm is a parallel version of adaptive...