Mix-CALADIN: A Distributed Algorithm for Consensus Mixed-Integer Optimization

1. Problem Statement

The paper addresses Distributed Consensus Mixed-Integer Programming (MIP) problems. Specifically, it focuses on scenarios where $N$ agents aim to minimize a sum of local objective functions subject to a global consensus constraint, where decision variables include both continuous components and Boolean (0/1) variables.

The problem is formulated as:
$$\min_{x_i, z} \sum_{i=1}^N f_i(x_i) \quad \text{s.t.} \quad x_i = z, \quad \forall i \in \{1, \dots, N\}$$
where $x_i = [y_i^\top, b_i^\top]^\top$, with $y_i \in \mathbb{R}^{n_c}$ (continuous) and $b_i \in \{0, 1\}^{n_d}$ (Boolean). The global variable $z$ must satisfy the same structure.

Key Challenges:

• Scalability: Centralized MIP solvers (e.g., Branch-and-Bound) struggle with large-scale distributed problems due to memory and communication bottlenecks.
• Solver Dependency: Existing distributed algorithms often require agents to solve local MIP subproblems using external solvers, which limits real-time applicability and scalability.
• Convergence Guarantees: Many heuristic approaches (e.g., rounding integer variables in ADMM) lack rigorous convergence guarantees, especially for nonconvex problems.

2. Methodology: Mix-CALADIN

The authors propose Mix-CALADIN, a novel two-stage distributed algorithm based on the Consensus Augmented Lagrangian Alternating Direction Inexact Newton (CALADIN) framework. The algorithm operates without relying on local mixed-integer solvers.

Stage I: Continuous Relaxation

• Objective: Solve a relaxed version of the problem where Boolean constraints are temporarily removed ($b_i \in [0, 1]$).
• Mechanism: The standard CALADIN algorithm is applied. Agents minimize their local augmented Lagrangian, compute gradients and Hessian approximations, and a coordinator solves a consensus Quadratic Program (QP) to update the global variable $z$ and dual variables.
• Outcome: This stage provides a deterministic lower bound for the original problem and yields a high-quality initial point ($\tilde{z}^*$) for Stage II.
• Convergence: Inherits CALADIN's guarantees: global linear convergence for convex problems and local linear convergence for nonconvex problems.

Stage II: Boolean Enforcement

• Objective: Drive the relaxed continuous variables toward Boolean values (0 or 1) while maintaining consensus.
• Mechanism: A bi-level optimization framework is employed at the coordinator:
  • Inner Loop: Agents compute gradients at the current global point $z^{[k]}$. The coordinator solves a convex QP with box constraints ($0 \le z_d \le 1$) and a linear penalty term $\alpha(1 - 2z_d^{[k]})^\top z_d$. This term approximates the nonconvex penalty $\alpha(1-z_d)^\top z_d$ to ensure numerical stability.
  • Outer Loop: If the Boolean constraint violation (measured by $(1-z_d)^\top z_d$) is above a threshold, the penalty parameter $\alpha$ is increased ($\alpha \leftarrow \beta \alpha$), and the inner loop restarts.
• Key Innovation: Instead of using a nonconvex penalty directly (which causes instability), the algorithm uses a convex linear approximation of the penalty term at each iteration, inspired by previous work on linear complementarity problems.

3. Key Contributions

1. Solver-Free Distributed MIP: Mix-CALADIN is the first distributed algorithm to solve mixed-integer consensus problems with rigorous convergence guarantees without requiring agents to invoke local MIP solvers.
2. Two-Stage Architecture:
   • Stage I leverages the efficiency of CALADIN on continuous relaxations to provide a robust initialization.
   • Stage II introduces a specialized penalty-based mechanism to enforce Boolean constraints, handling both convex and nonconvex landscapes.
3. Theoretical Guarantees:
   • Proves global linear convergence for convex problems in Stage I.
   • Proves local linear convergence for nonconvex problems in Stage I.
   • Proves convergence for Stage II under the mild assumption that objective functions are Lipschitz continuous, provided the penalty parameter $\rho$ exceeds the Lipschitz constant.
4. Numerical Robustness: By using a convex approximation for the Boolean penalty term, the algorithm avoids the numerical instability often seen in Big-M methods or direct rounding heuristics.

4. Numerical Results

The authors validated Mix-CALADIN using MATLAB on two test cases:

1. Nonconvex Sensor Localization: A problem with mixed-Boolean constraints and nonconvex terms.
2. Convex Optimization: A benchmark problem compared against projection-based ADMM.

Findings:

• Convergence Behavior: Stage I demonstrated linear convergence for both convex and nonconvex cases, aligning with theoretical predictions.
• Stage II Performance: The algorithm successfully converged to feasible Boolean solutions. The energy function profiles showed the characteristic "staircase" pattern where the outer loop increases $\alpha$, temporarily raising the energy, followed by the inner loop reducing it.
• Comparison: In the convex case, Mix-CALADIN outperformed the projection-based ADMM (a heuristic baseline). While ADMM converged to a local minimum, Mix-CALADIN achieved a superior solution quality with theoretical convergence guarantees.
• Efficiency: The two-stage approach allowed for rapid initialization (Stage I) followed by precise refinement (Stage II), proving effective for large-scale distributed settings.

5. Significance and Impact

• Bridging the Gap: This work bridges the gap between distributed optimization and mixed-integer programming, a domain where rigorous distributed solutions have been scarce.
• Practical Applicability: By eliminating the need for local MIP solvers, the algorithm is more scalable and suitable for real-time applications in areas like sensor network design, wireless antenna selection, and microgrid control.
• Theoretical Foundation: It establishes a new benchmark for convergence analysis in distributed mixed-integer optimization, moving beyond heuristics to provide mathematically guaranteed solutions for both convex and nonconvex problems.

Future Work: The authors plan to extend these techniques to resource-allocation variants, analyze the convergence rate of Stage II more deeply, and adapt the framework for open network settings where topology changes dynamically.