Holger H. Hoos, Thomas Stützle
Abstract. MAX-SAT is a well-known optimisation problem that can be seen as a generalisation of the propositional satisfiability problem. In this study, we investigate how the performance of...
R.: On effectively finding maximal quasi-cliques in graphs (2009)
Mauro Brunato, Holger H. Hoos, Roberto Battiti
Abstract. The problem of finding a maximum clique in a graph is prototypical for many clustering and similarity problems; however, in many real-world scenarios, the classical problem of finding a...
Biedl, Therese, Durocher, Stephane, Hoos, Holger H., Luan, Shuang, Saia, Jared, Young, Maxwell
he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes...
Alena Shmygelska, Holger H. Hoos
Abstract. The prediction of a protein’s structure from its amino-acid sequence is one of the most important problems in computational biology. In the current work, we focus on a widely studied...
Helbich; Salieri { A general, interactive Computer Music System (2008)
Holger H. Hoos, Jurgen Kilian, Kai Renz, Thomas Helbich
Abstract. In this paper we describe the Salieri System, an interactive software environment for structure oriented composition, manipulation, and analysis of music. The system is built on the newly...
Mirela Andronescu, Anne Condon, Holger H. Hoos, David H. Mathews, Kevin P. Murphy
Motivation: Accurate prediction of RNA secondary structure from the base sequence is an unsolved computational challenge. The accuracy of predictions made by free energy minimization is limited by...
1 Preface SAT COMPETITION 2007- SOLVER DESCRIPTION Scaling and Probabilistic Smoothing (SAPS) (2008)
The first part of this paper is essentially a reprint of the solver description from the 2005 competition, as the software submitted this year is identical to the 2005 software. We entered the SAPS...
Thomas Stützle, Holger H. Hoos
Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned...
SATzilla: Portfolio-based Algorithm Selection for SAT (2008)
Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-brown
It has been widely observed that there is no single “dominant ” SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of...
On the Quality and Quantity of Random Decisions in Stochastic Local Search for SAT (2008)
Abstract. Stochastic local search (SLS) methods are underlying some of the best-performing algorithms for certain types of SAT instances, both from an empirical as well as from a theoretical point of...
A HTTP Interface to Salieri (2008)
Abstract. This paper describes how the Salieri System, a powerful and exible tool for composition, analysis, and editing of score level music, has been modi ed to serve asa music-server in a local or...
Abstract ¡£ ¢ – ¤¦ ¥ Ant System Stützle§ (2008)
Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned...
RNA STRAND: The RNA Secondary Structure and Statistical Analysis Database (2008)
Andronescu, Mirela, Bereg, Vera, Hoos, Holger H, Condon, Anne
Abstract Background The ability to access, search and analyse secondary structures of a large set of known RNA molecules is very important for deriving improved RNA energy models, for evaluating...
BIOINFORMATICS Neighbourhood Thresholding for Projection-Based Motif Discovery (2008)
James King, Warren Cheung, Holger H. Hoos
The PROJECTION algorithm by Buhler and Tompa is one of the best existing methods for solving hard motif discovery problems for monad motifs of fixed length l. In this paper we introduce the...
Rogic, Sanja, Montpetit, Ben, Hoos, Holger H, Mackworth, Alan K, Ouellette, BF Francis, Hieter, Philip
Abstract Background Secondary structure interactions within introns have been shown to be essential for efficient splicing of several yeast genes. The nature of these base-pairing interactions and...
1 Preface SAT COMPETITION 2007- SOLVER DESCRIPTION Scaling and Probabilistic Smoothing (SAPS) (2008)
The first part of this paper is essentially a reprint of the solver description from the 2005 competition, as the software submitted this year is identical to the 2005 software. We entered the SAPS...
On the Quality and Quantity of Random Decisions in Stochastic Local Search for SAT (2008)
Abstract. Stochastic local search (SLS) methods are underlying some of the best-performing algorithms for certain types of SAT instances, both from an empirical as well as from a theoretical point of...
Holger H. Hoos, Kevin Smyth, Thomas Stützle
Abstract. MAX-SAT is a well-known optimisation problem that can be seen as a generalisation of the propositional satisfiability problem. In this study, we investigate how the performance of...
Combinatorial auctions (CAs) have emerged as an important model in economics and show promise as a useful tool for tackling resource allocation in AI. Unfortunately, winner determination for CAs is...
et de Développements en Intelligence Artificielle (2008)
Enda Ridge, Thomas Stützle, Mauro Birattari, Holger H. Hoos
This publication is a collection of contributions presented at SLS-DS 2007, Doctoral Symposium
Holger H. Hoos, Thomas Stützle
Stochastic local search (SLS) algorithms have been successfully applied to hard combinatorial problems from different domains. Due to their inherent randomness, the run-time behaviour of these...
Mirela Andronescu, Vera Bereg, Holger H Hoos, Anne Condon, Anne Condon
This is an Open Access article distributed under the terms of the Creative Commons Attribution License
Ian P Gent, Holger H Hoos, Kevin Smyth
We present WalkQSAT, a solver for Quantified Boolean Formulae (QBFs) which makes use of stochastic local search. It is structured as two components, one of which controls the QBF search while the...
Scaling and Probabilistic Smoothing: Ecient Dynamic Local Search for SAT (2007)
Abstract. In this paper, we study the approach of dynamic local search for the SAT problem. We focus on the recent and promising Exponentiated Sub-Gradient (ESG) algorithm, and examine the factors...
Alena Shmygelska, Holger H. Hoos
Abstract. The prediction of a protein’s structure from its amino-acid sequence is one of the most important problems in computational biology. In the current work, we focus on a widely studied...
For the past decade, various types of stochastic local search (SLS) methods have been applied very successfully to the propositional satisfiability problem (SAT). These include
MAX--MIN Ant System Thomas St utzle (2007)
Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned...
Abstract A New Algorithm for RNA Secondary Structure Design � (2007)
Mirela Andronescu, Anthony P. Fejes, Frank Hutter, Anne Condon, Holger H. Hoos
The function of many RNAs crucially depends on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g., in the context of...
Ian P. Gent, Holger H. Hoos, Patrick Prosser, Toby Walsh
We introduce a mechanism called "morphing " for introducing structure or randomness into a wide variety of problems. We illustrate the usefulness of morphing by performing several...
A replica exchange Monte Carlo algorithm for protein folding in the HP model (2007)
Thachuk, Chris, Shmygelska, Alena, Hoos, Holger H
Abstract Background The ab initio protein folding problem consists of predicting protein tertiary structure from a given amino acid sequence by minimizing an energy function; it is one of the most...
Efficient parameter estimation for RNA secondary structure prediction (2007)
Andronescu, Mirela, Condon, Anne, Hoos, Holger H., Mathews, David H., Murphy, Kevin P.
Motivation: Accurate prediction of RNA secondary structure from the base sequence is an unsolved computational challenge. The accuracy of predictions made by free energy minimization is limited by...
An adaptive bin framework search method for a beta-sheet protein homopolymer model (2007)
Shmygelska, Alena, Hoos, Holger H
Abstract Background The problem of protein structure prediction consists of predicting the functional or native structure of a protein given its linear sequence of amino acids. This problem has...
Computational RNA secondary structure design: empirical complexity and improved methods (2007)
Aguirre-Hernández, Rosalía, Hoos, Holger H, Condon, Anne
Abstract Background We investigate the empirical complexity of the RNA secondary structure design problem, that is, the scaling of the typical difficulty of the design task for various classes of RNA...
Boosting Verification by Automatic Tuning of Decision Procedures (2007)
Frank Hutter, Domagoj Babić, Holger H. Hoos, Alan J. Hu
Abstract—Parameterized heuristics abound in computer aided design and verification, and manual tuning of the respective parameters is difficult and time-consuming. Very recent results from the...
BMC Bioinformatics BioMed Central (2007)
Alena Shmygelska, Holger H Hoos
Research article An adaptive bin framework search method for a beta-sheet protein homopolymer model
Boosting Verification by Automatic Tuning of Decision Procedures (2007)
Frank Hutter, Domagoj Babić, Holger H. Hoos, Alan J. Hu
Abstract—Parameterized heuristics abound in computer aided design and verification, and manual tuning of the respective parameters is difficult and time-consuming. Very recent results from the...
SATzilla2007: a new & improved algorithm portfolio for SAT (2007)
Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-brown
Empirical studies often observe that the performance of
Automatic Algorithm Configuration based on Local Search (2007)
The determination of appropriate values for free algorithm parameters is a challenging and tedious task in the design of effective algorithms for hard problems. Such parameters include categorical...
Boosting Verification by Automatic Tuning of Decision Procedures (2007)
Frank Hutter, Domagoj Babić, Holger H. Hoos, Alan J. Hu
Abstract—Parameterized heuristics abound in computer aided design and verification, and manual tuning of the respective parameters is difficult and time-consuming. Very recent results from the...
SATzilla-07: The design and analysis of an algorithm portfolio for SAT (2007)
Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-brown
Abstract. It has been widely observed that there is no “dominant” SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of...
Hierarchical hardness models for SAT (2007)
Lin Xu, Holger H. Hoos, Kevin Leyton-brown
Abstract. Empirical hardness models predict a solver’s runtime for a given instance of an N P-hard problem based on efficiently computable features. Previous research in the SAT domain has shown...
T.: Automatic algorithm configuration based on local search (2007)
Frank Hutter, Holger H. Hoos, Thomas Stutzle
The determination of appropriate values for free algorithm parameters is a challenging and tedious task in the design of effective algorithms for hard problems. Such parameters include categorical...
Bmc Bioinformatics, Chris Thachuk, Alena Shmygelska, Holger H Hoos
Research article A replica exchange Monte Carlo algorithm for protein folding in the HP model
SATzilla-07: The design and analysis of an algorithm portfolio for SAT (2007)
Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-brown
Abstract. It has been widely observed that there is no “dominant” SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of...
complexity and improved methods (2007)
Bmc Bioinformatics, Rosalía Aguirre-hernández, Holger H Hoos, Anne Condon
Computational RNA secondary structure design: empirical
Dynamic Local Search for the Maximum Clique Problem (2006)
Pullan, Wayne John, Hoos, Holger H.
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices...
Dynamic Local Search for the Maximum Clique Problem (2006)
Pullan, Wayne John, Hoos, Holger H.
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices...
Performance prediction and automated tuning of randomized and parametric algorithms (2006)
Frank Hutter, Youssef Hamadi, Holger H. Hoos, Kevin Leyton-brown
Abstract. Machine learning can be used to build models that predict the runtime of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied for...
Performance prediction and automated tuning of randomized and parametric algorithms (2006)
Frank Hutter, Youssef Hamadi, Holger H. Hoos, Kevin Leyton-brown
Abstract. Machine learning can be utilized to build models that predict the runtime of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied...
Dynamic local search for the maximum clique problem (2006)
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices...
Dynamic local search for the maximum clique problem (2006)
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices...
Dynamic Local Search for the Maximum Clique Problem (2006)
Pullan, Wayne John, Hoos, Holger H.
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices...
Shmygelska, Alena, Hoos, Holger H
Abstract Background The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of...
Thermodynamically based dna strand design (2005)
Dan Tulpan, Mirela Andronescu, Seo Bong Chang, Michael R. Shortreed, Anne Condon, Holger H. Hoos, ...
We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial...
hydrophobic polar protein folding problem (2005)
Bmc Bioinformatics, Alena Shmygelska, Holger H Hoos, Alena Shmygelska, Holger H Hoos
An ant colony optimisation algorithm for the 2D and 3D
A thermodynamic approach to designing structure-free combinatorial DNA word sets (2005)
Michael R. Shortreed, Seo Bong Chang, Donggee Hong, Maggie Phillips, Bridget Campion, Dan C. Tulpan, ...
word sets
Thermodynamically based dna strand design (2005)
Dan Tulpan, Mirela Andronescu, Seo Bong Chang, Michael R. Shortreed, Anne Condon, Holger H. Hoos, ...
We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial...
HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots (2005)
REN, JIHONG, RASTEGARI, BAHARAK, CONDON, ANNE, HOOS, HOLGER H.
We present HotKnots, a new heuristic algorithm for the prediction of RNA secondary structures including pseudoknots. Based on the simple idea of iteratively forming stable stems, our algorithm...
Thermodynamically based DNA strand design (2005)
Tulpan, Dan, Andronescu, Mirela, Chang, Seo Bong, Shortreed, Michael R., Condon, Anne, Hoos, Holger H., ...
We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial...
A thermodynamic approach to designing structure-free combinatorial DNA word sets (2005)
Shortreed, Michael R., Chang, Seo Bong, Hong, DongGee, Phillips, Maggie, Campion, Bridget, Tulpan, Dan C., ...
An algorithm is presented for the generation of sets of non-interacting DNA sequences, employing existing thermodynamic models for the prediction of duplex stabilities and secondary structures. A DNA...
Stochastic local search : foundations and applications / (2004)
Stützle, Thomas G., Hoos, Holger H.
Darmstadt, Techn. Universiẗat, Habil.-Schr.
Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, David Poole
Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this...
Warped landscapes and random acts of SAT solving (2004)
Recent dynamic local search (DLS) algorithms such as SAPS are amongst the state-of-the-art methods for solving the propositional satisfiability problem (SAT). DLS algorithms modify the search...
Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
In many domains it is desirable to assess the preferences of users in a qualitative rather than quantitative way. Useful representations of qualitative preference orderings form an important...
Scaling and Probabilistic Smoothing (SAPS) 1 SAPS and Variants (2004)
(DLS) algorithm conceptually closely related to the Exponentiated Sub-Gradient (ESG) algorithm developed by Schuurmans, Southey and Holte [3]. When introducing SAPS, our major contributions were a...
Scaling and Probabilistic Smoothing (SAPS) 1 SAPS and Variants (2004)
(DLS) algorithm conceptually closely related to the Exponentiated Sub-Gradient (ESG) algorithm developed by Schuurmans, Southey and Holte [3]. When introducing SAPS, our major contributions were a...
Abstract. In this paper we introduce UBCSAT, a new implementation and experimentation environment for Stochastic Local Search (SLS) algorithms for SAT and MAX-SAT. Based on a novel triggered...
Preference-based constrained optimization with CP-nets (2004)
Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
Many AI tasks, such as product conguration, decision support, and the construction of autonomous agents, involve a process of constrained optimization, that is, optimization of behavior or choices...
Warped Landscapes and Random Acts of SAT Solving (2004)
Dave Tompkins And, Holger H. Hoos
Recent dynamic local search (DLS) algorithms such as SAPS are amongst the state-of-the-art methods for solving the propositional satisfiability problem (SAT). DLS algorithms modify the search...
Warped Landscapes and Random Acts of SAT Solving (2004)
Dave Tompkins And, Holger H. Hoos
Recent dynamic local search (DLS) algorithms such as SAPS are amongst the state-of-the-art methods for solving the propositional satisfiability problem (SAT). DLS algorithms modify the search...
MusicBLAST - Gapped Sequence Alignment for MIR (2004)
We propose an algorithm, MusicBLAST, for approximate pattern search/matching on symbolic musical data. MusicBLAST is based on the BLAST algorithm, one of the most commonly used algorithms for...
Conditional Ceteris Paribus, Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this...
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Kevin Leyton-brown, Holger H. Hoos, Alex Devkar, Yoav Shoham
Abstract. It is well known that the ratio of the number of clauses to the number of variables in a random k-SAT instance is highly correlated with the instance’s empirical hardness. We consider the...
Preference-based constrained optimization with CP-nets (2004)
Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, David Poole
Many AI tasks, such as product configuration, decision support, and the construction of autonomous agents, involve a process of con-1 strained optimization, that is, optimization of behavior or...
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Kevin Leyton-brown, Holger H. Hoos, Alex Devkar, Yoav Shoham
Abstract. It is well known that the ratio of the number of clauses to the numberof variables in a random k-SAT instance is highly correlated with the instance'sempirical hardness. We consider...
Preference-based constrained optimization with CP-nets (2004)
Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, David Poole
Many AI tasks, such as product configuration, decision support, and the construction of autonomous agents, involve a process of con-1 strained optimization, that is, optimization of behavior or...
Abstract. In this paper we introduce UBCSAT, a new implementation and experimentation environment for Stochastic Local Search (SLS) algorithms for SAT and MAX-SAT. Based on a novel triggered...
Conditional Ceteris Paribus, Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this...
Abstract. In this paper we introduce UBCSAT, a new implementation and experimentation environment for Stochastic Local Search (SLS) algorithms for SAT and MAX-SAT. Based on a novel triggered...
Iterated Robust Tabu Search for MAX-SAT (2003)
Kevin Smyth, Holger H. Hoos, Thomas Stützle
Abstract. MAX-SAT, the optimisation variant of the satisfiability problem in propositional logic, is an important and widely studied combinatorial optimisation problem with applications in AI and...
Stochastic Local Search for Multiprocessor Scheduling for Minimum Total Tardiness (2003)
Michael Pavlin, Holger H. Hoos, Thomas Stützle
Abstract. The multi-processor total tardiness problem (MPTTP) is an ÆÈ-hard scheduling problem, in which the goal is to minimise the tardiness of a set of jobs that are processed on a number of...
An improved ant colony optimization algorithm for the 2d hp protein folding problem (2003)
Alena Shmygelska, Holger H Hoos
Abstract. The prediction of a protein's conformation from its aminoacid sequence is one of the most prominent problems in computational biology. Here, we focus on a widely studied abstraction of...
Scaling and probabilistic smoothing: Dynamic local search for unweighted MAX-SAT (2003)
Abstract. In this paper, we study the behaviour of the Scaling and Probabilistic Smoothing (SAPS) dynamic local search algorithm on the unweighted MAX-SAT problem. MAX-SAT is a conceptually simple...
Hybrid randomised neighbourhoods improve stochastic local search for DNA Code design (2003)
Abstract. Sets of DNA strands that satisfy combinatorial constraints play an important role in various approaches to biomolecular computation, nanostructure design, and molecular tagging. The problem...
Using Stochastic Local Search to Solve Quantified (2003)
Boolean Formulae Ian, Ian P Gent, Holger H Hoos, Kevin Smyth
We present a novel approach to solving Quantified Boolean Formulae (QBFs), exploiting the power of stochastic local search methods for SAT. This makes the search process different in some interesting...
Using Stochastic Local Search to Solve Quantified Boolean Formulae (2003)
Ian P Gent, Holger H Hoos, Kevin Smyth
We present a novel approach to solving Quantified Boolean Formulae (QBFs), exploiting the power of stochastic local search methods for SAT. This makes the search process different in some interesting...
Using stochastic local search to solve quantified boolean formulae (2003)
Ian P Gent, Holger H Hoos, Kevin Smyth
We present WalkQSAT, a solver for Quantified Boolean Formulae (QBFs) which makes use of stochastic local search. It is structured as two components, one of which controls the QBF search while the...
Using stochastic local search to solve quantified boolean formulae (2003)
Ian P Gent, Holger H Hoos, Kevin Smyth
Abstract. We present a novel approach to solving Quantified Boolean Formulae (QBFs), exploiting the power of stochastic local search methods for SAT. This makes the search process different in some...
RNAsoft: a suite of RNA secondary structure prediction and design software tools (2003)
Mirela Andronescu, Rosalía Aguirre-hernández, Anne Condon, Holger H. Hoos
DNA and RNA strands are employed in novel ways in the construtSW n of nanostruostSW , asmolecu ar tags in libraries of polymers and intherapeu ics. New software tools for prediction and design...
Inference of transcriptional regulation relationships from gene expression data (2003)
Kwon, Andrew T., Hoos, Holger H., Ng, Raymond
Motivation: In order to find gene regulatory networks from microarray data, it is important to first find direct regulatory relationships between pairs of genes. Results: We propose a new method for...
RNAsoft: a suite of RNA secondary structure prediction and design software tools (2003)
Andronescu, Mirela, Aguirre-Hernández, Rosalía, Condon, Anne, Hoos, Holger H.
DNA and RNA strands are employed in novel ways in the construction of nanostructures, as molecular tags in libraries of polymers and in therapeutics. New software tools for prediction and design of...
An adaptive noise mechanism for walksat (2002)
Stochastic local search algorithms based on the WalkSAT architecture are among the best known methods for solving hard and large instances of the propositional satisfiability problem (SAT). The...
A mixture-model for the behaviour of SLS algorithms for SAT (2002)
Stochastic Local Search (SLS) algorithms are amongst the most effective approaches for solving hard and large propositional satisfiability (SAT) problems. Prominent and successful SLS algorithms for...
Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT (2002)
In this paper, we study the approach of dynamic local search for the SAT problem. We focus on the recent and promising Exponentiated Sub-Gradient (ESG) algorithm, and examine the factors determining...
An Adaptive Noise Mechanism for WalkSAT (2002)
Stochastic local search algorithms based on the WalkSAT architecture are among the best known methods for solving hard and large instances of the propositional satisfiability problem (SAT). The...
Bidding languages for combinatorial auctions (2001)
Craig Boutilier, Holger H. Hoos
Combinatorial auctions provide a valuable mechanism for the allocation of goods in settings where buyer valuations exhibit complex structure with respect to substitutability and complementarity. Most...
Holger H. Hoos, Kai Renz, Marko Görg
Musical databases are growing in number, size, and complexity, and they are becoming increasingly relevant for a broad range of academic as well as commercial applications. The features and...
VISCO -- Visual SALIERI Components (2000)
Juergen Kilian (Department Of Computer Science, Darmstadt University Of Technology), Holger H. Hoos (Department Of Computer Science, University Of British Columbia)
On the probabilistic approximate completeness of WalkSAT for 2-SAT (2000)
Joseph Culberson, Ian P. Gent, Holger H. Hoos
Introduction. The WalkSAT algorithm framework is a family of highly successful stochastic local search (SLS) algorithms for the Satisability problem [6, 5]. WalkSAT/SKC, the rst and most popular...
Stochastic local search methods for dynamic SAT–an initial investigation (2000)
Abstract. We introduce the dynamic SAT problem, a generalisation of the satisfiability problem in propositional logic which allows changes of a problem over time. DynSAT can be seen as a particular...
Solving combinatorial auctions using stochastic local search (2000)
Holger H. Hoos, Craig Boutilier
Combinatorial auctions (CAs) have emerged as an important model in economics and show promise as a useful tool for tackling resource allocation in AI. Unfortunately, winner determination for CAs is...
Local search algorithms for SAT: An empirical evaluation (2000)
Holger H. Hoos, Thomas Stutzle
Abstract. Local search algorithms are among the standard methods for solving hard combinatorial problems from various areas of Artificial Intelligence and Operations Research. For SAT, some of the...
SATLIB: An Online Resource for Research on SAT (2000)
Holger H. Hoos, Thomas Stutzle
Abstract. SATLIB is an online resource for SAT-related research established in June 1998. Its core components, a benchmark suite of SAT instances and a collection of SAT solvers, aim to facilitate...
Stochastic Local Search Methods for Dynamic SAT (2000)
An Initial Investigation, Holger H. Hoos
We introduce the dynamic SAT problem, a generalisation of the satisfiability problem in propositional logic which allows changes of a problem over time. DynSAT can be seen as a particular form of a...
Local search algorithms for SAT: An empirical evaluation (2000)
Holger H. Hoos, Thomas Stützle
Abstract. Local search algorithms are among the standard methods for solving hard combinatorial problems from various areas of Artificial Intelligence and Operations Research. For SAT, some of the...
SATLIB: An Online Resource for Research on SAT (2000)
Abstract. SATLIB is an online resource for SAT-related research established in June 1998. Its core components, a benchmark suite of SAT instances and a collection of SAT solvers, aim to facilitate...
Solving combinatorial auctions using stochastic local search (2000)
Combinatorial auctions (CAs) have emerged as an important model in economics and show promise as a useful tool for tackling resource allocation in AI. Unfortunately, winner determination for CAs is...
Stochastic local search : methods, models, applications / (1999)
Thesis (doctoral)--Technische Universität, Darmstadt, 1998.
Using Advanced GUIDO as a Notation Interchange Format (1999)
Holger H. Hoos (Department Of Computer Science, University Of British Columbia, Vancouver), Keith A. Hamel (School Of Music, University Of British Columbia, Vancouver), Kai Renz (Department Of Computer Science, Darmstadt University Of Technology)
To encode or not to encode - i: linear planning (1999)
Ronen I. Brafman, Holger H. Hoos
Stochastic local search (SLS) techniques are very effective in solving hard propositional satisfiability problems. This has lead to the popularity of the encode & solve paradigm in which...
Reasoning with Conditional Ceteris Paribus Preference Statements (1999)
Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
In many domains it is desirable to assess the preferences of users in a qualitative rather than quantitative way. Such representations of qualitative preference orderings form an important component...
Systematic vs. local search for sat (1999)
Holger H. Hoos, Thomas Stutzle
Abstract. Due to its prominence in artificial intelligence and theoretical computer science, the propositional satisfiability problem (SAT) has received considerable attention in the past....
Heavy-tailed behaviour in randomised systematic search algorithms for SAT (1999)
Prompted by recent results reported by Carla Gomes, Bart Selman, and Henry Kautz, and in the context of my ongoing project with Thomas Stutzle on characterising the behaviour of state-of-the-art...
Towards a characterisation of the behaviour of stochastic local search algorithms for sat (1999)
Holger H. Hoos, Thomas Stutzle
Stochastic local search (SLS) algorithms have been successfully applied to hard combinatorial problems from different domains. Due to their inherent randomness, the run-time behaviour of these...
Systematic vs. Local Search for SAT (1999)
Holger H. Hoos, Thomas Stützle
. Traditionally, the propositional satisfiability problem (SAT) was attacked with systematic search algorithms, but more recently, local search methods were shown to be very effective for solving...
Thomas Stützle, Holger H. Hoos
Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned...
Local Search Algorithms for SAT: An Empirical Evaluation (1999)
Holger H. Hoos, Thomas Stützle
. Local search algorithms are among the standard methods for solving hard combinatorial problems from various areas of Artificial Intelligence and Operations Research. For SAT, some of the most...
On the Run-time Behaviour of Stochastic Local Search Algorithms for SAT (1999)
Stochastic local search (SLS) algorithms for the propositional satisfiability problem (SAT) have been successfully applied to solve suitably encoded search problems from various domains. One drawback...
Analyzing the run-time behaviour of iterated local search for the TSP (1999)
Thomas Stutzle, Holger H. Hoos
Metaheuristics strongly involve random decisions made during the search process. Because of their nondeterministic nature, the run-time needed by such an algorithm to achieve a specific goal--- like...
Analyzing the Run-time Behaviour of Iterated Local Search for the TSP (1999)
Thomas Stützle, Holger H. Hoos
this article are taken from the TSPLIB Benchmark library accessible at http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html. These instances are actually Euclidean instances, that...
Reasoning With Conditional Ceteris Paribus Preference Statements (1999)
Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
In many domains it is desirable to assess the preferences of users in a qualitative rather than quantitative way. Such representations of qualitative preference orderings form an important component...
SAT-Encodings, Search Space Structure, and Local Search Performance (1999)
Stochastic local search (SLS) algorithms for propositional satisfiability testing (SAT) have become popular and powerful tools for solving suitably encoded hard combinatorial from different domains...
To Encode or not to Encode - I: Linear Planning (1999)
Ronen I. Brafman, Holger H. Hoos
Stochastic local search (SLS) techniques are very effective in solving hard propositional satisfiability problems. This has lead to the popularity of the encode & solve paradigm in which...
Reasoning With Conditional Ceteris Paribus Preference Statements (1999)
Craig Boutilier, Ronen I. Brafman, Holger H. Hoos, David Poole
In many domains it is desirable to assess the preferences of users in a qualitative rather than quantitative way. Such representations of qualitative preference orderings form an important component...
Systematic vs. local search for sat (1999)
Holger H. Hoos, Thomas Stützle
Abstract. Due to its prominence in artificial intelligence and theoretical computer science, the propositional satisfiability problem (SAT) has received considerable attention in the past....
The GUIDO Notation Format: A Novel Approach for Adequately Representing Score-Level Music (1998)
Holger H. Hoos (Fachbereich Informatik, Technische Universitat Darmstadt, Alexanderstr. 10, D-64283 Darmstadt, Germany), Keith A. Hamel (School Of Music, University Of British Columbia), Kai Renz (Fachbereich Informatik, Technische Universitat Darmstadt, Alexanderstr. 10, D-64283 Darmstadt, Germany), Jurgen Kilian (Fachbereich Informatik, Technische Universitat Darmstadt, Alexanderstr. 10, D-64283 Darmstadt, Germany)
An HTTP Interface to Salieri (1998)
Kai Renz (Darmstadt University Of Technology), Holger H. Hoos (Darmstadt University Of Technology)
Salieri: A General, Interactive Computer Music System (1998)
Holger H. Hoos (Darmstadt University Of Technology), Jurgen Kilian (), Kai Renz (), Thomas Helbich ()
A WEB-based Approach to Music Notation using GUIDO (1998)
Kai Renz (Darmstadt University Of Technology), Holger H. Hoos ()
A WEB-based Approach to Music Notation using GUIDO (1998)
Abstract. This paper describes how exible, online conventional music notation (CMN) can be obtained using the powerful music description language GUIDO in conjunction with the WEB-based GUIDO...
LPSP - A linear plan-level stochastic planner (1998)
Ronen I. Brafman, Holger H. Hoos, Craig Boutilier
We describe LPSP, a domain-independent planning algorithm that searches the space of linear plans using stochastic local search techniques. Because linear plans, rather than propositional...
Characterizing the Run-time Behavior of Stochastic Local Search (1998)
Holger Hoos, Holger H. Hoos, Thomas Stützle, Thomas Stutzle, Fachgebiet Intellektik, ...
Stochastic local search (SLS) algorithms have been successfully applied to hard combinatorial problems from different domains. One important feature of SLS algorithms is the fact that their run-time...
LPSP: A Linear Plan-level Stochastic Planner (1998)
Ronen I. Brafman, Holger H. Hoos, Craig Boutilier
We describe LPSP, a domain-independent planning algorithm that searches the space of linear plans using stochastic local search techniques. Because linear plans, rather than propositional...
Evaluating Las Vegas algorithms --- pitfalls and remedies (1998)
Holger H. Hoos, Thomas Stutzle
Stochastic search algorithms are among the most sucessful approaches for solving hard combinatorial problems. A large class of stochastic search approaches can be cast into the framework of Las Vegas...
A Characterization of GSAT's Performance on a Class of Hard Structured Problems (1996)
Holger Hoos, Fachgebiet Intellektik, Holger H. Hoos, Thomas Stützle, ...
Randomized algorithms for solving hard satisfiability problems have been successfully applied to many application areas, but are still poorly understood. In this work, we show that, applied to...
Solving Hard Combinatorial Problems with GSAT - a Case Study (1996)
. In this paper, we investigate whether hard combinatorial problems such as the Hamiltonian circuit problem HCP (an NP-complete problem from graph theory) can be practically solved by transformation...
RNAsoft: a suite of RNA secondary structure prediction and design software tools
Andronescu, Mirela, Aguirre-Hernández, Rosalía, Condon, Anne, Hoos, Holger H.
DNA and RNA strands are employed in novel ways in the construction of nanostructures, as molecular tags in libraries of polymers and in therapeutics. New software tools for prediction and design of...
A thermodynamic approach to designing structure-free combinatorial DNA word sets
Shortreed, Michael R., Chang, Seo Bong, Hong, DongGee, Phillips, Maggie, Campion, Bridget, Tulpan, Dan C., ...
An algorithm is presented for the generation of sets of non-interacting DNA sequences, employing existing thermodynamic models for the prediction of duplex stabilities and secondary structures. A DNA...
Thermodynamically based DNA strand design
Tulpan, Dan, Andronescu, Mirela, Chang, Seo Bong, Shortreed, Michael R., Condon, Anne, Hoos, Holger H., ...
We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial...
HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots
REN, JIHONG, RASTEGARI, BAHARAK, CONDON, ANNE, HOOS, HOLGER H.
We present HotKnots, a new heuristic algorithm for the prediction of RNA secondary structures including pseudoknots. Based on the simple idea of iteratively forming stable stems, our algorithm...
RNAsoft: a suite of RNA secondary structure prediction and design software tools
Andronescu, Mirela, Aguirre-Hernández, Rosalía, Condon, Anne, Hoos, Holger H.
DNA and RNA strands are employed in novel ways in the construction of nanostructures, as molecular tags in libraries of polymers and in therapeutics. New software tools for prediction and design of...
A thermodynamic approach to designing structure-free combinatorial DNA word sets
Shortreed, Michael R., Chang, Seo Bong, Hong, DongGee, Phillips, Maggie, Campion, Bridget, Tulpan, Dan C., ...
An algorithm is presented for the generation of sets of non-interacting DNA sequences, employing existing thermodynamic models for the prediction of duplex stabilities and secondary structures. A DNA...
Thermodynamically based DNA strand design
Tulpan, Dan, Andronescu, Mirela, Chang, Seo Bong, Shortreed, Michael R., Condon, Anne, Hoos, Holger H., ...
We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial...
HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots
REN, JIHONG, RASTEGARI, BAHARAK, CONDON, ANNE, HOOS, HOLGER H.
We present HotKnots, a new heuristic algorithm for the prediction of RNA secondary structures including pseudoknots. Based on the simple idea of iteratively forming stable stems, our algorithm...
RNA STRAND: The RNA Secondary Structure and Statistical Analysis Database
Andronescu, Mirela, Bereg, Vera, Hoos, Holger H, Condon, Anne
Rogic, Sanja, Montpetit, Ben, Hoos, Holger H, Mackworth, Alan K, Ouellette, BF Francis, Hieter, Philip
Using Advanced GUIDO as a Notation Interchange Format
Holger H. Hoos, Keith A. Hamel, Kai Renz
GUIDO Music Notation is a new music representation format based on the notion of representational adequacy, i.e., it represents simple musical concepts in simple ways, and requires complex...