Abstract
This paper introduces two novel decomposition-based methods for solving two-block mixed-integer linear programs (MILPs) to global optimality. By leveraging the separable structures inherent in many large-scale optimization problems, the proposed methods solve a sequence of lower-dimensional MILPs rather than tackling the monolithic problem directly. The first approach is based on an $\ell_1$-augmented Lagrangian method (ALM), while the second utilizes a modified alternating direction method of multipliers (ADMM). Both methods utilize non-convex cuts to handle discrete variables and are designed to exploit parallel architectures. Numerical experiments demonstrate that these methods significantly outperform state-of-the-art solvers like Gurobi on structured MILPs, particularly as problem size and complexity increase.
Introduction
Mixed-Integer Linear Programming (MILP) is a fundamental tool in industrial optimization, underpinning critical operations in power grid scheduling, supply chain logistics, and telecommunications. However, as these systems grow in complexity, the resulting MILPs often become computationally intractable for general-purpose solvers due to the exponential growth of the search space.
Many real-world MILPs exhibit a "block-angular" structure, characterized by several independent sub-problems linked by a small set of coupling constraints. While traditional decomposition techniques like Benders Decomposition are designed to exploit this structure, they often struggle with the non-convexity of integer variables, leading to slow convergence or failure to reach the global optimum. This research addresses these limitations by introducing decomposition schemes that maintain global convergence guarantees through the use of sharp penalty functions and non-convex approximations.
Methodology
The authors propose two primary algorithmic frameworks designed for "two-block" MILPs, where variables can be partitioned into two sets coupled by linear constraints.
1. AUSAL (Alternating Update for the Sharp Augmented Lagrangian)
The AUSAL method is an Augmented Lagrangian Method (ALM) that employs an $\ell_1$ penalty, often referred to as a "sharp" penalty. Unlike the squared $\ell_2$ penalties common in continuous optimization, the $\ell_1$ penalty provides "exact penalization." This ensures that for a sufficiently large penalty parameter, the solution to the penalized subproblem is identical to the solution of the original MILP.
AUSAL operates via a double-loop structure. The inner loop solves subproblems using Reverse Norm Cuts—specialized non-convex minorants that approximate the problem's value function more tightly than standard linear cuts. This allows the algorithm to navigate the discrete search space more effectively.
2. Modified ADMM
The second method adapts the Alternating Direction Method of Multipliers (ADMM) for discrete optimization. While standard ADMM is a staple of convex optimization, it typically lacks global convergence guarantees for MILPs. The authors overcome this by incorporating AL Cuts and specific update rules for dual variables. These modifications ensure that the algorithm converges to the global optimum even in the presence of integer constraints.
Both methods are highly parallelizable. In the presence of block-angular structures, the $x$-variables can be updated by solving multiple independent subproblems simultaneously, while the $z$-variables (the coupling block) are updated using the generated non-convex cuts.
Experimental Evaluation
The effectiveness of the proposed methods was tested against Gurobi 9.5.2 across three distinct classes of structured MILPs:
- Investment Planning Problems: These benchmarks involve capacity expansion decisions under uncertainty, a staple of stochastic programming.
- Stochastic Server Location Problems (SSLP): Sourced from the SIPLIB collection, these problems model the optimal placement of servers to satisfy uncertain client demand.
- Structured Random MILPs: To test the limits of scalability, the authors generated large-scale synthetic problems featuring up to 500 independent blocks tied by coupling constraints.
Key Results
The numerical experiments revealed several significant advantages of the decomposition approach:
- Computational Speed: On difficult variants of the Investment Planning problem, the proposed methods were approximately 55% faster than Gurobi.
- Scalability: In tests involving random MILPs with 500 blocks, Gurobi failed to find even a feasible solution within the 1800-second time limit. Conversely, both the ALM and ADMM decomposition methods reached the global optimum in 5 to 7 minutes.
- Feasibility and Robustness: The decomposition approach proved exceptionally robust at identifying high-quality feasible solutions in problems where coupling constraints typically make the search for feasibility difficult.
Discussion and Insights
The success of these methods stems from two primary theoretical pillars. First, the $\ell_1$ norm enables a form of "strong duality" for MILPs. This eliminates the "duality gap" that usually complicates discrete optimization, provided the penalty parameter is sufficiently high. Second, the use of non-convex cuts (Reverse Norm and AL cuts) provides a much tighter approximation of the underlying discrete value functions compared to the linear cuts used in Benders Decomposition. By "shaping" the search space more accurately, these cuts lead to faster global convergence.
Furthermore, the research highlights the benefit of "exploiting topology." While a general-purpose solver may struggle within a single, massive branch-and-bound tree, the decomposition approach effectively solves many smaller branch-and-bound trees in parallel, significantly reducing the total computational burden.
Conclusion
This paper demonstrates that decomposition methods, when combined with sharp penalty functions and non-convex cuts, offer a powerful alternative to monolithic solvers for structured MILPs. While the current implementation faces some challenges—such as the increasing complexity of the master problem as more cuts are added—the results on large-scale problems are promising. Future work may focus on instance-specific parameter tuning and the implementation of these algorithms in fully distributed environments to further unlock their parallel processing potential.
Summary updated