Distributed Optimization for Convex Mixed-Integer Programs based on Projected Subgradient Algorithm

Convex Mixed-Integer Program (MIP) has received extensive attention due to its wide applications. This paper proposes a distributed optimization algorithm based on Projected Subgradient Algorithm (PSA) to solve general convex MIPs. We first decouple the feasible region as the intersection of multiple local convex constraints and the relaxed integrality constraints. Then an auxiliary variable vector is assigned to each decoupled constraint with a consensus constraint to keep equivalence. A Distributed Projected Subgradient Algorithm (DPSA) is proposed to solve the reformulated problem. The updates of the auxiliary variables associated with the convex local constraints as well as the integrality constraint are implemented in a parallel way, followed by the gossip step to drive all auxiliary variable sets into consensus. While this algorithm applies to general convex MIPs, special attention is paid to quadratic and linear constraints in order to obtain a closed-form solution for each subproblem. While convergence of such DPSA for convex problems has been studied, the presence of the integrality constraint makes it inapplicable. Consequently, convergence of the proposed DPSA and properties at the converging point under certain assumptions is presented. Numerical results on maximum clique problem are provided to sustain the effectiveness of the proposed algorithm.