组合优化是一类决策变量为整数的最优化问题，其要求在一个离散有限的对象集中找出最优编排、分组、次序或筛选。近年来，出现了众多利用自构建机器学习方法求解组合优化问题的研究，这类方法直接建模了输入问题实例和最终解之间的近似映射关系，并可以在测试阶段直接根据输入实例来输出解。其中，著名的模型包括：基于Transformer神经网络的Attention Model模型、基于循环神经网络的Pointer Network模型等等。尽管这些模型在求解速度、设计算法的繁杂程度等方面表现出了对于传统算法的优势，但关于其理论基础的研究还很少。在这次报告里，我将介绍我在这方面的探索：关于自构建机器学习方法求解组合优化问题的表达能力的分析。具体而言：我会介绍组合优化问题的最优解和对应的马尔可夫决策过程策略的等价性，并论证存在一个给定参数的Attention Model模型足以表示该策略。在报告的最后，我也将介绍一些后续会进行的相关研究。