Improved methods and applications of Mixed-Integer Programming

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

• 批准号: RGPIN-2014-05623
• 负责人: Fukasawa, Ricardo
• 金额: $ 1.6万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=678724
• 关键词: 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工具的性能，并增加其应用范围。** 拟议的计划将培养3名博士生，2名MMath学生和1名博士后研究员。这些HQP将获得优化理论和优化算法实施方面的技能和知识。这些宝贵的技能在学术界和工业界都有很高的需求，从而为HQP提供了成功职业的各种可能性。我的项目的第一部分将重点关注改进MIP切割平面的方法和理论。切割平面是MIP软件中最重要的工具之一，受到了研究界的极大关注。 尽管如此，直到最近才有一个转移的重点，从切割平面来自单约束松弛到多约束松弛。** 本计划的目的是通过利用我最近的一些结果来研究属于这一类的新削减类别，这些结果为此类削减开发了一个有前途的新框架。我的目标是更深入地理解这个新框架的理论及其与其他现有框架的联系，然后研究它的潜力和局限性。该项目的第二部分将侧重于开发最先进的基于MIP的软件，以解决路由类型的问题。这类问题是一类重要的组合优化问题，在物流中有着直接的应用。除了为这些问题开发新的切割平面外，我们还将解决这个特定应用中出现的其他问题，包括如何设计一个精确的代码，尽管浮点运算固有的不准确性。此外，我将研究收敛问题以及如何设计更好的公式。最后，我将考虑这些算法的影响时，考虑不确定的数据。** 本提案中开发的理论和算法有可能影响商业MIP求解器，因此可以在所有上述应用领域产生重大影响。此外，为路由类型问题开发的特定技术可以在物流部门产生巨大影响，物流部门是依赖于将货物/设备/材料交付给消费者的任何行业中非常重要的部门。因此，加拿大的潜在利益是广泛的。