Distributed optimization for mixed integer linear programming on unbalanced directed graphs with row stochasticity

This paper investigates a distributed optimization approach for solving mixed integer linear programming (MILP) problems with a coupling constraint over unbalanced directed networks. The proposed method combines linear programming (LP) relaxation with a dual decomposition technique that uses row stochasticity of the network's weight matrix. A subgradient scaling mechanism is introduced to compensate for the estimation bias arising from asymmetric communication links. We prove that the proposed algorithm guarantees the feasibility of the solution in a finite number of iterations and provide a finite-time suboptimality bound. Numerical experiments also show that the local estimates converge to a feasible and near-optimal solution.