清华大学计算机系智能优化团队在超大规模智能优化求解器领域取得了新的突破,打破美国对我们的“卡脖子”问题,所开发的大规模智能优化求解器性能超越美国Gurobi商用求解器30%,成果发布在国际机器学习顶级国际会议ICML2023。联系方式:清华大学计算机系智能优化研究团队xuhua@tsinghua.edu.cn 支持团队:北京觉慧科技有限公司(原北京觉铭科技有限公司)
We Are Talking About Intelligent Optimization 我们说的是--超大规模智能优化求解
清华大学计算机系智能优化团队在超大规模智能优化求解器领域取得了新的突破,打破美国对我们的“卡脖子”问题,求解性能超越美国Gurobi商用求解器30%,成果发布在国际机器学习顶级国际会议ICML2023
Intelligent Optimization

智能优化是一种利用人工智能技术的优化方法,旨在通过模拟自然界的生物进化、群体行为等现象,采用自适应的算法来解决复杂的优化问题。 其核心思想是通过不断地搜索解空间中的最优解,在不断地迭代过程中寻找最优解,以达到提高效率和降低成本的目的。 智能优化算法具有较强的鲁棒性和全局搜索能力,可以应用于各个领域,如工程优化、金融风险管理、数据挖掘等。

Intelligent Optimization is an optimization method that utilizes artificial intelligence technology, aiming to solve complex optimization problems by simulating natural phenomena such as biological evolution and group behavior, and adopting adaptive algorithms. The core idea is to continuously search for the optimal solution in the solution space and search for the optimal solution during the iterative process, in order to achieve the goal of improving efficiency and reducing costs. Intelligent optimization algorithms have strong robustness and global search ability, and can be applied in various fields, such as engineering optimization, financial risk management, data mining, etc.

定义|Definition 分类|Classification 场景与价值|Scenarios&Value AI For Science 基于神经下潜的优化求解|Introdution to Optimization solution
我们是谁|who we are
清华大学计算机系智能优化团队

清华大学计算机系智能优化研究团队(https://thuiar.github.io/)依托北京信息科学与技术国家研究中心等科研平台。团队负责人以第一或通讯作者发表CCF A类国际会议论文25篇;SCI国际期刊论文45篇(一区32篇,IF>5.0有39篇,ESI高被引2篇),SCI 引用2425次,谷歌学术引用6130次;编著教材4部,学术专著4部;获发明专利授权36项,软著授权26项。成果已被ACM Comput. Surv.等顶级期刊引用,引用者包括6位海内外科学院院士和30余位IEEE Fellow。受邀担任工信部03号科技重大专项核心专家、“科技助力经济2020”国家重点研发计划项目验收专家组组长、国家发改委国家产业创新中心咨询专家、Elsevier人工智能国际期刊Intell. Syst. Appl.主编和Expert Syst. Appl.(1区,SCI IF=8.665)副主编。曾获得国家科技进步二等奖1次,北京市科学技术一等奖1次,行业协会科技一等奖2次,其它省部级二、三等奖3次。

团队近年来专注于智能优化理论和作业调度方法的研究工作,提出了面向多目标优化的智能演化优化理论和柔性作业车间调度(FJS)方法技术。所提出的基于Theta支配关系的演化优化方法被IEEE智能系统学会副主席评价为自2010年继第三代非支配排序算法(NSGA-III)之后又一里程碑性的最先进研究成果,有效解决了高维多目标优化问题求解,是当前最先进方法之一;成果发表在IEEE Trans. on EC(SCI IF= 16.497)等期刊上,被美国阿贡国家实验室、橡树岭国家实验室、日本宇航局和普林斯顿大学等应用于专业问题的优化求解。另一方面,所提出的作业调度方法成果被欧洲科学院院士焦李成教授评价为当前五类经典FJS调度方法之一,国际权威分析报告LCR分析为当前十大经典FJS调度算法排名第4。成功应用于国家面临的“卡脖子”领域——芯片制造领域自主国产化装备上(首台国产高密度等离子刻蚀机、PVD等),曾获国家科技进步二等奖和省部级和行业协会科技奖。独立编著出版国内演化机器学习领域首部学术专著《演化机器学习》。即将出版“演化学习与智能优化”系列学术专著。

Computer science department, TsingHua university (https://thuiar.github.io/) based on intelligent optimization research team in Beijing information science and technology, national research center for scientific research platform. The team leader published 25 CCF Class A international conference papers as the first or corresponding author; 45 SCI international journal papers (32 in Region I, 39 IF>5.0, 2 ESI highly cited), SCI citations, Google academic citations 6130 times; He has edited 4 textbooks and 4 academic monographs. It has been authorized 36 invention patents and 26 soft patents. The results have been cited by top journals such as ACM Comput. Surv., including 6 academicians of Chinese Academy of Sciences at home and abroad and more than 30 IEEE Fellows. Invited to serve as the core expert of No. 03 Science and Technology major project of the Ministry of Industry and Information Technology, "Science and Technology to help the economy 2020" national key research and development plan project acceptance team leader, National Industrial Innovation Center of the National Development and Reform Commission consulting expert, Elsevier artificial intelligence international journal Intell.Syst.Appl. Chief Editor and Associate Editor of Expert Syst.Appl. (Region 1, SCI IF=8.665). He has won the second prize of National Science and Technology Progress once, the first prize of Beijing Science and Technology once, the first prize of industry association science and technology twice, and the second and third prizes of other provincial and ministerial levels three times.

In recent years, the team has focused on the research of intelligent optimization theory and job scheduling methods, and proposed intelligent evolutionary optimization theory for multi-objective optimization and flexible job shop scheduling (FJS) method technology. The proposed evolutionary optimization method based on Theta domination relationship was evaluated by the vice president of IEEE Intelligent Systems Society as another milestone of the most advanced research achievement since 2010 after the third generation of non-domination sorting algorithm (NSGA-III), which effectively solved the high-dimensional multi-objective optimization problem, and is one of the most advanced methods at present. The results have been published in IEEE Trans.on EC (SCI IF= 16.497) and other journals, and have been applied to the optimization of professional problems by Argonne National Laboratory, Oak Ridge National Laboratory, Japan Space Agency and Princeton University. On the other hand, the proposed job scheduling method was evaluated as one of the five classic FJS scheduling methods by Professor Jiao Licheng, academician of the European Academy of Sciences, and the LCR analysis of the international authoritative analysis report ranked the fourth among the top ten classic FJS scheduling algorithms. It has been successfully applied to the "jam neck" field faced by the country - the independent localization equipment in the field of chip manufacturing (the first domestic high-density plasma etching machine, PVD, etc.), and has won the second prize of National science and Technology Progress and the science and technology award of provincial and ministerial level and industry association. He independently edited and published the first academic monograph "Evolutionary Machine Learning" in the field of evolutionary machine learning in China. A series of academic monographs "Evolutionary Learning and intelligent Optimization" will be published soon.


What we did|最新成果
研究团队在多目标优化理论的研究贡献 研究团队在作业调度方法的研究贡献
我们最新的成果:解决超大规模规划问题--超大规模平台调度|Our latest achievement:solving the problem of large-scale planning-scheduling of large-scale platforms
成果简介
介绍视频
开放下载

超大规模整数规划问题——超大规模平台调度
VLSI integer programming problem -- VLSI platform scheduling

成果简介(论文摘要 + 实验对比图表(与SCIP,GUROBI的对比)
Abstract of paper & Experimental comparison chart (Comparison with SCIP and GUROBI)

面向大规模整数规划问题,最新的基于图神经网络(Graph Neural Network,GNN)和大邻域搜索(Large Neighborhood Search, LNS)的两阶段优化框架是目前最热门的优化框架。但是现有的两阶段优化框架在图卷积网络上不能有效利用编码空间的特殊性质,且在大邻域搜索阶段高度依赖于大规模求解器,最终导致能解决的整数规划问题规模受限于当前求解器的求解能力,并进一步导致性能瓶颈。为了解决这些问题,本章提出了基于图神经网络和梯度提升决策树的大规模整数规划优化框架(GNN&GBDT-Guided Fast Optimizing Famework for Large-scale Integer Programming), 该 框 架 能 仅 使 用 小 规 模 的 优 化 求 解 器 高 效 求 解 大 规 模 整 数规划问题。具体来说,提出的框架可以被分为三个阶段:多任务图神经网络编码阶段(Multitask GNN Embedding)生成了编码空间,梯度提升决策树预测阶段(GBDT Prediction)高效使用编码空间信息,邻域优化阶段(Neighborhood Optimization)使用小规模优化求解器高效求解大规模整数规划问题。实验表明提出的框架可以只使用原问题规模 30% 大小的求解器就能解决百万级别的整数规划问题,并且能在固定的运行时间里得到比大规模求解器 SCIP 和 Gurobi 更好的结果。实验还表明提出的框架能节约 99% 的运行时间以达到和 SCIP 相同的求解质量,进一步验证了求解框架在解决大规模整数规划问题的有效性和高效性。

For large-scale integer programming problems, the latest Graph Neural Network (Graph Neural Network)
The two-stage optimization frameworks of GNN and Large Neighborhood Search (LNS) are currently the most popular optimization frameworks. However, the existing two-stage optimization framework cannot effectively utilize the special properties of coding space in graph convolutional networks, and it is highly dependent on large-scale solvers in the large neighborhood search stage. As a result, the scale of integer programming problems that can be solved is limited by the solving ability of the current solvers, and further leads to performance bottlenecks. To solve these problems, this chapter proposes a GNN&GBDT-Guided Fast Optimizing Famework for Large-scale Integer Programming based on graph neural networks and gradient lifting decision trees. The frame can be used to solve the integer programming problem of large moduli efficiently only with the optimization solver of small moduli. Specifically, the proposed framework can be divided into three phases: The coding space is generated in the coding phase of Multitask GNN Embedding, and the coding space information is efficiently used in the GBDT Prediction phase. The Neighborhood Optimization phase uses small-scale optimization solvers to efficiently solve large-scale integer programming problems. Experiments show that the proposed framework can solve millions of integer programming problems using only 30% of the original problem size, and can get better results than large-scale solvers SCIP and Gurobi in fixed running time. The experiment also shows that the proposed framework can save 99% running time to achieve the same solution quality as SCIP, which further verifies the effectiveness and efficiency of the solution framework in solving large-scale integer programming problems.


实验对比图表 Experimental comparison chart
在相同的运行时间下,提出框架与 SCIP 和 Gurobi 在不同的基准整数规划问题上的目标值结果的比较
Comparison of the target value results with SCIP and Gurobi on different benchmark integer programming problems under the same runtime
在相同的运行时间下,在不同的基准整数规划问题的目标值结果上,全面超越SCIP和Gurobi
在相同的优化结果下,提出框架与 SCIP 和 Gurobi 在不同的基准整数规划问题上的运行时间的比较
Comparing the runtime with SCIP and Gurobi on different benchmark integer programming problems under the same optimization results
在相同的优化结果下,在不同的基准整数规划问题的运行时间上,全面超越SCIP和Gurobi
在相同的运行时间下,提出框架与 SCIP 和 Gurobi 在不同的整数规划问题上的目标值结果的比较
Comparison of the target value results with SCIP and Gurobi on different integer programming problems under the same runtime
在相同的运行时间下,在整数规划的目标值结果上,全面超越SCIP和Gurobi
在相同的优化结果下,提出框架与 SCIP 和 Gurobi 在不同的整数规划问题上的运行时间的比较
Comparing the runtime with SCIP and Gurobi on different integer programming problems under the same optimization results
在相同的优化结果下,在不同的整数规划问题上的运行时间上,全面超越SCIP和Gurobi

关于高维算法说明:高维求解算法暂不开放共享,合作交流可联系。High-dimensional algorithm is not open for sharing, and can be contacted for cooperation and communication
应用案例|Application Cases|某大型互联网平台优化问题
某大型互联网平台面临百万级别的超大规模人员在线调度问题,考虑到人员可行的活动集合可以映射到有限的离散空间,从调度台的角度该问题可抽象为百万级别决策变量+百万级别约束条件
的单目标整数规划问题。本团队提出的方法采用基于图卷积神经网络和梯度提升决策树的三阶段快速优化框架,实现仅使用小规模开源求解器完成对该超大规模问题的求解,在固定时间内求解效果远超商用求解器Gurobi
A large-scale internet platform is facing a massive personnel scheduling problem involving millions of individuals. Considering that the feasible activities of personnel can be mapped to a limited discrete space, from the perspective of scheduling, this problem can be abstracted as a single-objective integer programming problem with millions of decision variables and millions of constraints. The method proposed by our team employs a three-stage fast optimization framework based on graph convolutional neural networks and gradient boosting decision trees. It achieves the solution to this large-scale problem using only small-scale open-source solvers, surpassing the performance of commercial solver Gurobi within a fixed timeframe.
关于合作 清华大学计算机系智能优化团队,合作内容:超大规模多目标优化问题的求解、动态多目标优化问题的求解、超大规模优化问题的约束降维、超大规模优化问题的决策变量降维、特定领域特征优化基线数据生成器及数据集、其它超大规模优化问题的求解合作
About Cooperation 研究团队开放资源下载|Research Team Open Source Download
求解框架代码与大规模实验结果(GitHub)
求解框架代码与大规模实验结果(Hugging Face)
研究组网站与其他信息|The Research Team Website
thuiar.github.io/
联系方式|清华大学计算机系智能优化研究团队xuhua@tsinghua.edu.cn|Contact information Intelligent Optimization Research team, Department of Computer Science, Tsinghua University xuhua@tsinghua.edu.cn
清华大学计算机系智能优化研究团队xuhua@tsinghua.edu.cn 支持团队:北京觉慧科技有限公司(原北京觉铭科技有限公司)
版权所有 清华大学计算机系智能优化研究团队 & 北京觉慧科技有限公司    京ICP备16046403号-1
Copyright ©2023- Intelligent Optimization Research Team, Department Computer Science, TsingHua University & BeiJing DreamSmart Technology Co.,Ltd ,All Rights Reserved