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.
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:
- The Leader: Primarily responsible for Objective I (maximizing fillrate).
- 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.
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