检索结果-南通市图书馆

Enhancing cut selection through reinforcement learning

Science China Mathematics 2024年第6期67卷 1377-1394页

作者： Shengchao Wang Liang Chen Lingfeng Niu yu-hong dai Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing100190China Research Center on Fictitious Economy and Data Science Chinese Academy of SciencesBeijing100190China

With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research domain.Apart from constructing end-to-end models directly,integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising direction.The cutting plane method is one of the fundamental algorithms used in modern MILP solvers,and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing efficiency.Due to the reliance on expert knowledge and problem-specific heuristics,classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane method.To provide a more efficient and generalizable strategy,we propose a reinforcement learning(RL)framework to enhance cut selection in the solving process of MILPs.Firstly,we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite graphs.Secondly,we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each metric.Thirdly,a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting factors.Finally,we transform the cut selection process into a Markov decision process and utilize RL method to train the model.Extensive experiments are conducted based on a leading open-source MILP solver SCIP.Results on both general and specific datasets validate the effectiveness and efficiency of our proposed approach.

关键词： reinforcement learning mixed-integer linear programming cutting plane method cut selection

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Preface

引用

Science China Mathematics 2024年第6期67卷 1189-1190页

作者： Zhiping Chen yu-hong dai Tiande Guo Xinmin Yang School of Mathematics and Statistics Xi’an Jiaotong UniversityXi’an710049China Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing100190China School of Mathematical Sciences University of Chinese Academy of SciencesBeijing100049China School of Mathematical Sciences Chongqing Normal UniversityChongqing401331China

Optimization stands as a foundational research discipline,permeating various domains such as engineering,and management,and beyond,where many problems inherently entail optimization.The development of algorithms tailored to solve optimization problems not only holds significant theoretical implications but also promises substantial practical applications.

关键词： optimization. holds optimization

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

A Mini-Batch Proximal Stochastic Recursive Gradient Algorithm with Diagonal Barzilai–Borwein Stepsize

引用

Journal of the Operations Research Society of China 2023年第2期11卷 277-307页

作者： Teng-Teng yu Xin-Wei Liu yu-hong dai Jie Sun School of Artificial Intelligence Hebei University of TechnologyTianjin 300401China Institute of Mathematics Hebei University of TechnologyTianjin 300401China LSEC ICMSECAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190China School of Business National University of SingaporeSingapore 119245Singapore

Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization term.Proximal stochastic gradient methods are popular for solving such composite optimization problems.We propose a minibatch proximal stochastic recursive gradient algorithm SRG-DBB,which incorporates the diagonal Barzilai–Borwein(DBB)stepsize strategy to capture the local geometry of the problem.The linear convergence and complexity of SRG-DBB are analyzed for strongly convex functions.We further establish the linear convergence of SRGDBB under the non-strong convexity condition.Moreover,it is proved that SRG-DBB converges sublinearly in the convex case.Numerical experiments on standard data sets indicate that the performance of SRG-DBB is better than or comparable to the proximal stochastic recursive gradient algorithm with best-tuned scalar stepsizes or BB stepsizes.Furthermore,SRG-DBB is superior to some advanced mini-batch proximal stochastic gradient methods.

关键词： Stochastic recursive gradient Proximal gradient algorithm Barzilai-Borwein method Composite optimization

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Preface:Special Issue on New Developments in Mathematical Programming and Operations Research

引用

Journal of the Operations Research Society of China 2022年第2期10卷 193-195页

作者： yu-hong dai De-Ren Han Ling-yun Wu Yan Xu Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing 100190China School of Mathematical Sciences Beihang UniversityBeijing 100191China School of Mathematics and Physics University of Science and TechnologyBeijing 1000191China

COVID-19 has brought us an abnormal environment,which caused a great deal of inconvenience to every aspect of life,including academic interchange.In response to this,the Operations Research Society of China(ORSC)organized an OR Road-to-Future Forum(运筹千里纵横论坛).As of April 30,2020,this series forum has held more than 100 talks from globally outstanding operational researchers,including the IFORS President Professor M.Grazia Speranza from University of Brescia(Italy),Professor Yin-yu Ye from Stanford University(USA),Professor Zhi-Quan Luo from the Chinese University of hong Kong(Shenzhen,China),and Professor De-Feng Sun from the hong Kong Polytechnic University(hong Kong,China).At the same time,OR Road-to-Future Forum also invites some outstanding junior speakers to share their latest works.These talks cover a wide range of areas in mathematical programming and operations research,such as graph theory,computational mathematics,bioinformatics,machine learning,artificial intelligence,engineering problems,as well as their applications.

关键词： speakers operations globally

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Achieving geometric convergence for distributed optimization with Barzilai-Borwein step sizes

引用

Science China(Information Sciences) 2022年第4期65卷 280-281页

作者： Juan GAO Xin-Wei LIU yu-hong dai Yakui HUANG Peng YANG School of Artificial Intelligence Hebei University of Technology Institute of Mathematics Hebei University of Technology LSEC Academy of Mathematics and Systems Science Chinese Academy of Sciences School of Mathematical Sciences University of Chinese Academy of Sciences

Dear editor,We consider distributed optimization, which can be formulated to minimize the average of all local objective functions:■where each local function f;:■ is L;-smooth and μ;-strongly convex and known only ... 详细信息

关键词： distributed optimization multi-agent network Barzilai-Borwein step sizes optimization algorithms convergence rate

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

A New Analysis on the Barzilai-Borwein Gradient Method

引用

Journal of the Operations Research Society of China 2013年第2期1卷 187-198页

作者： yu-hong dai State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems ScienceChinese Academy of SciencesP.O.Box 2719Beijing 100190P.R.China

Due to its simplicity and efficiency,the Barzilai and Borwein(BB)gradi-ent method has received various attentions in different fields.This paper presents a new analysis of the BB method for two-dimensional strictly convex quadratic func-tions.The analysis begins with the assumption that the gradient norms at the first two iterations are fixed.We show that there is a superlinear convergence step in at most three consecutive steps.Meanwhile,we provide a better convergence relation for the BB method.The influence of the starting point and the condition number to the convergence rate is comprehensively addressed.

关键词： Unconstrained optimization Barzilai and Borwein gradient method Quadratic function R-superlinear convergence Condition number

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Analysis of Sparse Quasi-Newton Updates with Positive Definite Matrix Completion

引用

Journal of the Operations Research Society of China 2014年第1期2卷 39-56页

作者： yu-hong dai Nobuo Yamashita State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems ScienceChinese Academy of SciencesP.O.Box 2719Beijing 100080People’s Republic of China Department of Applied Mathematics and Physics Graduate School of InformaticsKyoto UniversityKyoto 606-8501Japan

Based on the idea of maximum determinant positive definite matrix completion,Yamashita(Math Prog 115(1):1–30,2008)proposed a new sparse quasi-Newton update,called MCQN,for unconstrained optimization problems with sparse Hessian structures.In exchange of the relaxation of the secant equation,the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian matrices.However,local and superlinear convergence results were only established for the MCQN update with the DFP method.In this paper,we extend the convergence result to the MCQN update with the whole Broyden’s convex family.Numerical results are also reported,which suggest some efficient ways of choosing the parameter in the MCQN update the Broyden’s family.

关键词： Quasi-Newton method Large-scale problems Sparsity Positive definite matrix completion Superlinear convergence

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

引用

Science China Mathematics 2021年第1期64卷 211-220页

作者： Wei-Kun Chen yu-hong dai School of Mathematics and Statistics Beijing Institute of TechnologyBeijing100081China LSEC ICMSECAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing100190China School of Mathematical Sciences University of Chinese Academy of SciencesBeijing100049China

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs.However,it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover(Gu et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.

关键词： integer programming sequentially lifted cover inequality complexity lifting problem

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Complexity Analysis and Algorithm Design of Pooling Problem

引用

Journal of the Operations Research Society of China 2018年第2期6卷 249-266页

作者： yu-hong dai Rui Diao Kai Fu State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190China

The pooling problem,also called the blending problem,is fundamental in production planning of petroleum.It can be formulated as an optimization problem similar with the minimum-cost flow problem.However,Alfaki and Haugland(J Glob Optim 56:897–916,2013)proved the strong NP-hardness of the pooling problem in general case.They also pointed out that it was an open problem to determine the computational complexity of the pooling problem with a fixed number of qualities.In this paper,we prove that the pooling problem is still strongly NP-hard even with only one quality.This means the quality is an essential difference between minimum-cost flow problem and the pooling problem.For solving large-scale pooling problems in real applications,we adopt the non-monotone strategy to improve the traditional successive linear programming method.Global convergence of the algorithm is established.The numerical experiments show that the non-monotone strategy is effective to push the algorithm to explore the global minimizer or provide a good local minimizer.Our results for real problems from factories show that the proposed algorithm is competitive to the one embedded in the famous commercial software Aspen PIMS.

关键词： Pooling problem Complexity analysis Successive linear programming Non-monotone

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

A Stochastic Approximation Frame Algorithm with Adaptive Directions

引用

Numerical Mathematics(Theory,Methods and Applications) 2008年第4期1卷 460-474页

作者： Zi Xu yu-hong dai Department of Mathematics College of Sciences Shanghai University Shang-hai 200444 PR. China. State Key Laboratory of Scientific and Engineering Computing Institute of Com-putational Mathematics and Scientific/Engineering Computing The Academy ofMathematics and Systems Science Chinese Academy of Sciences P.O.Box 2719Beijing 100190 P.R. China.

Stochastic approximation problem is to find some root or extremum of a non- linear function for which only noisy measurements of the function are available.The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm,which uses the noisy evaluation of the negative gradient direction as the iterative direction.In order to accelerate the RM algorithm,this paper gives a flame algorithm using adaptive iterative directions.At each iteration,the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions.Two feasible choices of the criterions are pro- posed and two corresponding flame algorithms are formed.Different choices of the directions under the same given switch criterion in the flame can also form different algorithms.We also proposed the simultanous perturbation difference forms for the two flame algorithms.The almost surely convergence of the new algorithms are all established.The numerical experiments show that the new algorithms are promising.

关键词：随机逼近共轭梯度自适应方向极值

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：