【干货书】组合优化研究进展:旅行商的线性规划公式和其他困难的组合优化问题,154页

组合优化(CO)是应用数学、决策科学和计算机科学等领域的一个研究课题，旨在通过非穷尽搜索找到最优解。CO涉及计算复杂性理论、算法理论等学科，在运筹学/管理科学、人工智能、机器学习、软件工程等领域具有重要应用。

组合优化研究进展为将困难的组合优化问题表述为多项式规模的线性规划提供了一种通用的框架。尽管该框架是基于“旅行商问题”(TSP)开发的，但它可以直接将许多著名的NP完全约束条件问题(而不需要将它们归约为其他约束条件)表述为线性规划，并对其他三个问题(例如“顶点着色问题”(VCP))进行了同样的演示。该工作还证明了多项式时间复杂度类P和非确定多项式时间复杂度类NP的等价性，为“扩展公式”的理论和应用做出了贡献。

总的来说，组合优化的进展提供了新的建模和解决问题的视角，这将对从事路由、调度和排序决策的专业人员、研究生和研究人员有用，特别是在处理一般的计算理论。

组合优化(CO)是应用数学、决策科学和计算机科学等领域的一个研究课题，旨在通过非穷尽搜索找到最优解。CO涉及计算复杂性理论、算法理论等学科，在运筹学/管理科学、人工智能、机器学习、软件工程等领域具有重要应用。

组合优化研究进展为将困难的组合优化问题表述为多项式规模的线性规划提供了一种通用的框架。尽管该框架是基于“旅行商问题”(TSP)开发的，但它可以直接将许多著名的np完全约束条件问题(而不需要将它们归约为其他约束条件)表述为线性规划，并对其他三个问题(例如“顶点着色问题”(VCP))进行了同样的演示。该工作还证明了多项式时间复杂度类P和非确定多项式时间复杂度类NP的等价性，为“扩展公式”的理论和应用做出了贡献。

总的来说，组合优化的进展提供了新的建模和解决问题的视角，这将对从事路由、调度和排序决策的专业人员、研究生和研究人员有用，特别是在处理一般的计算理论。

读者:专业人士、研究生和研究人员，特别是涉及路由、调度和排序决策，或处理一般的计算理论。

主要特点:

本书提供了一个新的证明，证明了"P"和"NP"复杂性类的相等性。

虽然我们的方法是使用TSP框架开发的，但它对np完全类中的其他问题有自然的模拟，从而为许多组合优化问题(COPs)提供了一个统一的框架。

本书对扩展公式(EFs)的理论和应用做出了贡献，通过将概念退化的情况与定义良好/有意义的情况分开来细化EFs的概念。它将冗余约束和变量的添加(为了建立EF关系)与冗余约束和变量的添加无关紧要的情况分开

专知便捷查看

便捷下载，请关注专知公众号（点击上方蓝色专知关注）

• 后台回复“C154” 就可以获取《【干货书】组合优化研究进展:旅行商的线性规划公式和其他困难的组合优化问题，154页pdf》专知下载链接