Exploiting the Combinatorial Structures Found in Constraint Programming Models as Multivariate Distributions

利用约束规划模型中的组合结构作为多元分布

• 批准号: RGPIN-2017-05783
• 负责人: Pesant, Gilles
• 金额: $ 3.06万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=754211
• 关键词: Exploiting; Combinatorial; Structures; Found; Constraint

Many sectors of the economy rely on our ability to solve complex combinatorial problems in order to plan, organize, or schedule their activities in the best way possible. For example: scheduling nurses in a hospital according to their individual skills and preferences so that they cover the forecast demand in patient care, and assigning patients to them so as to achieve a balanced workload; or planning the construction of a forest road network in order to harvest and then transport the lumber, designing truck routes between harvesting sites and mills, and building synchronized schedules for trucks and loaders. Among the computerized methods to accomplish this, Constraint Programming represents the problem using a formalism that exposes much of its structure. This research proposes to use that structure in a deeper way in order to improve our ability to solve combinatorial problems. Any progress towards that general goal can apply to each of these sectors and therefore can have a significant impact on our productivity and well being.

经济的许多部门依赖于我们解决复杂组合问题的能力，以便以尽可能好的方式计划、组织或安排他们的活动。例如：根据护士的个人技能和喜好安排医院护士的时间，以满足病人护理的预测需求，并为他们分配病人，以实现工作量平衡；或规划建设森林公路网，以便收获木材并随后运输，设计收获地点和磨坊之间的卡车路线，以及为卡车和装载机建立同步时间表。在实现这一点的计算机化方法中，约束编程使用一种形式主义来表示问题，这种形式主义暴露了问题的大部分结构。这项研究建议更深入地使用这种结构，以提高我们解决组合问题的能力。实现这一总目标的任何进展都可以适用于这些部门，因此可以对我们的生产力和福祉产生重大影响。