In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope ${\rm conv}(X)$, where $X\subseteq \{0,1\}^n$. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem $\min\{w\cdot x\mid x\in X\}$, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only by a factor of $\log n$ larger than the running time of the optimization algorithm. When $X$ encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope ${\rm conv}(X)$ along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all ($c$-optimal) bases in a matroid; ($c$-optimal) spanning trees, forests, ($c$-optimal) matchings in a general graph; ($c$-optimal) vertex covers, ($c$-optimal) stable sets in a bipartite graph; as well as ($c$-optimal) antichains and ideals of a poset. The delay and space required by these algorithms are polynomial in the size of the matroid, graph, or poset, respectively, and these listings correspond to Hamilton paths on the corresponding combinatorial polytopes. We also obtain an $O(t_{\rm LP} \log n)$ delay algorithm for the vertex enumeration problem on 0/1-polytopes $\{x\in\mathbb{R}^n\mid Ax\leq b\}$, where $A\in \mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$, and $t_{\rm LP}$ is the time needed to solve the linear program $\min\{w\cdot x\mid Ax\leq b\}$. This improves upon the 25-year old $O(t_{\rm LP}\,n)$ delay algorithm of Bussieck and L\"ubbecke.
翻译:在本文中,我们提出了一个新的框架,利用组合优化有效地生成基于图形、拟阵、偏序和多面体的多种组合对象。我们的方法依赖于一个简单而多才多艺的算法,用于计算任何0/1-多面体${\rm conv}(X)$的骨架上的哈密尔顿路径,其中$X\subseteq \{0,1\}^n$。该算法使用任何解决经典线性优化问题$\min\{w\cdot x\mid x\in X\}$变体的算法作为黑匣子,所得到的延迟,即每个访问的顶点的运行时间,仅仅是优化算法的运行时间的$\log n$倍。当$X$编码一特定类组合对象时,沿着多面体${\rm conv}(X)$的骨架遍历哈密尔顿路径相当于通过局部变换操作列出组合对象,即我们获得了Gray码列表。作为我们一般框架的具体结果,我们获得了有效的算法来生成拟阵、图中的所有($c$-最优)基;任意图中的($c$-最优)生成树、生成森林、($c$-最优)匹配;二分图中的($c$-最优)顶点覆盖、($c$-最优)稳定集合;以及偏序的($c$-最优)反链和理想。这些算法需要的延迟和空间是多项式大小的拟阵、图形或偏序,这些列表对应于相应组合多面体上的哈密尔顿路径。我们还获得了一个在0/1-多面体$\{x\in\mathbb{R}^n\mid Ax\leq b\}$上执行顶点枚举问题的$O(t_{\rm LP}\,\log n)$延迟算法,其中$A\in \mathbb{R}^{m\times n}$ 且 $b\in\mathbb{R}^m$ , $t_{\rm LP}$是解决线性规划$\min\{w\cdot x\mid Ax\leq b\}$的时间。这比Bussieck和L\"ubbecke 25年前的$O(t_{\rm LP}\,n)$延迟算法有所改进。