Contributed by Institute of Automation, Chinese Academy of Sciences

Quantum Bit | Public Account QbitAI

Solve the stochastic programming problem in just 15 seconds, 1440 times faster than traditional methods!

New research from the Institute of Automation of the Chinese Academy of Sciences has made new breakthroughs in such problems using GCN, and the paper has been selected for the top AI conference ICML 2024.

This means that efficient decision-making can be achieved even under uncertain conditions.

Decision-making under uncertainty is an important type of decision-making problem, which requires decision makers to fully consider all random situations and make the most reasonable decision.

In the field of mathematics, a commonly used solution is stochastic programming, which is to include random variables in the mathematical programming model.

Among them, Two-Stage Stochastic Programming (2SP) is widely used as an effective method to model such decision problems.

This achievement of the Institute of Automation of the Chinese Academy of Sciences, the HGCN2SP model (HGCN stands for Hierarchical Graph Convolutional Network), is a combination of the 2SP method andpictureCombined with convolutional networks, the model can be used to solve such problems more efficiently.

The first author of the paper is Wu Yang, a doctoral student at the institute, and Researcher Zhang Yifan is the corresponding author.

What is two-stage stochastic programming?

The basic idea of ​​stochastic programming is to transform the possible future situations of the problem into several sample scenarios, then optimize each sample scenario, and finally integrate the optimization results of all scenarios to guide current decision-making.

Its application areas include supply chain management, financial investment, energy scheduling, disaster emergency management, etc.

The two-stage stochastic programming, as the name suggests, divides this process into two stages.

Specifically, these two stages require making macro and micro decisions respectively to minimize total costs or maximize total benefits.

Decisions in the first stage are made before uncertainty emerges, and the goal is to optimize the initial decision to adapt to a variety of possible future situations.

Decisions in the second phase are made after uncertainty emerges, and adjustments are made based on the decisions in the first phase and what actually happens to optimize the overall outcome.

Through the 2SP model, decision makers need to fully consider the impact of different possible scenarios during the decision-making process, so as to improve the robustness and flexibility of decisions and make more scientific and efficient decisions.

For example, suppose we want to select some from 10 candidate locations to build warehouses to meet the needs of 20 surrounding areas.

The first stage requires decisions about which of the 10 candidate sites should be selected;

The second stage is to determine the distribution relationship between warehouses and regions. At this time, the number of decision variables is as high as 200 (i.e., whether warehouse i distributes to region j).

△Image generated by DALL·E

Mathematically, the 2SP problem is usually expressed as:

Among them, Q(x,ξ) represents the second-stage optimization problem given the first-stage decision x and scenario ξ, and its form is:

In actual solutions, N scenes are generally sampled to calculate the corresponding Q values ​​to approximate the expectation.

Obviously, the larger N is, the more reliable the approximation is. However, as the number of scenarios increases, the problem size expands rapidly, which will greatly increase the solution time.

Let’s use the warehouse site selection problem to illustrate. In order to make better site selection decisions, we need to take into account uncertain factors such as demand, weather, flow of people, and transportation. The change of each factor corresponds to a scenario.

This means that it is necessary to sample N different scenarios extensively to simulate the real situation as closely as possible. At this time, the total number of decision variables in the second stage will be as high as 200N, making the solution time extremely long.

In fact, when N is 500, even using the most advanced commercial solver Gurobi, it takes at least 6 hours to make the optimal decision.

Traditional methods usually use random sampling or clustering techniques to select a small number of scenarios (such as 10 or 20) for approximate solutions. Although this reduces the time, the quality of the resulting decisions is often not ideal.

Based on this, the design idea of ​​the HGCN2SP model is to obtain accurate results as close as possible while reducing the number of sampling scenes.

Solving the 2SP problem with graph convolutional networks

The research team proposed the HGCN2SP model based on hierarchical graph convolutional network to solve the two-stage stochastic programming problem.

Specifically in terms of algorithm design, the team characterized the 2SP problem by constructing a hierarchical graph, where the bottom-level graph is used to characterize the characteristics of each scenario, while the top-level graph is used to characterize the relationship between scenarios.

Then, the hierarchical graph convolutional network (HGCN) is used to mine the embedding information of the bottom-level scene subgraphs and the structural information of the top-level scene space to extract the scene representation.

The attention-based decoder is used to select scenes in sequence, which can not only find representative scenes to simplify the problem, but also improve the selection of the initial basis when solving the problem by the simplex method by optimizing the arrangement order of the scenes, thereby significantly improving the solution time.

△HGCN2SP model framework

The team also combined reinforcement learning (RL) to comprehensively consider decision quality and solution time to optimize model parameters, significantly improving the efficiency and quality of problem solving.

In the above-mentioned warehouse location problem, although HGCN2SP only selected 10 scenarios, its decision result was only 1.7% different from the decision made by the Gurobi solver in 6 hours, and the solution time was only 15 seconds, which is equivalent to a speed increase of 1440 times, fully demonstrating the effectiveness of this method.

In addition, in the Network Design Problem (NDP) experiment, HGCN2SP achieved similar decision-making results in less than half the time of existing methods.

Especially in large-scale instances and a large number of scenarios, HGCN2SP still maintains strong generalization capabilities.

The proposal of HGCN2SP provides a new idea and tool for solving complex 2SP problems and has broad application prospects.

The research team plans to further optimize the model, reduce training costs, and explore its application in more practical problems.

Paper address:
https://openreview.net/forum?id=8onaVSFTEj