A Constraint Modelling Pipeline

约束建模管道

• 批准号: EP/P015638/1
• 负责人: Ian Miguel
• 金额: $ 113.01万
• 依托单位: University of St Andrews
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FP015638%2F1
• 关键词: Constraint; Modelling; Pipeline

In numerous contexts today we are faced with making decisions of increasing size and complexity, where many different considerations interlock in complex ways. Consider a staff rostering problem to assign staff to shifts while respecting required shift patterns and staffing levels, physical and staff resources, and staff working preferences. The decision-making process is often further complicated by the need also to optimise an objective, such as to maximise profit or to minimise waste.It is natural to characterise such problems as a set of decision variables, each representing a choice that must be made in order to solve the problem at hand (e.g. which staff member is on duty for the Friday night shift), and a set of constraints describing allowed combinations of variable assignments (e.g. a staff member cannot be assigned to a day shift immediately following a night shift). A solution is an assignment of a value to each variable satisfying all constraints.Many decision-making and optimisation formalisms take this general form. In all of these formalisms the model of the problem is crucial to the efficiency with which it can be solved. A model in this sense is the set of decision variables and constraints chosen to represent a given problem. There are typically many possible models and formulating an effective model is notoriously difficult. Therefore automating modelling is a key challenge.Over the last decade, in the context of Constraint Programming we have taken a novel approach to addressing this challenge. The user writes a problem specification in the abstract constraint specification language 'Essence', capturing the structure of the problem above the level of abstraction at which modelling decisions are made. Our modelling pipeline, on which our proposed research is based, automatically generates a model from this specification. This removes the need for user constraint modelling expertise, and also preserves the structure of the specified problem, allowing the system easily to explore alternative models and to exploit properties such as symmetry.Our pipeline generates constraint models equivalent in quality to those of a competent human constraint programmer, and so represents a significant milestone towards fully automated modelling. Important challenges do, however, remain. The first is to generate models of the quality that human experts are capable. Given the inherent difficulty of these problems, and the importance of the model in mitigating that difficulty, raising the quality of the generated models is crucial. The second is to expand the range of output models beyond the constraint programming formalism.The substantial challenge we address in this proposal is to overcome these two limitations to produce a powerful, general automated modelling and solving system unique in targeting a range of solving formalisms from a single abstract constraint specification. Our existing pipeline is ideal for extension to other formalisms.The impact of this change will be substantial: combinatorial search problems are ubiquitous across the public and private sectors, and academia. We will deliver better solutions to these problems more rapidly, increasing efficiency and reducing cost.

在今天的许多情况下，我们面临着做出越来越大和越来越复杂的决定，其中许多不同的考虑以复杂的方式相互交织在一起。考虑一个员工排班问题，将员工分配到班次，同时尊重所需的班次模式和人员配备水平、物力和人力资源以及员工的工作偏好。决策过程往往因为还需要优化一个目标而变得更加复杂，例如利润最大化或浪费最小化。很自然地，将这样的问题描述为一组决策变量，每个决策变量代表为了解决手头的问题而必须做出的选择(例如，哪个工作人员在周五晚班值班)，以及一组描述允许的变量分配组合的约束(例如，工作人员不能在上夜班后立即被分配到白班)。解是对满足所有约束的每个变量的赋值。许多决策和优化形式都采用这种一般形式。在所有这些形式主义中，问题的模型对解决问题的效率至关重要。从这个意义上讲，模型是为表示给定问题而选择的决策变量和约束的集合。通常有许多可能的模型，而制定一个有效的模型是出了名的困难。因此，自动化建模是一个关键的挑战。在过去的十年中，在约束编程的背景下，我们采取了一种新的方法来解决这一挑战。用户用抽象的约束规范语言“Essence”编写问题规范，捕获抽象级别之上的问题结构，在该抽象级别上做出建模决策。我们的建模管道是我们建议的研究的基础，它自动从该规范生成模型。这消除了对用户约束建模专业知识的需要，还保留了指定问题的结构，允许系统轻松地探索替代模型并利用诸如对称性等属性。我们的流水线生成的约束模型在质量上与称职的人类约束程序员的约束模型相同，因此代表着迈向完全自动化建模的一个重要里程碑。然而，重要的挑战依然存在。第一个是生成具有人类专家能力的模型。考虑到这些问题的固有困难，以及模型在缓解该困难方面的重要性，提高生成的模型的质量是至关重要的。第二个目标是扩展输出模型的范围，使其超越约束编程的形式化。我们在这个方案中解决的主要挑战是克服这两个限制，以产生一个强大的、通用的自动化建模和求解系统，该系统独特地针对来自单一抽象约束规范的一系列求解形式化。我们现有的管道非常适合推广到其他形式主义。这一变化的影响将是巨大的：组合搜索问题在公共和私营部门以及学术界无处不在。我们将更快地为这些问题提供更好的解决方案，提高效率，降低成本。

项目成果

Modelling Langford's Problem: a viewpoint for search

兰福德问题建模：搜索的观点

• 发表时间: 2018
• 作者: Akgun O

Endocrine Requirements for Oocyte Maturation Following hCG, GnRH Agonist, and Kisspeptin During IVF Treatment.

• DOI: 10.3389/fendo.2020.537205
• 发表时间: 2020
• 期刊: Frontiers in endocrinology
• 影响因子: 5.2
• 作者: Abbara A;Hunjan T;Ho VNA;Clarke SA;Comninos AN;Izzi-Engbeaya C;Ho TM;Trew GH;Hramyka A;Kelsey T;Salim R;Humaidan P;Vuong LN;Dhillo WS
• 通讯作者: Dhillo WS

A Framework for Constraint Based Local Search using Essence

使用 Essence 的基于约束的本地搜索框架

• DOI: 10.24963/ijcai.2018/173
• 发表时间: 2018
• 作者: Akgün Ö

Conjure: Automatic Generation of Constraint Models from Problem Specifications

• DOI: 10.1016/j.artint.2022.103751
• 发表时间: 2022-06
• 期刊: Artif. Intell.
• 作者: Özgür Akgün;Alan M. Frisch;Ian P. Gent;Christopher Jefferson;Ian Miguel;Peter William Nightingale

Conjure: Automatic Generation of Constraint Models from Problem Specifications (Extended Abstract)

Conjure：根据问题规范自动生成约束模型（扩展摘要）

• DOI: 10.24963/ijcai.2023/765
• 发表时间: 2023
• 作者: Akgün Ö