德克萨斯理工大学计算机学院陈林教授学术报告

报告主题: 分块结构整数规划的算法及其在优化问题中的应用

报告时间：2020年12月22日（周二）9:00-12:00

报告地点：腾讯会议(会议ID：495 948 934)

报告摘要：本次报告，首先总结约束矩阵具有分块结构的一类整数规划问题最近在算法上的进展。一般地，如果变量的个数只有常数多个，那么整数规划是多项式时间可解的；如果变量的个数是输入的一部分，那么整数规划是NP困难的。但是，如果整数规划的约束矩阵具有特殊的结构，那么仍然有可能设计出运行时间为变量个数的多项式的算法。分块结构整数规划就是这样一类的整数规划。尽管约束矩阵被限制必须具有分块的结构，该类型的整数规划依然是一个很强的数学工具，能用于建模包括调度(scheduling)，社会选择(computational social choice)，高维运输(high dimensional transportation)等问题在内的一系列优化问题。此次报告，将简要介绍分块结构整数规划以及它的各种应用，然后探讨近几年包括报告人在内的一系列研究者们对于该问题算法上的研究，最后将讨论该方向的一些重要的未解决问题。

 

专家介绍：

陈林，博士，德克萨斯理工大学计算机学院教授。 2013年在浙江大学取得博士学位，之后在德国柏林工业大学，慕尼黑工业大学先后从事博士后研究，后在休斯顿大学从事研究教授。目前主要研究算法和复杂性，及其在人工智能，组合优化等方面的应用。研究成果发表在SODA，SPAA，AAAI，IJCAI等顶级会议，以及SIAM journal on computing, ACM transactions on algorithms，mathematical programming等顶级期刊上。目前主持美国自然科学基金NSF 1756014，重点研究近似算法与参数算法。

 

 

 

信息管理学院

科研处