Benchmarking is an important tool for assessing the relative performance of alternative solving approaches. However, the utility of benchmarking is limited by the quantity and quality of the available problem instances. Modern constraint programming languages typically allow the specification of a class-level model that is parameterised over instance data. This separation presents an opportunity for automated approaches to generate instance data that define instances that are graded (solvable at a certain difficulty level for a solver) or can discriminate between two solving approaches. In this paper, we introduce a framework that combines these two properties to generate a large number of benchmark instances, purposely generated for effective and informative benchmarking. We use five problems that were used in the MiniZinc competition to demonstrate the usage of our framework. In addition to producing a ranking among solvers, our framework gives a broader understanding of the behaviour of each solver for the whole instance space; for example by finding subsets of instances where the solver performance significantly varies from its average performance.
翻译:基准是评估替代解决方法相对性能的一个重要工具。然而,基准的效用受到现有问题实例的数量和质量的限制。现代约束性编程语言通常允许对等级模型进行规格说明,该模型比实例数据具有参数性。这种区分为自动生成实例数据提供了一个机会,该实例数据可以界定分级(解决者在某种困难级别上可以解决)或区分两种解决方法。在本文件中,我们引入一个框架,将这两种属性结合起来,产生大量基准实例,目的是为有效和信息化的基准设定。我们使用MiniZinc竞争中使用的五个问题来展示我们框架的使用情况。除了在解决者中进行排名之外,我们的框架还使人们更加广泛地了解每个解决者在整个实例空间的行为;例如,通过找到解决者业绩与平均业绩大不相同的一系列情况。