Improved methods and applications of Mixed-Integer Programming

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

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.