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)$延迟算法有所改进。

0
下载
关闭预览

相关内容

专知会员服务
57+阅读 · 2021年6月1日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
123+阅读 · 2020年9月8日
最新《图嵌入组合优化》综述论文,40页pdf
专知会员服务
34+阅读 · 2020年9月7日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Java8 Lambda实现源码解析
阿里技术
2+阅读 · 2022年11月22日
动手实现推荐系统评价指标
机器学习与推荐算法
1+阅读 · 2022年6月1日
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
0+阅读 · 2023年6月2日
VIP会员
相关资讯
Java8 Lambda实现源码解析
阿里技术
2+阅读 · 2022年11月22日
动手实现推荐系统评价指标
机器学习与推荐算法
1+阅读 · 2022年6月1日
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员