Constraint solvers: An empirical evaluation of design decisions

2010/01/31 by Lars Kotthoff, Kotthoff, Lars · 2 citations
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Model-Driven Software Engineering Techniques #Performance (cs.PF)

paper · pdf · doi:10.48550/arxiv.1002.0134

openalex publication_date 2010/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents an evaluation of the design decisions made in four state-of-the-art constraint solvers; Choco, ECLiPSe, Gecode, and Minion. To assess the impact of design decisions, instances of the five problem classes n-Queens, Golomb Ruler, Magic Square, Social Golfers, and Balanced Incomplete Block Design are modelled and solved with each solver. The results of the experiments are not meant to give an indication of the performance of a solver, but rather investigate what influence the choice of algorithms and data structures has. The analysis of the impact of the design decisions focuses on the different ways of memory management, behaviour with increasing problem size, and specialised algorithms for specific types of variables. It also briefly considers other, less significant decisions.

Citations

• Use of Ranks in One-Criterion Variance Analysis

Cited by

• Machine learning for constraint solver design -- A case study for the alldifferent constraint
• Using machine learning to make constraint solver implementation\n decisions

Related

• Machine learning for constraint solver design -- A case study for the alldifferent constraint
• Using machine learning to make constraint solver implementation\n decisions
• Modelling Constraint Solver Architecture Design as a Constraint Problem
• An Enhanced Features Extractor for a Portfolio of Constraint Solvers
• Landscape-Aware Selection of Constraint Handling Techniquesin Multiobjective Optimisation