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

点击翻译按钮获取中文摘要

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.