Accelerate the optimization of large-scale manufacturing planning using game theory

Hui‐Ling Zhen, Zhenkun Wang, Xijun Li, Qingfu Zhang, Mingxuan Yuan, Jia ZengComplex 2021 · DOI

Abstract

This paper studies a real-world manufacturing problem modeled as a bi-objective integer programming problem. Given the massive scale—often involving billions of variables—traditional heuristic algorithms and commercial solvers like Gurobi struggle to find efficient solutions. While decomposition methods are typically used for large-scale problems, they often require strict block structures that real-world data lacks. We propose a game-theory-based decomposition algorithm that treats objectives as players in a Stackelberg game. This approach narrows the search space and accelerates convergence. Experimental results on industrial datasets show our method outperforms Gurobi in both solution quality and scalability, particularly as problem size increases.

The Challenge of Billion-Scale Planning

In modern industrial manufacturing, planning requires balancing two primary, often competing, objectives: maximizing the order fillrate to satisfy customer demand and minimizing total operational costs (including production, inventory, and logistics). Mathematically, this is formulated as a bi-objective Integer Programming (IP) problem.

Commercial solvers like Gurobi are the industry standard but face significant limitations when decision variables reach the "billion-scale." A common strategy for handling such complexity is decomposition—partitioning a large problem into smaller sub-problems. However, traditional methods like Benders or Dantzig-Wolfe decomposition rely on a "strict block structure," where variables and constraints are neatly separated. Real-world manufacturing constraints are rarely so cooperative; they often overlap, creating "intersectional parts" that prevent standard decomposition techniques from functioning effectively.

Figure 3: Non-strict block structure illustrating intersectional parts between objectives and constraints.

Breaking the Block: A Game-Theoretic Approach

To address these non-strict structures, we introduce a game-based decomposition algorithm. Instead of solving the bi-objective problem as a single monolithic task, we reframe it as a Stackelberg game between two strategic players:

  1. The Leader: Primarily responsible for Objective I (maximizing fillrate).
  2. The Follower: Primarily responsible for Objective II (minimizing cost).

The algorithm operates through an iterative feedback loop. The Leader proposes an initial plan. The Follower then identifies the "best response" to this plan. A critical innovation in our method is the generation of heuristic constraints derived from the Follower’s response (often using the dual form of the sub-problem). These constraints are fed back to the Leader, effectively narrowing the search space for subsequent iterations. This mechanism allows the algorithm to handle messy, overlapping constraints without requiring the strict independence demanded by traditional decomposition.

Figure 6: The iterative game-based decomposition framework showing the interaction between Leader and Follower objectives.

Experimental Evaluation and Results

We evaluated the algorithm using real-world industrial datasets from Huawei Noah’s Ark Lab, ranging from "Million-scale" to "Billion-scale" (up to 66,000 items and 68 plants).

The results demonstrate two major advantages:

  • Solution Quality: The game-based approach consistently produced "Pareto-dominant" solutions, achieving higher fillrates at lower costs than Gurobi in nearly all test cases.
  • Scalability: While Gurobi may be faster on smaller, simpler problems, its computational requirements explode as scale increases. In our tests, moving from million-scale to billion-scale caused Gurobi’s runtime to increase by a factor of 1,682. In contrast, our game-based algorithm's runtime only increased by a factor of 517.

Conclusion and Future Work

By viewing optimization through the lens of game theory, we can decompose massive problems that were previously considered "untidy" for traditional methods. This approach not only provides a path to solving billion-scale industrial problems but also offers a more robust framework that is less sensitive to the exponential growth of data. Future research will focus on automating the selection of the "Leader" objective and extending this framework to broader supply chain challenges beyond manufacturing planning.

Summary updated

Abstract

Abstract This paper studies a real-world manufacturing problem, which is modeled as a bi-objective integer programming problem. The variables and constraints involved are usually numerous and dramatically vary according to the manufacturing data. It is very challenging to directly solve such large-scale problems using heuristic algorithms or commercial solvers. Considering that the decision space of such problems is usually sparse and has a block-like structure, we propose to use decomposition methods to accelerate the optimization process. However, the existing decomposition methods require that the problem has strict block structures, which is not suitable for our problem. To deal with problems with such block-like structures, we propose a game theory based decomposition algorithm. This new method can overcome the large-scale issue and guarantee convergence to some extent, as it can narrow down the search space and accelerate the convergence. Extensive experimental results on real-world industrial manufacturing planning problems show that our method is more effective than the world fastest commercial solver Gurobi. The results also indicate that our method is less sensitive to the problem scale comparing with Gurobi.
BibTeX
@inproceedings{zhen2021accelerate,
  author = {Hui‐Ling Zhen and Zhenkun Wang and Xijun Li and Qingfu Zhang and Mingxuan Yuan and Jia Zeng},
  title = {{Accelerate the optimization of large-scale manufacturing planning using game theory}},
  booktitle = {Complex},
  year = {2021},
  doi = {10.1007/s40747-021-00352-7},
}
Figure