Clock-Stopped Workers for Distributed LP Relaxations That Will Be Rounded

Many hard discrete problems, such as choosing which facilities to open or which bids to accept, are solved in practice in two steps. First, the yes/no decisions are relaxed into fractions between 0 and 1, which turns the problem into a linear program (LP), an optimization with a linear objective and linear constraints that can be solved efficiently. Then the fractional answer is rounded back to a discrete one. When the LP is too large for one machine, it is split across workers. Synchronous splitting then runs only as fast as the slowest worker, the "straggler." This proposal argues that two habits are wasteful here. The first is solving the relaxation to very high precision, often $10^{-8}$. The second is making every worker reach the same precision. The rounding step adds its own error, which is usually far larger than $10^{-6}$. Precision below that floor cannot change the final discrete answer.

The idea in two sentences is this. Give every worker a fixed wall-clock deadline instead of a precision target, so a slow worker returns a looser but certified partial answer rather than stalling everyone or being thrown away. Then stop the whole solve once the certified LP error falls below the measured noise floor of the rounding step. Whether this works is an empirical question about wall-clock time to a good integer solution. The literature has not measured it: the rounding papers in this area are largely theoretical, and the scalable LP solvers are single-node.

Core Claim

The setting is block-structured LPs. Each worker owns a group of variables with local constraints, such as one region's facilities or one agent's assignments. A small set of shared constraints couples the groups, such as a global budget or capacity. The standard tool is Lagrangian dual decomposition. A coordinator holds prices $\lambda$ on the shared constraints, each worker solves its own block given those prices, and the coordinator adjusts prices from the workers' answers.

We add a small quadratic term $\frac{\mu}{2}\|x_i\|^2$ to each block. This makes the price-adjustment problem smooth. If worker $i$ returns a block solution whose own optimality gap is at most $\varepsilon_i$, the error it injects into the coordinator's price gradient is bounded by

$$\|e_i\| \le \|D_i\|\sqrt{2\varepsilon_i/\mu},$$

where $D_i$ is the worker's slice of the shared constraint matrix. The bound follows because the regularized block objective is $\mu$-strongly convex. Every worker can compute $\varepsilon_i$ locally from its own primal-dual gap, so each error is certified, not guessed.

The claim has two parts.

First, deadline truncation with warm starts produces errors that shrink on their own. Under a fixed per-iteration deadline $T$, each worker resumes from its previous block solution. Its error after the deadline is roughly its leftover error, plus the amount the prices moved, times a contraction factor $\rho_i^{s_i T}$. Here $s_i$ is the worker's speed and $\rho_i$ the inner solver's per-step contraction. As the prices settle, the errors of slow workers shrink with them. We conjecture this is enough for the summable-error condition $\sum_k \|e_k\| < \infty$ that keeps inexact methods convergent (New inertial proximal gradient methods). It should hold whenever the coordinator's price iterates converge fast enough. So stragglers become a source of bounded, decaying inexactness, not delay.

Second, a stopping rule tied to rounding. Dependent rounding schemes, such as swap rounding within each block, preserve each variable's expected value. The expected objective of the rounded solution therefore equals $c^\top x$ at the fractional point. The certified total gap bounds how far that is from the LP optimum. We stop once the certified gap falls below a fraction $\eta$ of the empirical rounding loss, which is estimated from a handful of rounding samples taken during the solve.

Relation to Prior Work

Several papers motivate the deadline-based inexact oracle, and none of them puts per-worker precision under clock control.

  • IPLD decomposes large convex problems into inexactly solved worker subproblems. Its coordinator waits at a synchronous barrier, and its output is fractional with no rounding. It does report that its results are insensitive to subproblem tolerance below $10^{-4}$, which is early evidence for our noise-floor thesis.
  • Local ADA treats $K$ local steps as an inexact dual gradient. $K$ is fixed and shared across workers, so slow workers still gate each round.
  • The accelerated fixed-point method with delayed inexact oracles models delay and inexactness abstractly. It does not tie the error to a truncated inner solver, and it is tested on a matrix game and MNIST, not on LPs.
  • Inexact first-order primal-dual algorithms supplies the error-decay schedules we compare our self-generated decay against.

Straggler work constrains the design.

  • Ringmaster ASGD achieves optimal time by discarding stale updates, but assumes identical data across workers. In a block LP, dropping a worker drops its constraints.
  • Rescaled ASGD shows that uneven worker speeds bias the solution toward fast workers. That is exactly the failure we must avoid in the coupling constraints.
  • ACPD and ARock proceed without waiting for everyone. ACPD acts once a subset of workers has reported. ARock lets workers update shared coordinates without locks. Both assume exact local operators, and both target continuous learning objectives with no feasibility requirement. - Delay-adaptive step sizes rescale steps by observed delay. Our analogue rescales by certified error.

The method's components come from two places. The LP machinery comes from PDLP, which serves as both the inner block solver and the centralized reference. The rounding comes from the dependent-rounding line: swap/pipage rounding with contention resolution, KPR, and laminar dependent rounding for facility location. All of these assume an exact fractional input, and several have no experiments at all. That is the empirical gap this work fills: what happens when the input is only approximately feasible.

Research Program

We will build a coordinator–worker solver. Each worker runs warm-started PDLP-style restarted primal-dual iterations on its regularized block. It stops at a wall-clock deadline and reports its block solution and certified gap $\varepsilon_i$. The coordinator takes an accelerated price step and weights each worker's contribution by its certified error bound. It maintains a running certified gap for the whole problem.

Every few rounds, the coordinator also draws a few block-wise swap roundings of the current fractional point. It measures their objective loss and coupling violation and applies the stopping rule. Coupling violations left after rounding are fixed by a greedy repair, and the cost of that repair is reported separately so it cannot hide quality loss.

The theory will be modest and checkable. We will state a convergence result for warm-started deadline truncation under linear inner convergence, together with the expected-value bound for the stopping rule. The theory exists to predict which instances benefit, namely those where rounding loss is large relative to the precision being chosen. It is not meant to be the main contribution.

Baselines

Synchronous barrier. This is the naive reference. Every worker solves its block to the same tolerance and everyone waits for the slowest. This is IPLD's architecture, run with PDLP as the inner solver. It shows the cost of stragglers with no mitigation.

Centralized PDLP solved to high precision, then dependent rounding. This is the strongest existing method on the LP side. PDLP reports solving 283 of 383 MIPLIB 2017 relaxations to high accuracy, against 50 for plain primal-dual hybrid gradient. It also reports a 6.3x geometric-mean speedup over SCS and a $10^7$-node PageRank LP solved in 5.4 hours. We run it on one node with all of that node's cores, using the same rounding and repair code. To beat it, we must reach a rounded solution of equal objective and equal violation in less wall-clock time on instances that fit in memory. On instances that do not fit, we must produce any competitive solution at all.

Centralized PDLP at loose tolerance. The same solver is run at $10^{-3}$ and $10^{-4}$. This isolates whether the rounding-aware stopping rule adds anything beyond "use a loose tolerance."

Drop-straggler and partial-participation variants. These are a Ringmaster-style staleness cutoff and an ACPD-style rule that updates once $B$ of $K$ workers report. They get the same deadline budget. We expect them to show measurable coupling violation and bias toward fast workers.

Fixed-$K$ inner steps. All workers take the same number of inner steps, as in Local ADA. Comparing this to our deadline rule tests whether letting precision vary by worker matters.

ARock-style asynchronous updates. These run directly on the primal-dual operator of the full LP, without decomposition.

Ablations. Deadline truncation is run with and without warm starts. The stopping rule is run with and without rounding samples. Block swap rounding is compared against independent rounding.

Integer reference. For instances small enough, SCIP or Gurobi supplies the integer optimum, so we can report true optimality gaps. Distributional MIPLIB reports a SCIP primal-dual integral of 20.0 on its easiest Optimal Transmission Switching tier, which serves as a calibration point.

All methods share the same hardware, the same injected straggler traces, and the same tuning budget, a fixed number of configurations per method. We found no reported result on Lacuna for end-to-end rounded-solution quality from any distributed or inexact LP solve. The comparison against centralized PDLP is therefore new, not a re-run.

Why not just…?

Why not just run centralized PDLP with a loose tolerance and round? This is the real threat. If an instance fits on one machine, a loose centralized solve may match or beat us outright. The loose-tolerance PDLP baseline settles this directly. If it wins on every instance that fits in memory, we will report that honestly. The contribution then narrows to two things: the stopping rule, which chooses the tolerance per instance instead of by hand, and the regime where problems are naturally distributed or too large for one node. PDLP's own memory-scale results and IPLD's report that SDPT3 ran out of memory suggest that regime is real.

Why not just drop the stragglers? Ringmaster's optimality depends on identical data across workers. In a block LP, the dropped worker owns constraints. Rescaled ASGD documents the resulting bias toward fast workers in learning problems. Our drop-straggler baseline will measure the analogous coupling violation and repair cost directly.

Why not just use lock-free asynchronous updates on the whole LP? ARock's 26.1x versus 1.3x speedup on news20 shows that asynchrony is powerful. However, it needs shared memory and exact coordinate operators. Its stale reads also blur the budget sums that dependent rounding preserves. It is included as a baseline. If it reaches equal rounded quality faster on a single shared-memory node, our method is justified only in the distributed-memory setting.

Why not just round independently and repair? Independent coin flips let budget sums drift randomly. ProbFair and the KPR analysis both motivate dependent schemes for this reason. The rounding ablation will quantify how much extra repair independent rounding needs once the input is inexact.

Proposed Experiments

Testbeds. We use three kinds of instances:

  • Block-angular instances generated at controlled scale: multi-region capacitated facility location, generalized assignment, and multi-knapsack median.
  • Set Covering and Combinatorial Auction domains from Distributional MIPLIB across its hardness tiers, with blocks recovered by constraint-graph partitioning.
  • Additional same-distribution instances from G2MILP.

We also run the solver alone, without rounding, on MIPLIB 2017 LP relaxations. This checks that the deadline rule does not break convergence on structure we did not choose.

Straggler models. We inject three kinds of slowdown: a single 10x-slow worker, matching ACPD's test; heavy-tailed per-round slowdowns; and transient bursts.

Metrics. We measure:

  • wall-clock time to a rounded solution within 1% and 5% of the best known integer value;
  • coupling violation before and after repair;
  • certified LP gap at stopping;
  • primal-dual integral.

Decisive checks. There are three.

  1. Certified block errors under deadline truncation should decay at the predicted rate when warm-started and fail to decay without warm starts. If they plateau instead, the core mechanism is wrong.
  2. Rounded quality should saturate well before $10^{-6}$ LP precision on most instances, consistent with IPLD's insensitivity below $10^{-4}$. If it does not, the noise-floor thesis fails.
  3. Under a 10x straggler, our method should match the synchronous barrier's rounded quality in substantially less time, without the coupling violations of drop-straggler variants. We report wherever centralized loose-tolerance PDLP is faster.