Distributed Optimization for Overconstrained Problems and its Application

Contents

Distributed optimization requires the optimization of a global objective function that is distributed among a set of autonomous, communicating agents and is unknown by any individual agent. One major mode of attack has been to treat optimization as an overconstrained distributed satisfaction problem and exploit existing distributed constraint satisfaction techniques. These approaches require incremental searches with periodic synchronization operations and lack any guarantees of optimality. This paper presents Adopt, an asynchronous, distributed algorithm for overconstrained settings. The fundamental ideas in Adopt are to represent constraints as discrete functions (or valuations) --- instead of binary good/nogood values --- and to use the evaluation of these constraints to measure progress towards optimality. In addition, Adopt uses a sound and complete partial solution combination method to allow non-sequential, asychronous computation. Finally, Adopt is not only provably optimal when given enough time, but allows solution time/quality tradeoffs when time is limited. We apply Adopt to a real-world overconstrained distributed resource allocation problem and we present empirical results comparing Adopt to previous approaches.