金年会jinnianhuicom学术报告
A polyhedral study of frustration index problems
陈伟坤
（北京理工大学）
报告时间：2025年11月20日 星期四 下午14：30-15：30
报告地点：沙河校区E806
报告摘要：In signed graphs, each edge is labeled as either positive or negative, capturing the polarity of a relationship. A signed (sub)graph is balanced if the vertices can be divided into two subsets such that negative edges exist only between the two subsets. In this talk, we consider the frustration index problem (FIP) which asks to find the minimum number of edges whose removal makes the resultant subgraph balanced. We present a new integer programming (IP) formulation for the FIP and provide an in-depth investigation of the structure of the underlying polytope. In particular, we show that any facet of the related polytopes, induced by subgraphs of the signed graph, can also define a facet of the underlying polytope of the IP formulation. As an application, we consider the polytopes induced by the structured subgraphs—unbalanced cycles—and develop a class of strong facet-defining inequalities. Moreover, we show that the proposed unbalanced cycle inequalities can be separated using an exact polynomial-time algorithm. Finally, computational results on a testbed of 1513 FIP instances demonstrate the strength of the proposed unbalanced cycle inequalities in substantially strengthening the linear programming relaxation of the IP formulation and improving the overall performance of a state-of-the-art IP solver.
报告人简介：陈伟坤，北京理工大学数学与统计学院特别副研究员 ，硕士生导师。2019年在中国科学院数学与系统科学研究院获得博士学位。主要研究兴趣是整数规划理论、算法与软件及其在无线通信、物流等领域中的应用。现为中国运筹学会算法与软件分会常务理事，中国运筹学会数学规划分会青年理事，在SIAM J. Optim., Eur. J. Oper. Res., ACM Trans. Math. Softw., IEEE J. Sel. Areas Commun., IEEE Trans. Signal Process., IEEE Trans. Netw. Service Manag.等杂志发表数篇学术论文。2018年获得中国运筹学会“科学技术奖运筹应用奖”，2020年获得中国科学院“中国科学院优秀博士学位论文”。担任《Journal of Global Optimization》客座编委，《运筹学学报（中英文）》编委。主持和参与国家自然科学青年、面上基金。
邀请人：谢家新
