Improving ADMM-based optimization of Mixed Integer objectives

摘要

We consider a class of mixed integer programs where the problem is convex except for a vector of discrete variables. Two methods based on the Alternating Direction Method of Multipliers (ADMM) are presented. The first, which has appeared in the recent literature, duplicates the discrete variable, with one copy allowed to vary continuously. This results in a simple projection, or rounding, to determine the discrete variable at each iteration. We introduce an alternate method, whereby part of the objective is replaced by a new variable instead. When the objective satisfies a certain condition, this allows the update of the discrete variables to be handled separately for each one, thus maintaining linear complexity of this update, while incorporating some of the objective into the update. Initial comparisons on examples for which both methods are applicable show that the latter exhibits clear improvements in both performance and run-time.