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

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

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.