Huawei Cloud and HUST Team Dual Champions in DIMACS Implementation Challenge
Apr 18, 2022
At its recent 12th Implementation Challenge on Vehicle Routing Problems, DIMACS awarded multiple medals to the Huawei Cloud-HUST joint team. Teaming up with Huazhong University of Science and Technology (HUST), the Huawei Cloud Alkaid Scheduling Algorithm Team were the only participants to win more than two Gold medals, and the team with the most top-3 placings overall with one Silver and two Bronze medals. This continues their stellar track record after two championships at the OCP and USCP tracks of the GECCO 2020 Competition and more than 50 PDPTW world records.
The Challenges were started by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) in 1990. Dedicated to promoting algorithm research for major application problems, they are renowned and respected international computing algorithm competitions. Previous Challenges include the traveling salesman problem, graph partitioning problem, network flow and matching problem, shortest path problem, semidefinite and related optimization problems, which are the most difficult and challenging topics in the field of computational complexity theory and operations optimization. Being both theoretical and practical, the current Challenge attracted more than 50 top research teams from around the world, representing both enterprise and academia from countries such as France and Canada. With that many famous scholars in the field participating, the medal placements are especially hard to win.
The 12th DIMACS Implementation Challenge is about the Vehicle Routing Problem (VRP). As a typical NP-hard problem, the VRP has been continuously studied by researchers for more than half a century. As with previous Challenges, DIMACS chose one of the most challenging subjects in the field to solve and a subject of great theoretical and practical value even today.
At the core of the VRP problem is finding the optimal path in a graph network that satisfies a series of constraints. To be considered optimal, the path must minimize time, cost, and other factors. These objectives must be solved with certain constraints and limited resources. VRP is used in many fields, such as resource scheduling, logistics, and route planning. Cloud computing also requires complex constraint optimization. A typical scenario would be optimizing cloud resource utilization and maximizing tenant service quality under constraints such as capacity, topology, and power. This is a key issue and competitiveness factor for operations capability and customer service quality on the cloud platform. At the scale of the public cloud, a 1% increase in resource efficiency may save tens of millions of dollars at the same user service quality. Huawei Cloud invests heavily in optimization algorithm research and accumulating practical experience, and participating in this Challenge reflects this commitment.
The Huawei Cloud Alkaid scheduling algorithm team is led by Huawei's Young Talents and Doctorate professionals. Highly experienced in algorithm design and implementation and previous winners in the ACM competition, they work closely with the HUST team, headed by Professor Lv Zhipeng, on scheduling optimization to tackle multiple complex optimization problems in Huawei Cloud's scheduling scenarios. Professor Lv's team is also experienced in optimization algorithms and a multiple heavyweight competition winner. Building on the Alkaid Cloud Brain, the Huawei Cloud team's intelligent decision optimization engine framework is tailored for cloud scenarios. The flexible and scalable algorithm policy libraries in this framework adapt to changing cloud scenarios and solution requirements, especially when requiring large-scale optimization under complex constraints. At the Challenge, the team designed a new neighborhood search operator and perturbation mechanism for the VRP problem based on the solution engine framework and algorithm strategy library, and boosted the efficiency of neighborhood search using a lazy loading cache mechanism. The team's winning algorithm beat the runner up by more than 5% on average and more than 10% in some cases, remarkable results considering such fierce competition and the challenge of solving a 50-year-old problem.
In the future, Huawei Cloud will optimize the decision-making, optimization, and solution capabilities of the Alkaid Cloud Brain for full competitiveness in all-domain scheduling, capacity management, SLA assurance, and other scenarios. Huawei Cloud strives to provide infrastructure with the ultimate performance, rock-solid stability, diversified computing power, and cloud-edge-device collaboration needed by various industries. In addition, Huawei Cloud will continue to make full use of full-stack innovation to explore all-domain scheduling and software-hardware collaboration in the distributed cloud so its enterprise customers enjoy a lean, compelling cloud experience.