报告人学术简介
 陈伟坤，北京理工大学数学与统计学院长聘副教授，博士生导师。2019年在中国科学院数学与系统科学研究院获得博士学位。主要研究兴趣是整数规划理论、算法与软件及其在无线通信、物流等领域中的应用。现为中国运筹学会算法与软件分会常务理事，中国运筹学会数学规划分会青年理事，在SIAM J. Optim., Math. Program. Comput., INFORMS J. Comput., Eur. J. Oper. Res., ACM Trans. Math. Softw., IEEE JSAC, TSP, TNSM等杂志发表数篇学术论文。曾获得中国运筹学会“科学技术奖青年科技奖”、“科学技术奖运筹应用奖”，中国科学院“中国科学院优秀博士学位论文”。担任《Journal of Global Optimization》客座编委，《运筹学学报（中英文）》编委。主持和参与国家自然科学青年、面上基金。

报告内容
 In this talk, we consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a priori tour, the expected recourse function—the objective function of the PTSP—can be evaluated using efficient polynomial-time procedures under certain distributions of the random customer presence. However, a tractable convex representation exploiting the structure of the a priori tour and recourse policy for the expected recourse function was unknown until now, despite its importance in developing sophisticated exact algorithms for the PTSP and related problems. In this paper, we fill this research gap by deriving a new tractable convex piecewise-affine representation for the expected recourse function in the PTSP with an arbitrary distribution of the random customer presence. Building upon this convex representation, we develop new mixed integer linear programming formulations for the PTSP, and design an exact algorithm in which the exponentially many linear inequalities are separated dynamically. Extensive computational results on benchmark instances with both independent and correlated customer presences demonstrate that, thanks to the strong linear programming relaxation bound, the proposed exact algorithm significantly outperforms the state-of-the-art integer L-shaped method. Using the proposed algorithm, PTSP instances with up to 300 vertices can now be solved to optimality or near-optimality within a two-hour time limit. Moreover, when run under a 600-second time budget, it can provide much better solutions than a leading heuristic algorithm in the literature.