Mar, 2018
学习分支
Learning to Branch
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik
TL;DR使用机器学习确定任何一组划分程序的最佳加权,并通过实验证明,学习如何分叉在实践中非常有益,可以显著减小树的规模。
Abstract
tree search algorithms, such as branch-and-bound, are the most widely used
tools for solving combinatorial and nonconvex problems. For example, they are
the foremost method for solving (mixed) integer programs and constraint
satisfaction problems. →
tree search algorithmsmachine learningpartitioning techniquessample complexityalgorithm configuration
发现论文,激发创造
TreeDQN:学习最小化分枝定界树
本文介绍了一种基于强化学习的组合优化问题解决方法,使用树马尔可夫决策过程视角选择变量分支,并且优化学习对象,相较之前的强化学习方法,训练数据量更小,生成树的大小更小。
Jun, 2023
MurTree:使用动态规划和搜索实现的最优分类树
本研究提出了一种基于动态规划和搜索的学习算法来实现最优决策树,这种算法支持对树的深度和节点数量设置限制,并在实验证明使用我们的算法只需要很短的时间就可以处理具有成千上万个实例的数据集,从而极大地提高了最优决策树的实用性。
Jul, 2020
分支:用于优化决策树的快速动态规划和分支限界算法
Branches 算法结合了动态规划和分支界限方法,提供了出色的速度和稀疏性解决方案,通过理论分析和实证评估验证了比现有方法更低复杂性以及始终产生最优的决策树的优势。
Jun, 2024
非凸优化的采样与界限
用采样方法改进蒙特卡洛树搜索来实现全局非凸函数优化,避免传统分区树方法在高维情况下指数级增长的树规模,通过利用数值上估计的目标不确定性指标、采样估计的一阶和二阶信息,并且避免传统固定组合模式,快速高效地发现有潜力的区域,有效平衡探索与开发。在高维非凸优化测试中与其他方法进行了对比,并分析了超参数的影响。
Jan, 2024
分支定界算法中的变量选择强化学习
文章提出了一种名为 FMSTS 的新型增强学习方法,采用一种全新的分支策略来优化整数线性规划问题,具有一致性和泛化能力,并在计算实验中验证了其有效性。
May, 2020
基于整数规划的算法选择问题的最优决策树
本文提出了基于整数规划的方法来构建用于算法选择问题的决策树,并使用 COIN-OR Branch & Cut solver 实现的线性规划算法进行了实验。实验结果表明,该方法具有很好的泛化性能且未过度拟合。
Jul, 2019