197 research outputs found
A multi-paradigm tool for large neighborhood search
No full textStudies in Computational Intelligence
Volume 434, 2013, Pages 389-414
A multi-paradigm tool for large neighborhood search (Article)
Cipriano, R.a , Di Gaspero, L.b , Dovier, A.a
a Dipartimento di Matematica e Informatica, Università Degli Studi di Udine, via delle Scienze 208, I-33100 Udine, Italy
b Dipartimento di Ingegneria Elettrica, Gestionale EMeccanica, Università Degli Studi di Udine, via delle Scienze 208, I-33100 Udine, Italy
View references (21)
Abstract
We present a general tool for encoding and solving optimization problems. Problems can be modeled using several paradigms and/or languages such as: Prolog, MiniZinc, and GECODE. Other paradigms can be included. Solution search is performed by a hybrid solver that exploits the potentiality of the Constraint Programming environment GECODE and of the Local Search framework EasyLocal++ for Large Neighborhood Search. The user can modify a set of parameters for guiding the hybrid search. In order to test the tool, we show the development phase of hybrid solvers on some benchmark problems. Moreover, we compare these solvers with other approaches, namely a pure Local Search, a pure constraint programming search, and with a state-of-the-art solver for constraint-based Local Search
A reinforcement learning approach for the cross-domain heuristic search challenge
No full textThe International Cross-Domain Heuristic Search Challenge (hereinafter CHeSC 2011) [3] is an ongoing competition that prompts for the design of a generally applicable high-level strategy for the automatic selection of problem-specific low-level heuristics across different problem domains. We participate in the challenge with a Reinforcement Learning approach. In this paper we describe the current state of the general algorithm by outlining our design choices and we present the preliminary results achieved by this approach.
QuadProg++: a C++ implementation of the Goldfarb-Idnani algorithm for Quadratic Programming
No full textStochastic local search for large-scale instances of the haplotype inference problem by parsimony
No full textHaplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms (in the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (integer Linear Programming, Semidefinite Programming, SAT and pseudo-boolean encoding) that, at present, are adequate only for moderate size instances. In this paper, we present and discuss an approach based on the combination of local search metaheuristics and a reduction procedure based on an analysis of the problem structure. Some relevant design issues are first described, then a family of local search metaheuristics is defined to tackle the Haplotype Inference. Results on common Haplotype Inference benchmarks show that the approach achieves a good trade-off between solution quality and execution time
EasyLocal++: An object-oriented framework for flexible design of local search algorithms
No full text- …
