学术报告一

报告题目: Efficient presolving methods for solving maximal covering and partial set covering location problems

报告人：陈伟坤（北京理工大学副教授）

报告时间：2021年7月25日 9：00—11：00

报告地点：腾讯会议 (ID: 749 299 787)

主办单位: 数学与统计学院

摘要:The maximal covering location problem (MCLP) and the partial set covering location problem (PSCLP) are two fundamental problems in facility location and have widespread applications in practice. The MCLP determines a subset of facilities to open that maximizes the demand of covered customers subject to a budget constraint on the cost of open facilities; and the PSCLP aims to minimize the cost of open facilities while requiring that a certain amount of customer demand is covered. Both problems can be modeled as mixed integer programming (MIP) formulations. However, because of the intrinsic NP-hardness nature, it is a great challenge to solve them to optimality by standard MIP solvers, especially for large-scale cases. In this talk, by exploiting the special problem structures of the two problems, we propose five customized presolving methods for enhancing the capability of employing standard MIP solvers in solving the two problems. The proposed presolving methods are designed to reduce the sizes of the problem formulation and the branch-and-bound search tree. For one of the presolving methods, an analysis is given on problems defined on a plane under the Euclidean or rectilinear distance measurement. Specifically, we prove that the number of customers in the reduced problems is bounded above by a quadratic polynomial of the number of facilities. This is particularly advantageous for solving problems with an extremely huge number of customers but a relatively small number of facilities. By extensive numerical experiments, the proposed presolving methods are demonstrated to be effective in accelerating the solution process of solving the MCLP and PSCLP. Moreover, they enable us to solve problems with billions of customers, which is at least one order of magnitude larger than those that can be tackled by previous approaches.

报告人简介: 陈伟坤，北京理工大学数学与统计学院特别副研究员，硕士生导师。2019年在中国科学院数学与系统科学研究院获得博士学位，师从戴彧虹研究员。主要研究兴趣是整数规划理论、算法与软件及其在无线通信与社交网络等领域中的应用。现为北京运筹学会理事，在SIAM Journal on Optimization，IEEE Journal on Selected Areas in Communications，IEEE Transactions on Network and Service Management，Journal of Global Optimization，EURO Journal on Computational Optimization等杂志发表数篇学术论文。2018年获得中国运筹学会”科学技术奖运筹应用奖”，2020年获得中国科学院“中国科学院优秀博士学位论文”。

学术报告二

报告题目: CMIP——混合整数规划求解器

报告人：陈亮（中国科学院数学与系统科学研究院 助理研究员）

报告时间：2021年7月25日下午15：00—17：00

报告地点：腾讯会议 (ID: 749 299 787)

主办单位: 数学与统计学院

摘要: 混合整数规划在经济、供应链、通信、制造、航空以及国防等领域有广泛的应用，发展快速有效的混合整数规划求解器有利于解决我国工业应用中的重要混合整数规划问题。CMIP求解器是中科院数学院自主研发的国产混合整数规划求解器。它以分支定界——割平面为基本算法框架，包含了分支策略、节点选择策略、预处理方法、割平面方法、启发式方法五大主要模块，融合了CMIP团队在预处理、割平面等方面的最新研究成果。本次报告主要介绍CMIP求解器，并以最大覆盖选址和航班调度等实际应用问题为例介绍其性能效果。

报告人简介: 陈亮，中国科学院数学与系统科学研究院博士后、助理研究员，2020年博士毕业于中国科学院数学与系统科学研究院，师从戴彧虹研究员，研究方向是混合整数规划，是国产混合整数规划求解器 CMIP 开发骨干成员之一，主要参与其预处理方法、割平面方法、启发式方法等各模块的开发，参与华为、阿里、电科院等多个合作项目。