Arrow Research search

Author name cluster

Meinolf Sellmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

SAT Conference 2021 Conference Paper

PyDGGA: Distributed GGA for Automatic Configuration

  • Carlos Ansótegui
  • Josep Pon
  • Meinolf Sellmann
  • Kevin Tierney

Abstract We present PyDGGA, a Python tool that implements a distributed version of the automatic algorithm configurator GGA, which is a specialized genetic algorithm to find high quality parameters for solvers and algorithms. PyDGGA implements GGA using an event-driven architecture and runs a simulation of future generations of the genetic algorithm to maximize the usage of the available computing resources. Overall, PyDGGA offers a friendly interface to deploy elastic distributed AC scenarios on shared high-performance computing clusters.

Details

AAAI Conference 2019 Conference Paper

Consensual Affine Transformations for Partial Valuation Aggregation

  • Hermann Schichl
  • Meinolf Sellmann

We consider the task of aggregating scores provided by experts that each have scored only a subset of all objects to be rated. Since experts only see a subset of all objects, they lack global information on the overall quality of all objects, as well as the global range in quality. Inherently, the only reliable information we get from experts is therefore the relative scores over the objects that they have scored each.We propose several variants of a new aggregation framework that takes this into account by computing consensual affine transformations of each expert’s scores to reach a globally balanced view. Numerical comparisons with other aggregation methods, such as rank-based methods, Kemeny-Young scoring, and a maximum likelihood estimator, show that the new method gives significantly better results in practice. Moreover, the computation is practically affordable and scales well even to larger numbers of experts and objects.

PDF Details

AAAI Conference 2017 Conference Paper

Reactive Dialectic Search Portfolios for MaxSAT

  • Carlos Ans—tegui
  • Josep Pon
  • Meinolf Sellmann
  • Kevin Tierney

Metaheuristics have been developed to provide general purpose approaches for solving hard combinatorial problems. While these frameworks often serve as the starting point for the development of problem-specific search procedures, they very rarely work efficiently in their default state. We combine the ideas of reactive search, which adjusts key parameters during search, and algorithm configuration, which fine-tunes algorithm parameters for a given set of problem instances, for the automatic compilation of a portfolio of highly reactive dialectic search heuristics for MaxSAT. Even though the dialectic search metaheuristic knows nothing more about MaxSAT than how to evaluate the cost of a truth assignment, our automatically generated solver de- fines a new state of the art for random weighted partial MaxSAT instances. Moreover, when combined with an industrial MaxSAT solver, the self-assembled reactive portfolio was able to win four out of nine gold medals at the recent 2016 MaxSAT Evaluation on random, crafted, and industrial partial and weighted-partial MaxSAT instances.

PDF Details

AAAI Conference 2014 Conference Paper

MaxSAT by Improved Instance-Specific Algorithm Configuration

  • Carlos Ansotegui
  • Yuri Malitsky
  • Meinolf Sellmann

Our objective is to boost the state-of-the-art performance in MaxSAT solving. To this end, we employ the instancespecific algorithm configurator ISAC, and improve it with the latest in portfolio technology. Experimental results on SAT show that this combination marks a significant step forward in our ability to tune algorithms instance-specifically. We then apply the new methodology to a number of MaxSAT problem domains and show that the resulting solvers consistently outperform the best existing solvers on the respective problem families. In fact, the solvers presented here were independently evaluated at the 2013 MaxSAT Evaluation where they won six of the eleven categories.

PDF Details

AAAI Conference 2014 Conference Paper

Parallel Restarted Search

  • Andre Cire
  • Serdar Kadioglu
  • Meinolf Sellmann

We consider the problem of parallelizing restarted backtrack search. With few notable exceptions, most commercial and academic constraint programming solvers do not learn no-goods during search. Depending on the branching heuristics used, this means that there are little to no side-effects between restarts, making them an excellent target for parallelization. We develop a simple technique for parallelizing restarted search deterministically and demonstrate experimentally that we can achieve near-linear speed-ups in practice.

PDF Details

IJCAI Conference 2013 Conference Paper

Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering

  • Yuri Malitsky
  • Ashish Sabharwal
  • Horst Samulowitz
  • Meinolf Sellmann

Different solution approaches for combinatorial problems often exhibit incomparable performance that depends on the concrete problem instance to be solved. Algorithm portfolios aim to combine the strengths of multiple algorithmic approaches by training a classifier that selects or schedules solvers dependent on the given instance. We devise a new classifier that selects solvers based on a cost-sensitive hierarchical clustering model. Experimental results on SAT and MaxSAT show that the new method outperforms the most effective portfolio builders to date.

PDF Details DOI

SAT Conference 2013 Conference Paper

Snappy: A Simple Algorithm Portfolio

  • Horst Samulowitz
  • Chandra Reddy
  • Ashish Sabharwal
  • Meinolf Sellmann

Abstract Algorithm portfolios try to combine the strength of individual algorithms to tackle a problem instance at hand with the most suitable technique. In the context of SAT the effectiveness of such approaches is often demonstrated at the SAT Competitions. In this paper we show that a competitive algorithm portfolio can be designed in an extremely simple fashion. In fact, the algorithm portfolio we present does not require any offline learning nor knowledge of any complex Machine Learning tools. We hope that the utter simplicity of our approach combined with its effectiveness will make algorithm portfolios accessible by a broader range of researchers including SAT and CSP solver developers.

Details

SAT Conference 2012 Conference Paper

Learning Back-Clauses in SAT - (Poster Presentation)

  • Ashish Sabharwal
  • Horst Samulowitz
  • Meinolf Sellmann

Abstract In [3], SAT conflict analysis graphs were used to learn additional clauses, which we refer to as back-clauses. These clauses may be viewed as enabling the powerful notion of “probing”: Back-clauses make inferences that would normally have to be deduced by setting a variable deliberately the other way and observing that unit propagation leads to a conflict. We show that short-cutting this process can in fact improve the performance of modern SAT solvers in theory and in practice. Based on out numerical results, it is suprising that back-clauses, proposed over a decade ago, are not yet part of standard clause-learning SAT solvers.

Details

AAAI Conference 2011 Conference Paper

A General Nogood-Learning Framework for Pseudo-Boolean Multi-Valued SAT

  • Siddhartha Jain
  • Ashish Sabharwal
  • Meinolf Sellmann

We formulate a general framework for pseudo-Boolean multivalued nogood-learning, generalizing conflict analysis performed by modern SAT solvers and its recent extension for disjunctions of multi-valued variables. This framework can handle more general constraints as well as different domain representations, such as interval domains which are commonly used for bounds consistency in constraint programming (CP), and even set variables. Our empirical evaluation shows that our solver, built upon this framework, works robustly across a number of challenging domains.

PDF Details

SAT Conference 2011 Conference Paper

Non-Model-Based Algorithm Portfolios for SAT

  • Yuri Malitsky
  • Ashish Sabharwal
  • Horst Samulowitz
  • Meinolf Sellmann

Abstract When tackling a computationally challenging combinatorial problem, one often observes that some solution approaches work well on some instances, while other approaches work better on other instances. This observation has given rise to the idea of building algorithm portfolios [5]. Leyton-Brown et al. [1], for instance, proposed to select one of the algorithms in the portfolio based on some features of the instance to be solved. This approach has been blessed with tremendous success in the past. Especially in SAT, the SATzilla portfolios [7] have performed extremely well in past SAT Competitions [6].

Details

AAAI Conference 2010 Conference Paper

Filtering Bounded Knapsack Constraints in Expected Sublinear Time

  • Yuri Malitsky
  • Meinolf Sellmann
  • Radoslaw Szymanek

We present a highly efficient incremental algorithm for propagating bounded knapsack constraints. Our algorithm is based on the sublinear filtering algorithm for binary knapsack constraints by Katriel et al. and achieves similar speed-ups of one to two orders of magnitude when compared with its lineartime counterpart. We also show that the representation of bounded knapsacks as binary knapsacks leads to ineffective filtering behavior. Experiments on standard knapsack benchmarks show that the new algorithm significantly outperforms existing methods for handling bounded knapsack constraints.

PDF Details

ECAI Conference 2010 Conference Paper

ISAC - Instance-Specific Algorithm Configuration

  • Serdar Kadioglu
  • Yuri Malitsky
  • Meinolf Sellmann
  • Kevin Tierney

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with categorical, ordinal, and/or continuous parameters, a training benchmark set of input instances for that solver, and an algorithm that computes a feature vector that characterizes any given instance. ISAC then provides high quality parameter settings for any new input instance. Experiments on a variety of different constrained optimization and constraint satisfaction solvers show that automatic algorithm configuration vastly outperforms manual tuning. Moreover, we show that instance-specific tuning frequently leads to significant speed-ups over instance-oblivious configurations.

Details

AAAI Conference 2006 Conference Paper

Disco—Novo—GoGo: Integrating Local Search and Complete Search with Restarts

  • Meinolf Sellmann
  • Carlos Ansótegui

A hybrid algorithm is devised to boost the performance of complete search on under-constrained problems. We suggest to use random variable selection in combination with restarts, augmented by a coarse-grained local search algorithm that learns favorable value heuristics over the course of several restarts. Numerical results show that this method can speedup complete search by orders of magnitude.

PDF Details

IJCAI Conference 2005 Conference Paper

Structural Symmetry Breaking

  • Meinolf Sellmann
  • Pascal Van

Symmetry breaking has been shown to be an important method to speed up the search in constraint satisfaction problems that contain symmetry. When breaking symmetry by dominance detection, a computationally efficient symmetry breaking scheme can be achieved if we can solve the dominance detection problem in polynomial time. We study the complexity of dominance detection when value and variable symmetry appear simultaneously in constraint satisfaction problems (CSPs) with single-valued variables and set-CSPs. We devise an efficient dominance detection algorithm for CSPs with single-valued variables that yields symmetry-free search trees and that is based on the abstraction to the actual, intuitive structure of a symmetric CSP.

PDF

AAAI Conference 2004 Conference Paper

The Practice of Approximated Consistency for Knapsack Constraints

  • Meinolf Sellmann

Knapsack constraints are a key modeling structure in discrete optimization and form the core of many real-life problem formulations. Only recently, a cost-based filtering algorithm for Knapsack constraints was published that is based on some previously developed approximation algorithms for the Knapsack problem. In this paper, we provide an empirical evaluation of approximated consistency for Knapsack constraints by applying it to the Market Split Problem and the Automatic Recording Problem.

PDF Details