COHDA

COHDA (Combinatorial Optimization Heuristic for Distributed Agents) is a fully distributed heuristic for the Multiple-Choice Combinatorial Optimization Problem (MC-COP). It requires no central coordinator — participants exchange solution candidates with their neighbours and converge through local search.

Problem Formulation

Each of the \(N\) participants independently selects exactly one schedule from a personal menu of \(M\) choices. The goal is to minimise the weighted L1 distance of the combined schedule sum to a target vector \(T\):

\[ \begin{align}\begin{aligned}\max_{x_{i,j}} \left(-\bigl\lVert T - \sum_{i=1}^{N}\sum_{j=1}^{M} U_{i,j}\cdot x_{i,j}\bigr\rVert_1\right)\\\text{s.t.}\quad \sum_{j=1}^{M} x_{i,j} = 1 \;\forall\, i,\quad x_{i,j}\in\{0,1\}\end{aligned}\end{align} \]

where \(U_{i,j} \in \mathbb{R}^m\) is the \(j\)-th schedule of participant \(i\).

How It Works

COHDA is a gossip-style algorithm:

  1. A start message carrying the target \(T\) is sent to one participant.

  2. On receiving a message, each participant updates its working memory — a view of the current best known system configuration — and applies local search to improve its schedule.

  3. If the working memory changed, the participant broadcasts an updated solution candidate to all its neighbours.

  4. The algorithm terminates when no participant can improve the objective any further (the system configuration stabilises).

Usage

>>> from distributed_resource_optimization import (
...     create_cohda_participant,
...     create_cohda_start_message,
...     start_distributed_optimization,
... )
>>> actor1 = create_cohda_participant(1, [[0.0, 1.0, 2.0], [1.0, 2.0, 3.0]])
>>> actor2 = create_cohda_participant(2, [[0.0, 1.0, 2.0], [1.0, 2.0, 3.0]])
>>> start = create_cohda_start_message([1.2, 2.0, 3.0])
>>> asyncio.run(start_distributed_optimization([actor1, actor2], start))
>>> actor1.memory.solution_candidate.perf < 0
True

Complete Example

>>> schedules_A = [[1.0, 0.0, 0.0, 0.0], [0.0, 1.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0]]
>>> schedules_B = [[2.0, 0.0, 0.0, 0.0], [0.0, 2.0, 0.0, 0.0], [0.0, 0.0, 0.0, 2.0]]
>>> actors = [
...     create_cohda_participant(1, schedules_A),
...     create_cohda_participant(2, schedules_B),
...     create_cohda_participant(3, schedules_A),
...     create_cohda_participant(4, schedules_B),
... ]
>>> start = create_cohda_start_message([3.0, 3.0, 1.0, 2.0])
>>> asyncio.run(start_distributed_optimization(actors, start))
>>> actors[0].memory.solution_candidate.perf < 0
True

Working Memory and Solution Candidates

Internally COHDA uses three data structures:

  • WorkingMemory — each participant’s current view of the world: target parameters, the best known system configuration, and the best known solution candidate.

  • SystemConfig — a mapping from participant IDs to their currently selected schedule.

  • SolutionCandidate — a proposed full system configuration together with its performance value (negative weighted L1 distance).

These types are exported and can be inspected after the algorithm runs.

Custom Performance Functions

By default COHDA uses a weighted L1 distance metric. Provide a custom performance function when creating a participant. The function receives a 2-D NumPy array (rows = participants, columns = time steps) and a TargetParams instance, and must return a float:

>>> from distributed_resource_optimization import create_cohda_participant
>>> def my_perf(cluster_schedule, target_params):
...     diff = target_params.schedule - cluster_schedule.sum(axis=0)
...     return -float(np.sqrt((diff ** 2).sum()))
>>> actor = create_cohda_participant(1, [[1.0, 0.0], [0.0, 1.0]], my_perf)

Local Search Decider

For participants with continuous feasible sets (corridors) rather than discrete schedule lists, use LocalSearchDecider:

>>> from distributed_resource_optimization import (
...     LocalSearchDecider,
...     create_cohda_participant_with_decider,
... )
>>> decider = LocalSearchDecider(
...     initial_schedule=np.array([1.0, 1.0]),
...     corridors=[(0.0, 5.0), (0.0, 5.0)],
...     local_performance=lambda _: 0.0,
...     convergence_force_factor=0.1,
...     max_iterations=20,
...     sample_size_per_value=20,
... )
>>> actor = create_cohda_participant_with_decider(1, decider)

Note

COHDA is a heuristic and does not guarantee a globally optimal solution. Quality typically improves with more participants and more schedule choices. Convergence is detected when the system configuration stabilises across all participants.

See Also