首页期刊导航|中国科学：数学（英文版）
期刊信息/Journal information
中国科学：数学（英文版）
中国科学：数学（英文版）

周光召

月刊

1674-7283

sales@scichina.org

010-64019820

100717

北京东黄城根北街16号

中国科学：数学（英文版）/Journal Science China(Mathematics)CSCDCSTPCDSCI
查看更多>>《中国科学》是中国科学院主办、中国科学杂志社出版的自然科学专业性学术刊物。《中国科学》任务是反映中国自然科学各学科中的最新科研成果，以促进国内外的学术交流。《中国科学》以论文形式报道中国基础研究和应用研究方面具有创造性的、高水平的和有重要意义的科研成果。在国际学术界，《中国科学》作为代表中国最高水平的学术刊物也受到高度重视。国际上最具有权威的检索刊物SCI，多年来一直收录《中国科学》的论文。1999年《中国科学》夺得国家期刊奖的第一名。
正式出版
收录年代

    Preface

    Zhiping ChenYu-Hong DaiTiande GuoXinmin Yang...
    1189-1190页
      原文链接:
    • 万方数据
    • 维普

    Learning to optimize:A tutorial for continuous and mixed-integer optimization

    Xiaohan ChenJialin LiuWotao Yin
    1191-1262页
    查看更多>>摘要：Learning to optimize(L2O)stands at the intersection of traditional optimization and machine learning,utilizing the capabilities of machine learning to enhance conventional optimization techniques.As real-world optimization problems frequently share common structures,L2O provides a tool to exploit these structures for better or faster solutions.This tutorial dives deep into L2O techniques,introducing how to accelerate optimization algorithms,promptly estimate the solutions,or even reshape the optimization problem itself,making it more adaptive to real-world applications.By considering the prerequisites for successful applications of L2O and the structure of the optimization problems at hand,this tutorial provides a comprehensive guide for practitioners and researchers alike.
      原文链接:
    • 万方数据
    • 维普

    Optimal pivot path of the simplex method for linear programming based on reinforcement learning

    Anqi LiTiande GuoCongying HanBonan Li...
    1263-1286页
    查看更多>>摘要：Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is Cnm,our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.
      原文链接:
    • 万方数据
    • 维普

    Alleviating limit cycling in training GANs with an optimization technique

    Keke LiLiping TangXinmin Yang
    1287-1316页
    查看更多>>摘要：In this paper,we undertake further investigation to alleviate the issue of limit cycling behavior in training generative adversarial networks(GANs)through the proposed predictive centripetal acceleration algorithm(PCAA).Specifically,we first derive the upper and lower complexity bounds of PCAA for a general bilinear game,with the last-iterate convergence rate notably improving upon previous results.Then,we combine PCAA with the adaptive moment estimation algorithm(Adam)to propose PCAA-Adam,for practical training of GANs to enhance their generalization capability.Finally,we validate the effectiveness of the proposed algorithm through experiments conducted on bilinear games,multivariate Gaussian distributions,and the CelebA dataset,respectively.
      原文链接:
    • 万方数据
    • 维普

    Learning to sample initial solution for solving 0-1 discrete optimization problem by local search

    Xin LiuJianyong SunZongben Xu
    1317-1340页
    查看更多>>摘要：Local search methods are convenient alternatives for solving discrete optimization problems(DOPs).These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time limit.It is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search method.In this paper,we propose to take the initial solution as a random variable and learn its preferable probability distribution.The aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality solution.We develop two different deep network models to deal with DOPs established on set(the knapsack problem)and graph(the maximum clique problem),respectively.The deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability vector.Experimental results show that given the initial solution sampled from the learned probability distribution,a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erdös-Rényi random graph instances.Furthermore,with sampled initial solutions,a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS instances.Particularly,we emphasize that the developed models can generalize in dimensions and across graphs with various densities,which is an important advantage on generalizing deep-learning-based optimization algorithms.
      原文链接:
    • 万方数据
    • 维普

    A neural branch-and-price for truck scheduling in cross-docks

    Rahimeh Neamatian MonemiShahin GelarehNelson MaculanWei-Kun Chen...
    1341-1358页
    查看更多>>摘要：In this paper,we address the complex problem of dock-door assignment and truck scheduling within cross-docking operations.This is a problem that requires frequent resolution throughout the operational day,as disruptions often invalidate the optimal plan.Given the problem's highly combinatorial nature,finding an optimal solution demands significant computational time and resources.However,the distribution of data across problem instances over a lengthy planning horizon remains consistently stable,with minimal concern regarding distribution shift.These factors collectively establish the problem as an ideal candidate for a learn-to-optimize solution strategy.We propose a Dantzig-Wolfe reformulation,solving it via both a conventional branch-and-price approach and a neural branch-and-price approach,the latter of which employs imitation learning.Additionally,we introduce some classes of valid inequalities to enhance and refine the pricing problem through a branch-and-cut scheme.Our computational experiments demonstrate that this methodology is not only feasible but also presents a viable alternative to the traditional branch-and-price algorithms typically utilized for such challenges.
      原文链接:
    • 万方数据
    • 维普

    NeuroPrim:An attention-based model for solving NP-hard spanning tree problems

    Yuchen ShiCongying HanTiande Guo
    1359-1376页
    查看更多>>摘要：Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.
      原文链接:
    • 万方数据
    • 维普

    Enhancing cut selection through reinforcement learning

    Shengchao WangLiang ChenLingfeng NiuYu-Hong Dai...
    1377-1394页
    查看更多>>摘要：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.
      原文链接:
    • 万方数据
    • 维普

    A dynamical neural network approach for distributionally robust chance-constrained Markov decision process

    Tian XiaJia LiuZhiping Chen
    1395-1418页
    查看更多>>摘要：In this paper,we study the distributionally robust joint chance-constrained Markov decision process.Utilizing the logarithmic transformation technique,we derive its deterministic reformulation with bi-convex terms under the moment-based uncertainty set.To cope with the non-convexity and improve the robustness of the solution,we propose a dynamical neural network approach to solve the reformulated optimization problem.Numerical results on a machine replacement problem demonstrate the efficiency of the proposed dynamical neural network approach when compared with the sequential convex approximation approach.
      原文链接:
    • 万方数据
    • 维普

    Gradient-based algorithms for multi-objective bi-level optimization

    Xinmin YangWei YaoHaian YinShangzhi Zeng...
    1419-1438页
    查看更多>>摘要：Multi-objective bi-level optimization(MOBLO)addresses nested multi-objective optimization problems common in a range of applications.However,its multi-objective and hierarchical bi-level nature makes it notably complex.Gradient-based MOBLO algorithms have recently grown in popularity,as they effectively solve crucial machine learning problems like meta-learning,neural architecture search,and reinforcement learning.Unfortunately,these algorithms depend on solving a sequence of approximation subproblems with high accuracy,resulting in adverse time and memory complexity that lowers their numerical efficiency.To address this issue,we propose a gradient-based algorithm for MOBLO,called gMOBA,which has fewer hyperparameters to tune,making it both simple and efficient.Additionally,we demonstrate the theoretical validity by accomplishing the desirable Pareto stationarity.Numerical experiments confirm the practical efficiency of the proposed method and verify the theoretical results.To accelerate the convergence of gMOBA,we introduce a beneficial L2O(learning to optimize)neural network(called L2O-gMOBA)implemented as the initialization phase of our gMOBA algorithm.Comparative results of numerical experiments are presented to illustrate the performance of L2O-gMOBA.
      原文链接:
    • 万方数据
    • 维普