《8-1 机器学习遇上运筹优化助力企业降本增效:一种双层优化方法.pdf》由会员分享,可在线阅读,更多相关《8-1 机器学习遇上运筹优化助力企业降本增效:一种双层优化方法.pdf(22页珍藏版)》请在三个皮匠报告上搜索。
1、机器学习遇上运筹优化:一种双层优化方法A Bi-Level Framework for Learning to Solve Combinatorial Optimization on GraphsRunzhong Wang Zhigang Hua Gan Liu Jiayi Zhang Junchi Yan Feng Qi Shuang Yang Jun Zhou Xiaokang YangNeurIPS 2021Code Available at https:/ BioEducation 2019-now:PhD student at Shanghai Jiao Tong Universit
2、y 2015-2019:Bachelor student at Shanghai Jiao Tong UniversityResearch Interest Graph learning,especially machine learning and combinatorial optimization.Publications I have published 11 papers(7 first-author)in top conferences and journals,including TPAMI,NeurIPS,ICML,ICLR,ICCV,and CVPR.I develop an
3、d maintain several Github repositories with 1700+stars.Academic/Social Services I serve as the reviewer of ICML,NeurIPS,ICLR,CVPR,ICCV,AAAI,and MM.I serve as the class monitor of Wu Wen-Tsun Honorary Doctoral Class at Shanghai Jiao Tong University.At the oral session at ICCV 20193What is Optimizatio
4、n?optimization/ptmzen/nounthe action of making the best or most effective use of a situation or resource.(Oxford English dictionary)Convex OptimizationStrong general solversMany are polynomial-timeNon-Convex OptimizationNo general solversUsually exponential-time4What is Combinatorial Optimization?mi
5、n ,.discrete constraints on What Combinatorial Optimization(CO)looks like:for example:is binary has no more than nonzero elements is a path from A to B0/1 knapsackcardinality-constrained portfoliorouting5The Problems Considered in This Paper Graph Edit Distance:Minimize graph edit cost Hamiltonian C
6、ycle:Find valid Hamiltonian Cycles DAG Scheduling:Minimizemakespan timeMao et al.“Learning scheduling algorithms for data processing clusters.SIGCOMM 2019.Wang et al.“Combinatorial learning of graph edit distance via dynamic embedding.”CVPR 2021MethicillinPenicillin6Combinatorial Optimization Proble
7、ms on GraphsExponential worst-case complexity:NP-complete or NP-hardHowever:We are solving similar problems again and againData-driven approaches are appealing!State Of Mathematical Optimization Report 2021,Gurobi Optimization LLC.7Optimization Techniques have been Adoptedby various industries:for v
8、arious purposes:2.2xEstimated Growth of Global Marketfrom 2020 to 2025(Markets and Markets Research Ltd.,2020)Why ML for Combinatorial OptimizationYoshua Bengio et al.Machine LearningMachine Learning for Combinatorial OptimizationCombinatorial Optimization:a Methodological Tour dHorizon.In Euro.J.Op
9、erations Research 2020.Buy a commercial solver:$100K/yearHow giant companies do optimization today:We are solving problems with similar structures again and againIt is appealing to model the problem automatically in a data-driven manner.Most companies&organizations:We cannot afford this.Download an
10、open-source solver:freeMy vision for future optimization with ML:Provide affordable optimization for all with ML techniques.Whats next Digitalization?Hire a team of PhD:$1M/year Tailored algorithms and hyperparameters Optimization-as-a-service:charge-on-usage Automatic algorithm selection¶meter
11、tuningOptimization!9Existing Papers:Single-Level Optimizationdecision variableobjective scoreconstraintsaction sequencerewardfeasible actionsProblem FormulationRL Approach:However:If is large,the action sequence will be long.Sparse rewardEnough model capacity to learn .Non-trivial model design10Modi
12、fy the Problem Structure to Aid Problem SolvingAdd cutting planes for integer programmingA classic idea:In this paper:Modify the graph structure to aid problem solvingAdd edgesOur Formulation:Bi-Level OptimizationProblem FormulationUpper-Level Optimization:Optimize Lower-Level Optimization:Optimize
13、We introduce an optimized graph .decision variableobjective score with ,constraints with objective score with ,is similar to and no enlarged feasible spaceby RLby classic methods12Bi-Level Optimization by Reinforcement LearningReward13We Implement on 3 Combinatorial Optimization Problems14Experiment
14、 ResultsDAG schedulingGraph Edit Distance We outperform learning-free and learning-based baselines:We can generalize with different training/testing sizes:Learning-free HeuristicsSingle-level baselineRandom baselineOur bi-level methodDAG SchedulingGraph Edit DistanceHamiltonian Cycle Problem15Perhap
15、s the Best Practice for MLCO Previous single-level methods:Demand higher model capacities Manually model design for different problems Harder to converge More engineering efforts Our bi-level method:Lower model capacities A general framework for many problems Easier to converge Less engineering effo
16、rts16Steps to Tackle Your Own ProblemSelect a traditional algorithmDesign the action space:The feasible region is not enlarged after RL action Build the problem encoder(GNN/Transformer)17Further Applications of Combinatorial Optimization Computer Vision Privacy-aware Machine Learning FinanceClient 1
17、Client Ndistributetraintrainuploaduploadfusionvecvec()maxs.t.0,112,=,Learn to Solve:18CV:Image Keypoint MatchingPascal VOC20 classes of imageshttps:/ 2019ICLR 2020TPAMI 2020TPAMI 2021Code:https:/ ML:Federated Learning联邦学习中:神经网络对齐等价于图匹配Client 1Client NCIFAR10:节省40%通信次数distributetraintrainuploadupload
18、fusionCode:https:/ Portfolio Prediction and Optimization资产历史价格(标普500)价格预测模型投资组合优化模型MAX1990诺贝尔经济学奖前端感知预测后端决策优化可微分闭环约束放松可微求解2021历史回测:收益跑赢大盘70%21Open Questions How to optimize billion-scale graphs?How to build general framework for joint prediction and optimization?How to optimization from samples?22Thank You!Code for this talkhttps:/ Collection of Machine Learning and Combinatorial OptimizationPapershttps:/ Novel deep graph matching modelshttps:/ Python Graph Matching Tools(now support:pytorch andnumpy)$pip install pygmtools import pygmtools