Solving rich and integrated decision problems with hybrid operations research and constraint programming approaches

使用混合运筹学和约束规划方法解决丰富的综合决策问题

• 批准号: 288209-2009
• 负责人: Rousseau, LouisMartin
• 金额: $ 1.46万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=525731
• 关键词: Solving; rich; integrated; decision; problems

In recent decades, decision support systems and optimization software have generated huge savings while significantly increasing the productivity of organizations in Canada and around the world. Commercial software packages based on Operations Research (OR) technologies have been able to produce near optimal solutions to many of the difficult problems faced by modern industries. Airline demand forecasting, fleet sizing, flight scheduling, crew scheduling and rostering, and aircraft routing are examples of some of the areas which have benefited. Typically, each of the these problems has been addressed separately and in sequence, with outputs from the first problems solved serving as inputs to those coming later. This sequential and sometimes simplified approach allowed researchers to understand the individual problems and develop effective methodologies to address them, but the process can be somewhat myopic since optimal global decision-making is not specifically addressed. Even though the integration of all levels of decisions in order to model the complete problem is in most cases impossible or impractical, progress toward that end should in many cases yield additional cost savings and gains in productivity. The main obstacle to realising the potential additional benefits of integrated decision making lies in the structural differences which exist among the models used to address different parts of the overall problem. Algorithms developed to optimize parts of the global problem cannot simply be merged together. The proposed research program thus aims at making significant progress toward solving rich integrated decision problems by proposing new methodologies based on hybridizing traditional operations research approaches and Constraint Programming (CP) techniques. CP concentrate on the feasibility of a solution; logical inference and filtering techniques are used to discard quickly those partial solutions which can be shown to be infeasible, even though the majority of the variables are still unassigned. The combination of CP's modeling flexibility and its emphasis on feasibility together with OR's optimization efficiency offers the promise of decision tools that are both powerful and versatile.

近几十年来，决策支持系统和优化软件已经产生了巨大的节省，同时显着提高了加拿大和世界各地组织的生产力。基于运筹学（OR）技术的商业软件包已经能够为现代工业面临的许多难题提供接近最佳的解决方案。航空公司需求预测、机队规模、航班调度、机组人员调度和名册编制以及飞机航线安排等都是受益的领域。通常情况下，这些问题中的每一个都是单独和顺序解决的，第一个问题解决后的输出作为后面问题的输入。这种连续的，有时是简化的方法使研究人员能够理解个别问题，并制定有效的方法来解决这些问题，但这个过程可能有点短视，因为最佳的全球决策没有得到具体解决。尽管在大多数情况下，集成所有级别的决策以模拟完整的问题是不可能的或不切实际的，但在许多情况下，朝着这一目标的进展应该产生额外的成本节约和生产力的提高。实现综合决策的潜在额外好处的主要障碍在于用于解决整体问题的不同部分的模型之间存在的结构差异。为优化全局问题的部分而开发的算法不能简单地合并在一起。因此，拟议的研究计划的目的是在解决丰富的综合决策问题，提出新的方法的基础上杂交传统的运筹学方法和约束编程（CP）技术取得重大进展。CP集中在解决方案的可行性;逻辑推理和过滤技术被用来快速丢弃那些部分解决方案，可以被证明是不可行的，即使大多数的变量仍然没有分配。CP的建模灵活性及其对可行性的强调与OR的优化效率相结合，提供了强大而通用的决策工具。