Bottleneck transportation problem in a grid with pairing of two adjacent cells

Question

While working on a personal project I stumbled into a problem that can be formulated as follows:

You have a grid with N rows and M columns. The table contains some red and some green cells. The goal is to find such an assignment of red to green cells, such that the total distance between red and green cells in their matching is minimal. In addition, two adjacent(with a common edge or vertex) red grid cells can be paired together and moved to another pair of adjacent green cells.

Let's say the limits are N <= 1000, M <= 1000. It is not guaranteed that the number of red cells is equal to the number of green cells, i.e. they are different most of the time. Moving a group into another group that doesn’t have the same look(say two on top of each other into two that are diagonal to each other) is allowed.

I tried finding a similar problem and a lot are close to it, however without the pairing part. I've tried representing it as a transportation problem, an assignment problem or a maximum flow problem(edges having capacity 1 and maybe including an additional "layer" of vertexes to represent groups), however I haven't found a way to properly include the pairing part.

I have managed to represent it as an ILP problem: Red and green cells are represented as vertexes in a complete bipartite graph - R1, R2,.. G1, G2,.., where the edge weights between Ri and Gj is the Euclidean distance between those two cells in the grid. All valid groupings of red and green cells form a second completed bipartite graph, where the position of the group is just the average of the two cells. Each edge in the two graphs is assigned a boolean variable that represents whether or not we move said cell/group into the other. The constraints are that the sum of each edge that is related to Ri(i.e. the ones that come from Ri and from groups that include Ri) is equal to one and that the sum of the edges that go into Gi(cell or group) is <= 1. The objective function is the minimum sum of the boolean variable multiplied by the edge weight it is associated with.

Here is a python implementation of the solution

import pulp
import math

# manhattan or euclidean
DISTANCE_CALCULATION = "euclidean"
# default or gurobi
SOLVER = "gurobi"

# change these value pairs
red_cell_cords = [(1, 8),(1, 9),(1, 19),(1, 20),(2, 8),(2, 9),(2, 19),(2, 20),(3, 9),(3, 19),(6, 9),(6, 19),(7, 18),(8, 11),(8, 17),(9, 12),(9, 16),(11, 13),(11, 15),(12, 14)]
green_cell_cords = [(0, 6),(0, 21),(0, 22),(1, 6),(1, 23),(2, 5),(2, 6),(2, 23),(2, 24),(3, 4),(3, 5),(3, 6),(3, 24),(3, 25),(4, 4),(4, 5),(4, 9),(4, 19),(4, 25),(5, 5),(5, 25),(6, 5),(6, 7),(6, 21),(6, 25),(7, 4),(7, 5),(7, 25),(8, 4),(8, 25),(9, 4),(9, 6),(9, 22),(9, 26),(10, 5),(10, 27),(11, 5),(11, 27),(12, 27),(14, 24),(17, 25),(19, 25)]

red_cells = [f"R{i}" for i in range(len(red_cell_cords))]
green_cells = [f"G{i}" for i in range(len(green_cell_cords))]

red_group_cords = []
green_group_cords = []

red_groups = []
green_groups = []

# Generate RED groups and coordinates
for r1_idx, r1_cord in enumerate(red_cell_cords):
    for r2_idx, r2_cord in enumerate(red_cell_cords):
        if r1_idx < r2_idx:
            if abs(r1_cord[0] - r2_cord[0]) <= 1 and abs(r1_cord[1] - r2_cord[1]) <= 1:
                red_groups.append(f"R{r1_idx}-R{r2_idx}-")
                red_group_cords.append(((r1_cord[0] + r2_cord[0]) / 2, (r1_cord[1] + r2_cord[1]) / 2))
# Generate GREEN groups and coordinates
for g1_idx, g1_cord in enumerate(green_cell_cords):
    for g2_idx, g2_cord in enumerate(green_cell_cords):
        if g1_idx < g2_idx:
            if abs(g1_cord[0] - g2_cord[0]) <= 1 and abs(g1_cord[1] - g2_cord[1]) <= 1:
                green_groups.append(f"G{g1_idx}-G{g2_idx}-")
                green_group_cords.append(((g1_cord[0] + g2_cord[0]) / 2, (g1_cord[1] + g2_cord[1]) / 2))

costs = {}

# Edge weights for singular cells
for r_idx, r_cord in enumerate(red_cell_cords):
    for g_idx, g_cord in enumerate(green_cell_cords):
        red_label = red_cells[r_idx]
        green_label = green_cells[g_idx]
        if DISTANCE_CALCULATION == "manhattan":
            distance = abs(r_cord[0] - g_cord[0]) + abs(r_cord[1] - g_cord[1])
        elif DISTANCE_CALCULATION == "euclidean":
            distance = math.sqrt(math.pow(abs(r_cord[0] - g_cord[0]), 2) + math.pow(abs(r_cord[1] - g_cord[1]), 2))
        else:
            raise BaseException("Invalid parameter as DISTANCE_CALCULATION. Check for typos")
        costs[(red_label, green_label)] = distance

# Edge weights for groups
for r_idx, r_cord in enumerate(red_group_cords):
    for g_idx, g_cord in enumerate(green_group_cords):
        red_label = red_groups[r_idx]
        green_label = green_groups[g_idx]
        if DISTANCE_CALCULATION == "manhattan":
            distance = abs(r_cord[0] - g_cord[0]) + abs(r_cord[1] - g_cord[1])
        elif DISTANCE_CALCULATION == "euclidean":
            distance = math.sqrt(math.pow(abs(r_cord[0] - g_cord[0]), 2) + math.pow(abs(r_cord[1] - g_cord[1]), 2))
        else:
            raise BaseException("Invalid parameter as DISTANCE_CALCULATION. Check for typos")
        costs[(red_label, green_label)] = distance

prob = pulp.LpProblem("RedGreenAssignment", pulp.LpMinimize)

# Variables
## Singular movement
vars = pulp.LpVariable.dicts("Assign", (red_cells, green_cells), 0, 1, pulp.LpBinary)
## Group movement
vars_groups = pulp.LpVariable.dicts("Assign group", (red_groups, green_groups), 0, 1, pulp.LpBinary)

# Objective function
## Singular movement & Group movement
prob += pulp.lpSum([vars[r][g] * costs[(r, g)] for r in red_cells for g in green_cells]) + pulp.lpSum([vars_groups[r][g] * costs[(r, g)] for r in red_groups for g in green_groups])

# Constraints
## For each red cell, ensure it's either assigned individually or through a group
for i, r in enumerate(red_cells):
    related_groups = [group for group in red_groups if f"R{i}-" in group]
    prob += (pulp.lpSum([vars[r][g] for g in green_cells]) + \
             pulp.lpSum([vars_groups[group][g_group] for group in related_groups for g_group in green_groups])) == 1
## For each green cell, ensure it assigned individually or through a group at most once
for i, g in enumerate(green_cells):
    related_groups = [group for group in green_groups if f"G{i}-" in group]
    prob += (pulp.lpSum([vars[r][g] for r in red_cells]) + \
             pulp.lpSum([vars_groups[r_group][group] for group in related_groups for r_group in red_groups])) <= 1

# Solve
if SOLVER == "default":
    prob.solve()
elif SOLVER == "gurobi":
    solver = pulp.GUROBI_CMD(path=r'C:\gurobi1103\win64\bin\gurobi_cl.exe') # include your path to the gurobi solver
    prob.solve(solver)
else:
    raise BaseException("Invalid parameter as SOLVER. Check for typos")

# Result
for r in red_cells:
    for g in green_cells:
        if pulp.value(vars[r][g]) == 1:
            print(f"{r} is assigned to {g}")

for r in red_groups:
    for g in green_groups:
        if pulp.value(vars_groups[r][g]) == 1:
            print(f"{r} is assigned to {g}")

print(f"Total Cost: {pulp.value(prob.objective)}")

Having about 2500 edges gives a solution in under 0.5 seconds, i.e. my current solution works reasonably fast.

Marked in yellow with arrows are the “matchings” of red to green cells. Groupings in pairs are marked by having a line over the two. Solution(not necessarily optimal) found by hand for a grid of 22x29 without considering pairs: Solution(optimal) found by the ILP solver for a grid of 22x29 with pairings in consideration:

My question is: Is there a more efficient algorithm(which still finds the optimal assignment) that can handle the red-green cell pairing constraint and improve performance within the grid size limit compared to the ILP solution?

The people I've discussed the problem with are surprised that the ILP solution works in a reasonable amount of time(since ILPs are generally NP-hard).

This is my first question, feel free to correct my statement or suggest a proper mathematical representation of the ILP formulation.

Bottleneck transportation problem in a grid with pairing of two adjacent cells

Answers (1)

Related Questions