Representations in constraint programming
Representations in constraint programming
复制标题
约束规划中的表示
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Christopher Jefferson
中科院分区：
文献类型：
--
作者：
Christopher Jefferson
约束编程是一种功能强大的通用工具，用于解决大量的组合和现实世界的问题。CP求解器联合收割机许多强大的通用算法，当它们一起使用时，通常可以解决其他框架中的问题。阻碍约束编程被更广泛的受众采用的主要实际问题是，将问题从高级描述转换为适合约束求解器的格式，称为建模，与其说是一门科学，不如说是一门艺术。因此，建模只能由专家实践者很好地完成。通常，对未经培训的用户来说可能毫无用处的小变化可能会导致解决问题所需时间的大幅减少或增加。第一，也可以说是最重要的，在建模问题时的决定是选择将要使用的变量类型。大多数约束系统只提供少量的变量类型;通常是整数、矩阵和可能的集合。用户必须将问题的高级抽象类型转换为这些基本类型，然后将约束映射到这些类型上。所有这些都必须仅使用求解器提供的约束集来完成。这篇论文提供了第一个完整的，通用的方法来比较一个特定变量的所有表示。在这样做的过程中，它提供了一些关键的见解，提高了自动化建模过程的最新技术水平。在CP中，选择高级变量的“最佳”表示（如时间表或分区）是非常困难的;最佳的定义有许多可能相互冲突。一般来说，保持使用的变量和约束的数量较小将允许求解器更快地工作。设计表示，以便可以使用全局约束的传播器也可以提高性能。通常不同的表征具有不同的强度，
Constraint programming is a powerful and general purpose tool which is used to solve a large range of combinatorial and real-world problems. CP solvers combine a number of powerful and generic algorithms, which when used together can often solve problems infeasable in other frameworks. The major practical issue which stalls adoption of constraint programming by a wider audience is that transforming a problem from a high-level description into a format suitable for a constraint solver, called modelling, is more of an art than a science. Hence, modelling can only be accomplished well by expert practitioners. Often small changes, which to the untrained user may appear useless, can lead to huge reductions or increases in the time taken to solve a problem. The first, and arguably most important, decision when modelling a problem is to choose the type of variables which will be used. Most constraint systems provide only a small number of variable types; usually integers, matrices and possibly sets. Users must transform the high-level abstract types from their problem into these basic types, and then map the constraints down onto these types. All this must be accomplished using only the set of constraints provided by their solver. This thesis provides the first complete, generic method for comparing all the representations of a particular variable. In doing so it provides a number of key insights which improve the state of the art in automating the modelling process. Choosing the “best” representation of a high-level variable, such as a timetable or partition, in CP is extremely difficult; with many possible conflicting definitions of best. In general keeping the number of variables and constraints used small will allow the solver to work faster. Designing the representation so that propagators for global constraints can be used can also improve performance. Often different representations have different strengths,