Jin Lei from Concave Fei Temple qubit | qbitai
The solver, known as the "core of industrial software", has been monopolized by foreign countries for many years
Recently, the Industrial Development Promotion Center of the Ministry of Industry and Information Technology and other units held a special competition (the first energy electronics industry innovation competition) to allow domestic solvers to PK in the complex scenario of power grid dispatching.
Why are solvers so important?
In fact, whether it is the scheduling of subways and planes, or the design of express package delivery routes, it is the solver behind the calculation of these complex math problems.
It's like the "strongest brain", always able to quickly find the optimal solution in a very large-scale task.
In important fields related to the national economy and people's livelihood, such as industrial design and power grid dispatching, as long as digital transformation is involved, the intelligent decision-making capabilities provided by the solver cannot be bypassed.
The championship of this competition was won by Mindopt, which was independently developed by Alibaba DAMO Academy for four years.
It has excellent performance in speed indicators and accuracy indicators, and helps to minimize the start-up and shutdown costs and operating costs of units while ensuring the safe operation of the power grid.
Generated by Dall·e 3.
In fact, the technical barriers of solvers are high, and the research and development is difficult, looking at a few years ago, this field was almost monopolized by foreign manufacturers, and it was as long as decades.
Therefore, the process of realizing the domestic self-development of the solver from 0 to 1 and has matured enough to be assured of "taking up the post of power dispatcher" can also be regarded as a microcosm of the development history of the domestic solver.
After 4 years of independent research and development, this software has actually just been launched1Version 0.
Next, let's turn over this "four years of sharpening a sword" and iterate on 26 versions of the story.
Three minutes?No, up to 15 seconds!
Let's go back to 2019.
At that time, the development of domestic solvers was not a barren place, and there were already some companies that were gearing up and emerging in this field.
However, as we just mentioned, foreign commercial solver giants have dominated the global market for 20 years, the most typical ones are Gurobi, known as the "Big Three", IBM's CPClex and FICO's Xpress.
Synthesized with the help of DALL·E 3.
Even the Big Three have been working in the solver space for two decades to build up their technical and commercial experience.
The reason for this is precisely because the technical barriers involved in solvers are too high, covering many scientific fields such as operations research, computational mathematics, software engineering, etc.
Therefore, even if the domestic solver has started, many companies still choose the mature and stable high-performance foreign solver that they are used to: Alibaba and Damo Academy at that time were also the same.
However, in this year, with the arrival of an internationally renowned mathematician, an inevitable prelude to "domestic self-development" was completely opened.
His name is Yin Wotao, and he is the only Chinese scientist to receive the prestigious Egon Balas Prize (won in 2021) in the field of operations research, which is usually awarded to only one person in the world each year.
Yin Wotao. Yin Wotao officially joined the DAMO Academy in March 2019 and is responsible for leading the decision-making intelligence laboratory.
This lab focuses on optimization solver technology, time series technology, interpretable AI technology, and moreAt the same time, in new energy-related ** and scheduling projects, verify the feasibility of technology.
However, not long after he joined the company, the team encountered an "internal worry" problem in the matter of solvers - in the face of the rare business scale and complexity of China's Internet, the performance of foreign solvers reached a bottleneck and was insufficient.
In a task that required intelligent decision-making, the team came up with two solutions based on the existing solver: the first solution took half an hour, and the second solution took 3 minutes.
But the business side said directly:
15 seconds!Users can only wait for a maximum of 15 seconds!
Examples such as this when solver performance could not keep up were becoming more and more frequent in the team's internal practice, and even the team's assessment of the "internal worries" at that time was that all the existing solvers could not solve them.
As a result, in this case, the path of self-development seems to be the only optimal solution for this group of "solver fanatics".
However, one thing to say, at that time, the three giants monopolized the global solver market, and it has gone through decades of development, and the manpower and material resources invested during this period are unimaginable.
It's really hard to develop a high-performance solver from scratch.
Not only are the inherent technical barriers there, but Yin Wotao's starting point is also relatively high—he wants to lead the team to develop his own general optimization solver.
This means that it must be able to deal with a wide range of problems, not only with a high degree of generality, but also with the ability to fine-tune specific problems.
In this way, how to make this solver cover a large number of different algorithms, and configure them well, the subsequent software engineering, algorithm engineering, and multi-core concurrency, etc., have become breakthroughs to be solved.
To this end, Yin Wotao formulated a "two-legged" strategy for the team:
The first leg: the modules that others have implemented well, we must also implement very well;The second leg: research and development of next-generation technologies and explore cutting-edge algorithms. In a word, the Dharma Academy that others can do must be done, and the Dharma Academy that others cannot do must also be done.
Goals and strategies are set, but there are still many difficulties in the implementation process, for example, the construction of team talents has become a long-standing problem.
After all, the talents needed to make a solver are highly interdisciplinary, not only with deep mathematical skills and operations research knowledge, but also with numerical computing and software engineering capabilities.
The even colder reality is that in 2019, many colleges and universities have almost no fully matched majors.
In the face of such a dilemma, Yin Wotao made the choice to absorb talents from within and exercise in development.
Luckily, there are several students in the team who have world-class backgrounds in mathematics or computer scienceSome of the students had in-depth experience in using solvers before joining the team.
What's more, all the students who joined the team have great interest and enthusiasm for the self-developed general optimization solver, and they are "called" to come in as soon as they get through.
According to Wang Mengchang, a senior algorithm expert in the laboratory and one of the main forces in the research and development of general optimization solvers, recalled:
At first, we all crossed the river by feeling the stones, learning on our own through the information that has been published on the Internet, and filling in the gaps. Mr. Yin also recommended a book called Computational Techniques of the **x Method as a must-read, which contains many excellent theoretical and practical cases that are worth learning and learning from.
For those unpublished data, especially for special algorithms, the strategy adopted by the team is to refine the rules in the process of "guessing" and "verifying" step by step, and then make mathematical proofs of the obtained rules, and finally "write" them into the solver.
Of course, this process is not done behind closed doors, and the team is constantly learning from the existing and easy-to-use high-performance solvers to ensure the integrity of the self-developed optimization solvers.
It is through this continuous research, trial and error, and improvement that the general optimization solver of the Damo Academy's Decision Intelligence Laboratory is like building a house, gradually building up from the foundation little by little.
And at this time, the solver has been named - mindopt.
went to hit the list, but it attracted "external trouble".
Just as there will be many authoritative lists to evaluate the performance of popular large model technology, there are also corresponding lists in the solver circle.
After a year of self-development and testing, the initial optimization solver was formed, and Yin and his team decided it was time to go out and give it a try.
In August 2020, they submitted the phased results, that is, the simplex method module of the Damo Academy's self-developed solver Mindopt, to the list of linear programming simplex methods of Mittelmann, an international authoritative third-party evaluation.
And this appearance can be described as a real blockbuster-
Break the record and win the first place!
As can be seen from the results, the number "1" represents the fastest solution speed of the DAMO Academy's self-developed solver and serves as the reference timeThe number "40" indicates that mindopt successfully solved all 40 linear programming studies.
And in speed it is already 0The gap of 1 surpasses that of the established giant manufacturer Gurobi.
Under such achievements, the whole team must be very pleased and happy, after all, their own "internal worries" will be solved.
However, no one expected that such a hit on the list would attract an "external trouble".
As we mentioned earlier, before the DAMO Academy decided to develop its own solver, it used the technology and services of one of the Big Three.
And it was this technical service provider that has cooperated with the Damo Academy for a long time, and suddenly changed its mind after seeing the results of the list:
It turns out that you are developing your own solver, so we will not sell you in the new version in the future.
You must know that although the results of the Damo Academy's self-developed solver at that time were amazing, it focused on the problem of linear programmingHowever, in the process of solving real-world problems, there are still nonlinear programming and mixed integer programming with higher difficulty coefficients.
In other words, the Damo Academy's self-developed solver has not yet been developed to the extent of being completely independent.
Many people may think that the sudden change of hexagram behavior of this giant will bring a lot of impact to the Damo Academy, but in fact, this has become a reassurance in the hearts of this group of "solver fanatics":
This incident strengthened our determination to develop our own universal optimization solver!
On the one hand, the team actually started to prepare for the more challenging R&D such as nonlinear programming in early 2020, and accelerated the process after the outbreak of the "external threat".
On the other hand, after Alibaba Group heard about the results of the Damo Academy's self-developed solver, large and small business departments also threw olive branches to the Damo Academy, wanting to try it in their own scenarios.
This gives mindopt more valuable opportunities for practical operation, and to a certain extent, it also accelerates the process of moving towards the goal, and this process is still a win-win situation within Alibaba.
According to the public information released that year, Alibaba Cloud has saved hundreds of millions of yuan in cost after integrating the self-developed solver of the Damo Academy
And this is the first stage of mindopt's "four years of sharpening a sword" story. To sum it up in the words of Yin Wotao:
At this stage, we achieved the first place in technology through a single approach, which was a great encouragement to the team, and the internal requirements were improved accordingly.
The second phase, which runs from August 2020 to mid-2021, can be summarized as the evolution of a single approach into two approaches: in addition to supporting linear programming problems, mindopt can also address nonlinear quadratic programming problems.
At present, the DAMO Academy solver has been able to solve mainstream optimization problems, including linear programming, mixed integer linear programming, large-scale network flow, convex quadratic programming, semidefinite programming, and general nonlinear programming.
As for the third stage, that is, from mid-2021 to the present, Yin Wotao's team is not only challenging more difficult technologies such as mixed integer programming, but also integrating deep learning, reinforcement learning, and even popular large language models, focusing on a comprehensive development.
Moreover, in the two years of the second and third phases, judging from the evaluation results of the international list, the self-developed solver of the Damo Academy has also won the first place many times. However, for the results of the list, Yin Wotao thinks:
It's more like exam-oriented education, and if you are well prepared for the questions, your grades will naturally be goodPay more attention to the effect in the actual scene.
In fact, the Damo Academy solver has not only won the championship in power-related competitions at home and abroad for many times, but also proved itself in the actual power grid battle.
Last year, the DAMO Academy cooperated with the Power Dispatching and Control Center of China Southern Power Grid to release the "Power Dispatching Intelligent Decision-making Platform" to help the Southern Power Grid General Dispatcher achieve dispatching from 15 minutes to seconds, with an accuracy rate of experienced dispatchers.
In the end, after four years, the self-developed solver of the Damo Academy went through hundreds of links of careful research and development, actual testing, and 25 update iterations, and finally officially released its 1Version 0.
This also means that the self-developed solver of the Damo Academy is already a universal optimization solver that is comparable to the world's first-class level and can be assured to "get on the job".
Four years to sharpen a sword, but not yet to the peak.
Nowadays, the latest strength of the self-developed solver of the DAMO Academy has also been recognized by the domestic high-level authority.
Moreover, it is worth mentioning that the basic solver used in the second prize of this competition also uses the technology opened up by the Damo Academy's self-developed solver, and then "fine-tuned" it is made in the power scene based on its own experience.
So is the current Damo Academy's self-developed solver already at its peak?
To this question, Yin Wotao modestly replied:
It can be said that it is the first echelon of general optimization solvers, but it cannot be said to be at the top.
First of all, with the continuous acceleration of the digitalization process in China, more and more large-scale scenarios need to involve intelligent decision-making and the optimization solver behind it.
In this process, it is precisely in response to the saying that "practice is the only criterion for testing truth", and only by constantly trying, correcting mistakes and improving the cycle can we truly improve our ability.
Secondly, in the process of talking about the old foreign solver giants, Yin Wotao also said frankly:
They need to learn their ability to quickly identify patterns by observing the evolution of product forms. As well as in the calculation of input-output ratio and risk control, it is also necessary to refer to some successful foreign enterprises.
In addition, Wang Mengchang believes that it is also necessary to learn from them the spirit of focusing and persevering in one thing for ten years.
As for the technical difficulties to be broken through in the next step of the self-developed solver of the Damo Academy, Yin Wotao said:
The threshold for use should be lowered. How to make the process more automated is the key. The rapid development of large models is a good opportunity.
For example, combined with the actual needs of China's industrial scenarios, the DAMO Academy's self-developed solver has successively launched its own modeling language, parameter tuner, and optimization platform. In August this year, we built a large model for decision-making and reasoning, and launched a "AI optimization engineer" Mindopt Copilot.
For users in various industries such as energy, cloud computing, e-commerce, finance, etc., which the Damo Academy's self-developed solver now serves, they do not need to understand complex mathematical or programming knowledge, and directly use natural language to ask questions, and the "AI optimization engineer" will automatically convert the problem into a mathematical model and calculate the best answer.
This belongs to the half of the story that "the Damo Academy must do what others can't do".
In the longer run, the story of "four years of sharpening a sword" from a demand as a starting point of mindopt also reminds people of the history of computer development.
It was also because Babbage proposed the differential machine and the analysis machine in order to simplify the calculation, and ADA realized that the processing power of numbers could be used for any form of information, so that the seeds of the digital age could blossom and bear fruit a hundred years later.
The progress of science and technology requires not only the creative ideas of countless visionary people, but also countless small progresses.
It is worth looking forward to what kind of unexpected results the seeds of the domestic general solver sown by the Damo Academy will be able to produce in the future.