English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We solve large-scale mixed-integer linear programs (MILPs) via distributedasynchronous saddle point computation. This is motivated by the MILPs beingable to model problems in multi-agent autonomy, e.g., task assignment problemsand trajectory planning with collision avoidance constraints in multi-robotsystems. To solve a MILP, we relax it with a nonlinear program approximationwhose accuracy tightens as the number of agents increases relative to thenumber of coupled constraints. Next, we form an equivalent Lagrangian saddlepoint problem, and then regularize the Lagrangian in both the primal and dualspaces to create a regularized Lagrangian that isstrongly-convex-strongly-concave. We then develop a parallelized algorithm tocompute saddle points of the regularized Lagrangian. This algorithm partitionsproblems into blocks, which are either scalars or sub-vectors of the primal ordual decision variables, and it is shown to tolerate asynchrony in thecomputations and communications of primal and dual variables. Suboptimalitybounds and convergence rates are presented for convergence to a saddle point.The suboptimality bound includes (i) the regularization error induced byregularizing the Lagrangian and (ii) the suboptimality gap between solutions tothe original MILP and its relaxed form. Simulation results illustrate thesetheoretical developments in practice, and show that relaxation andregularization together have only a mild impact on the quality of solutionobtained.

Technical Report: Distributed Asynchronous Large-Scale Mixed-Integer Linear Programming via Saddle Point Computation