编辑推荐：
本推荐将介绍一项在离散优化领域的重要工作。为解决旅行商问题（TSP）中子巡回消除多面体P(G)的最小描述问题，研究人员Brahim Chaourar针对任意图（而非仅限于完全图Kn）的子巡回多面体的面（Facets）进行了深入研究。该研究成功推广了Maurras (1975) 以及 Gr?tschel 和 Padberg (1979b) 的经典结果，给出了P(G)的紧凑描述，并定义了“锁定子图”（locked subgraph）这一关键概念。这一成果对深化TSP的多面体方法理解、优化算法设计具有重要意义。
旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域中最著名、被研究得最深入的问题之一。它的身影不仅出现在理论研究中，更在实际生活的诸多场景中随处可见，例如物流配送、电路板钻孔、基因组测序等。这个问题的核心，是寻找一个访问所有城市恰好一次并返回起点的最短环路。尽管问题描述简单，但它却是计算机科学中典型的NP难问题，这意味着寻找其精确最优解的计算量随着城市数量的增加会爆炸式增长。
为了攻克这一难题，研究者们发展出多种策略，其中“多面体方法”（Polyhedral Approach）尤为引人注目。这种方法试图从几何角度来理解问题：将TSP的所有可行解（即哈密顿回路，Hamiltonian circuit）映射为高维空间中的点，然后研究这些点所构成的凸包（convex hull），即旅行商多面体TSP(G)。如果能够找到描述这个多面体的完整不等式系统，就可以利用线性规划等方法高效地求解TSP。然而，直接描述TSP(G)极为困难，因此研究者通常会先研究一个更宽松、更容易描述的“松弛”多面体，即子巡回消除多面体（subtour elimination polytope），记作P(G)。P(G)由非负性、度数为2（即每个顶点关联的边变量之和为2）以及子巡回消除约束（要求任意非空真顶点子集U的割边变量之和至少为2）共同定义。显然，TSP(G)包含于P(G)中，因此P(G)的最优值可以为TSP提供一个有效的下界。
那么，一个自然的问题是：描述P(G)的这一系列约束中，哪些是真正“必不可少”的，即定义其“面”（facet）的？Maurras (1975) 以及 Gr?tschel 和 Padberg (1979b) 独立地解决了当图G是完全图Kn时的情况，他们证明了子巡回消除约束x(δ(U)) ≥ 2 是TSP(Kn)的一个面，当且仅当 2 ≤ |U| ≤ n-2。这个结果为完全图上的TSP研究奠定了坚实的多面体理论基础。但是，现实世界中的网络往往不是完全连接的，例如交通网、通信网通常都是稀疏的任意图。那么，对于任意图G，P(G)的面又该如何刻画？其最小描述是什么？这正是Brahim Chaourar在本研究中致力于回答的核心问题。
为了解答上述问题，作者对任意无向图G=(V, E)的子巡回多面体P(G)进行了系统的分析。研究首先回顾了Pashkovich (2012) 的工作，后者证明了P(G)可以用一组“更精简”的子巡回消除约束来描述，即只要求那些使得诱导子图G(U)和G(V\U)都连通的顶点子集U所对应的约束。作者将满足此条件且2 ≤ |U| ≤ |V|-2 的诱导子图G(U)称为Pashkovich子图。然而，并非所有Pashkovich子图对应的约束在描述P(G)时都是必不可少的。作者通过引入“锁定子图”（locked subgraph）这一核心概念，对Pashkovich的结果进行了进一步的提炼和深化。研究表明，P(G)实际上可以由度约束和仅针对“锁定子图”的非负性约束和子巡回消除约束来描述，并且这一描述是“最小”的，即其中任何一个约束都不能被其他约束线性表出，从而构成了P(G)的一个极小不等式系统。这项研究工作发表在期刊《Discrete Optimization》上，它不仅推广了经典结果，也为在更一般的图结构上应用TSP的多面体方法提供了新的工具和洞察。
本研究主要运用了组合优化与多面体理论中的关键技术方法。核心方法是多面体刻画与面分析，即通过分析子巡回消除多面体P(G)的几何结构（维度、面）来寻找其最小不等式描述。研究利用了图论工具，特别是关于图的连通性（2-连通）和诱导子图的性质。论证过程大量依赖线性代数技巧，例如分析由度约束方程所构成的系数矩阵的秩，以确定多面体的维度。证明策略上，作者采用了归纳法和反证法，并通过构造满足特定等式约束的向量来证明某些不等式是冗余的或非冗余的。整个研究建立在对前人工作（Maurras, Gr?tschel与Padberg, Pashkovich）结果的深入理解和推广之上。
研究结果
1. 引言与背景
文章首先阐述了旅行商问题（TSP）及其多面体方法的重要性，明确了子巡回消除多面体P(G)作为TSP(G)松弛的定义。它回顾了完全图Kn上的经典结论（Maurras-Gr?tschel-Padberg定理），并引出了本文的核心目标：将这一结论推广到任意图G，寻求P(G)的一个最小描述。
2. 主要定义与“锁定”概念
本部分给出了研究所需的图论和多面体基本记号。关键性地，在Pashkovich子图（即G(U)和G(V\U)连通，且2 ≤ |U| ≤ |V|-2）的基础上，作者定义了“锁定子图”：一个Pashkovich子图G(U)被称为锁定的，如果G(U)和G(V\U)中至少有一个是2-连通的。这一概念是区分冗余与非冗余约束的核心。
3. 主要定理与推论
定理4.8 是本文的核心结论之一。它指出，设G是一个无向图，满足|V(G)| ≥ 4且G是2-连通的。那么，子巡回消除约束x(δ(U)) ≥ 2 定义P(G)的一个面，当且仅当诱导子图G(U)是锁定的。
推论4.10 基于定理4.8，给出了P(G)的一个更紧凑的描述：(i) P(G)由非负约束x(e) ≥ 0、度约束x(δ(v)) = 2 以及针对所有锁定子图U的子巡回消除约束x(δ(U)) ≥ 2 所描述。(ii) 此外，P(G)也可以仅由度约束和针对锁定子图U的约束（包括非负约束和子巡回消除约束）来描述。这比Pashkovich的描述（需要所有Pashkovich子图）更为精简。
引理3.2 通过一个具体的图例（由两个三角形通过一条边连接而成）证明，存在是Pashkovich子图但不是锁定子图的情况，这意味着在Pashkovich的描述中，某些约束确实是冗余的。
4. 结论与意义
推论5.7 是研究的最终成果，它确立了P(G)的一个最小不等式描述：当|V(G)| ≥ 4且G是2-连通时，P(G)的一个最小线性不等式描述由以下组成：(a) 对于所有边e ∈ E(G)，约束x(e) ≥ 0，但仅限于那些边e使得G[V(G) \ {e}]（即删除边e后的图）不再是2-连通的边。(b) 对于所有锁定的顶点子集U ? V(G)，子巡回消除约束x(δ(U)) ≥ 2。这个描述是“最小”的，意味着其中任何一个不等式都不能被其他不等式的非负组合所导出。
研究结论与讨论
本研究的核心结论是成功刻画了任意2-连通无向图G的子巡回消除多面体P(G)的面，并给出了其最小线性描述。具体而言，研究证明了子巡回消除约束x(δ(U)) ≥ 2 是P(G)的一个面，当且仅当对应的诱导子图G(U)是“锁定”的，即它是Pashkovich子图且G(U)与G(V\U)中至少一个是2-连通的。基于此，作者推导出P(G)可以由度约束、针对部分边的非负约束以及仅针对锁定子图的子巡回消除约束来完整描述，并且这一描述是极小的。
这项研究的意义重大。首先，它是对经典的Maurras-Gr?tschel-Padberg定理的重大推广，将结论从完全图扩展到了任意的2-连通图，极大地扩展了多面体方法在TSP上的应用范围。其次，研究引入了“锁定子图”这一新颖的图论概念，精确地区分了哪些子巡回约束在定义多面体时是本质的（定义面的），哪些是冗余的。这不仅深化了对子巡回多面体几何结构的理论理解，也为设计切割平面算法提供了直接的理论指导：算法可以优先生成或分离对应于锁定子图的约束，从而提高求解效率。最后，研究所给出的P(G)的最小描述本身具有重要的理论价值，它是对该多面体不等式系统的一个简洁而完整的刻画，为后续相关研究（如研究其他组合多面体，或设计针对稀疏图TSP的精确算法）奠定了坚实的基础。
