Improved methods and applications of Mixed-Integer Programming

混合整数规划的改进方法及应用

• 批准号: RGPIN-2014-05623
• 负责人: Fukasawa, Ricardo
• 金额: $ 1.6万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=567285
• 关键词: Improved; methods; applications; Mixed; Integer

Mixed-Integer Programming (MIP) is an extremely important tool in quantitative decision making within modern corporations. Its applications include air transportation, telecommunications, logistics and manufacturing. This research program will investigate key issues to improve the performance of MIP tools and increase the spectrum of their applications. The proposed program will train 3 PhD students, 2 MMath students and 1 Postdoctoral fellow. These HQPs will gain skills and knowledge in optimization theory and in the implementation of optimization algorithms. These valuable skills are in high demand in academia and in industry, thus giving the HQP a great range of possibilities for successful careers. The first part of my project will focus on improving the methodology and theory of cutting planes for MIPs. Cutting planes are one of the most important tools in any software for MIPs, having received significant attention by the research community. Nonetheless, only recently has there been a shift in focus from cutting planes derived from single-constraint relaxations to multiple-constraint relaxations. The aim of this program will be to investigate new classes of cuts that fall into this category, by exploiting some of my recent results that developed a promising new framework for such cuts. My objective is to gain a deeper understanding of the theory of this new framework and its connections to other existing frameworks and then investigate its potential and limitations. The second part of the project will focus on developing state-of-the-art MIP-based software for solving routing-type problems. These kinds of problems are an important class of combinatorial optimization problems which have immediate applications in Logistics. Besides developing new cutting-planes for these problems, we also will address other issues that arise in this particular application including how to design a code that is accurate in spite of the inaccuracies intrinsic to floating point arithmetic. Furthermore, I will investigate convergency issues and how to design better formulations. Finally, I will consider the impact on these algorithms when uncertain data is considered. The theory and algorithms developed in this proposal have the potential to impact commercial MIP solvers, which by consequence can have a significant impact in all of its abovementioned application areas. In addition, the specific techniques developed for routing type problems can have a great impact in the Logistics sector which is a very important sector in any industry that relies on delivering goods/equipment/materials to its consumers. Therefore, the potential benefits to Canada are widespread.

混合整数规划（MIP）是现代企业定量决策的重要工具。它的应用包括航空运输、电信、物流和制造业。该研究计划将研究提高MIP工具性能和增加其应用范围的关键问题。拟培养博士研究生3名，硕士研究生2名，博士后1名。这些hqp将获得优化理论和优化算法实现方面的技能和知识。这些宝贵的技能在学术界和工业界都有很高的需求，因此为HQP的成功职业生涯提供了很大的可能性。我的项目的第一部分将专注于改进MIPs切割平面的方法和理论。切割平面是所有MIPs软件中最重要的工具之一，受到了研究界的极大关注。尽管如此，直到最近才将焦点从单约束松弛导出的切割平面转移到多约束松弛。这个项目的目的是通过利用我最近的一些研究结果，研究属于这一类别的新削减类别，这些研究结果为这类削减制定了一个有希望的新框架。我的目标是更深入地了解这个新框架的理论及其与其他现有框架的联系，然后研究它的潜力和局限性。该项目的第二部分将侧重于开发最先进的基于mip的软件，以解决路由类型的问题。这类问题是一类重要的组合优化问题，在物流领域有直接的应用。除了为这些问题开发新的切割平面外，我们还将解决在这个特定应用中出现的其他问题，包括如何设计一个精确的代码，尽管浮点运算固有的不准确性。此外，我将研究收敛问题以及如何设计更好的公式。最后，我将考虑在考虑不确定数据时对这些算法的影响。本提案中开发的理论和算法有可能影响商用MIP求解器，从而在所有上述应用领域产生重大影响。此外，为路线类型问题开发的特定技术可以对物流部门产生重大影响，物流部门是任何依赖于向消费者交付货物/设备/材料的行业中非常重要的部门。因此，对加拿大的潜在好处是广泛的。