2022/04/30 by Mohammad Javad Feizollahi, Feizollahi, Mohammad Javad
Business, Management and Accounting · Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Optimization and Search Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2205.00356
openalex publication_date 2022/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose two exact distributed algorithms to solve mixed integer linear programming (MILP) problems with multiple agents where data privacy is important for the agents. A key challenge is that, because of the non-convex nature of MILPs, classical distributed and decentralized optimization approaches cannot be applied directly to find their optimal solutions. The proposed exact algorithms are based on adding primal cuts and restricting the Lagrangian relaxation of the original MILP problem. We show finite convergence of these algorithms for MILPs with only binary and continuous variables. We test the proposed algorithms on the unit commitment problem and discuss its pros and cons comparing to the central MILP approach.