Minimum Cost Maximum Flow Algorithm with restrictions

Minimum Cost Maximum Flow Algorithm with Restrictions

This algorithm allocates c clients to s servers, such that the total distance travelled is minimized.

LOOP until stop
Loop over servers
  SET closest = NULL
  SET shortest = INFINITY
  Loop over clients
    IF client has server
      CONTINUE
    SET dist = distance from client to server
    IF dist < shortest
      SET closest = client
      SET shortest = dist
    ENDLOOP over clients
  IF closest == NULL
    STOP
  Connect closest client to server
ENDLOOP over servers
ENDLOOP until stop

Alternatively, this problem can be modelled as a Mixed-Integer Linear Program (MIP): Variables:

• x_ij = 1 if client i is assigned to server j; else 0
• y_j = number of clients assigned to server j

Known Constants:

• d_ij = distance between client i and server j

Formulation:

min Σ_i,jd_ijx_ij

Subject to:

Σ_jx_ij = 1 for each client i

Σ_ix_ij - y_j = 0 for each server j

y_j - f >= 0 for each server j

y_j - f <= 1 for each server j

x_ij = 0 or 1

y_j variables will be forced to equal integers.