计算机科学
强化学习
启发式
可扩展性
数学优化
放松(心理学)
公制(单位)
集合(抽象数据类型)
人工智能
线性规划松弛
分析
线性规划
跳跃式监视
变量(数学)
机器学习
算法
数学
数据挖掘
心理学
社会心理学
数学分析
运营管理
数据库
经济
程序设计语言
作者
Quentin Cappart,David Bergman,Louis-Martin Rousseau,Isabeau Prémont‐Schwarz,Augustin Parjadis
出处
期刊:Informs Journal on Computing
日期:2022-05-04
卷期号:34 (5): 2552-2570
被引量:10
标识
DOI:10.1287/ijoc.2022.1194
摘要
Prescriptive analytics provides organizations with scalable solutions for large-scale, automated decision making. At the core of prescriptive analytics methodology is optimization, a field devoted to the study of algorithms that solve complex decision-making problems. Optimization algorithms rely heavily on generic methods for identifying tight bounds, which provide both solutions to problems and optimality guarantees. In the last decade, decision diagrams (DDs) have demonstrated significant advantages in obtaining bounds compared with the standard linear relaxation commonly used by commercial solvers. However, the quality of the bounds computed by DDs depends heavily on the variable ordering chosen for the construction. Besides, the problem of finding an ordering that optimizes a given metric is generally NP-hard. This paper studies how machine learning, specifically deep reinforcement learning (DRL), can be used to improve bounds provided by DDs, in particular through learning a good variable ordering. The introduced DRL models improve primal and dual bounds, even over standard linear programming relaxations, and are integrated in a full-fledged branch-and-bound algorithm. This paper, therefore, provides a novel mechanism for utilizing machine learning to tighten bounds, adding to recent research on using machine learning to obtain high-quality heuristic solutions and, for the first time, using machine learning to improve relaxation bounds through a generic bounding method. We apply the methods on a classic optimization problem, the maximum independent set, and demonstrate through computational testing that optimization bounds can be significantly improved through DRL. We provide the code to replicate the results obtained on the maximum independent set. Summary of Contribution: This paper studies the use of reinforcement learning to compute a variable ordering of decision diagram-based approximations for discrete optimization problems. This is among the first works to propose the use of machine learning to improve upon generic bounding methods for discrete optimization problems, thereby establishing a critical bridge between optimization and learning.
科研通智能强力驱动
Strongly Powered by AbleSci AI