algorithm optimization dynamic-programming graph-theory maximize

Maximize distance while pushing crates

I'm struggling to write an algorithm for this problem. What approach can be used to solve it?

Problem

There's a company called CratePushers, whose employees are willing to push crates for money. Their employees have certain attributes:

Each employee pushes crates at a certain rate. For example, Alice might push crates at 3 feet per dollar, and Bob might push them at 2 feet per dollar
Each employee has a certain set of crate types that they're capable of pushing. For example, Alice might only be able to push crates that are labeled with an A, B, or C, while Bob might only be able to push crates that are labeled with an A or a D
Each employee might have a limit to the total number of crates they're willing to push. For example, even though Alice is capable of pushing crates A, B or C, she might have a policy where she only pushes a maximum of 2 crates per job assignment
Each employee might also have a limit to the number of dollars they're willing to accept. For example, Alice might have a policy where she only accepts up to $35 per job assignment. (A solution that ignores this attribute would still be very helpful.)

Now let's say I want to enlist their services. I have several crates in my back yard, and I have a certain budget for each crate. For example, let's say I have 5 crates, labeled A through E, and I'm willing to spend $20 on each crate, but my budget for each crate can only be used to push one specific crate. My goal is to maximize the sum of the distance pushed for all the crates. And the question is: how do I allocate my money optimally? That is, who do I pay to push which crates, and for how much money?

Input

The list of employees and their attributes, e.g.

[
  {
    name: 'Alice',
    capableOfPushing: ['A', 'B', 'C'],
    paymentLimit: 35,
    crateLimit: 2,
    efficiency: 3, // Feet per dollar
  },
  {
    name: 'Bob',
    capableOfPushing: ['A', 'D'],
    paymentLimit: null,
    crateLimit: null,
    efficiency: 2,
  }
]

along with my per-crate budget, e.g.

[
  {
    crate: 'A',
    budget: 20,
  },
  {
    crate: 'B',
    budget: 20
  },
  {
    crate: 'C',
    budget: 20
  },
  {
    crate: 'D',
    budget: 20
  },
  {
    crate: 'E',
    budget: 20
  },
]

Output

Any optimal solution is acceptable. One solution for the above example would be:

[
  {
    employee: 'Alice',
    crate: 'B',
    amountPaid: 20,
  },
  {
    employee: 'Alice',
    crate: 'C',
    amountPaid: 15,
  },
  {
    employee: 'Bob',
    crate: 'A',
    amountPaid: 20,
  },
  {
    employee: 'Bob',
    crate: 'D',
    amountPaid: 20,
  }
]

(No one can push crate E, so my $20 budget for that crate remains in my pocket.)

If my budget for crate B was anything less than $5, the optimal solution would then be to pay Alice $15 for crate A and $20 for crate C, and pay Bob $5 for crate A and $20 for crate D. That would mean we're leaving crate B unpushed, but we're still maximizing the total sum of the distance pushed when considering all the crates.

What I've considered (but hasn't worked)

There's the brute force solution, where we create all possible combinations of crates pushed. For example, we consider all 3 scenarios where Alice pushes (A,B), (A,C), (B,C). This solution is way too inefficient because it scales out of control when multiple employees have crate limits, or even if a single employee has larger numbers for their attributes. Like if Alice could push up to 30 crate types and had a crate limit of 10, the number of scenarios would already be in the tens of millions.

I feel like dynamic programming could work, but again it's the crate limits that cause issues in terms of knowing the optimal solution at each point.

I've looked for similar questions on LeetCode but haven't yet found any that are sufficiently related.

This problem vaguely resembles the knapsack problem, but doesn't really fit.

It also resembles multi-commodity max flow problems, but doesn't quite fit that either? I'm struggling to figure out a viable way to represent the employees as a graph, and AGAIN the crate limits are really problematic. This seems like the most promising direction though.

Solution

Thank you @nneonneo for suggesting MILP! That's a great solution for this.

The example problem could be formulated like this, which provides the right answer:

import gurobipy as gp
from gurobipy import GRB

model = gp.Model("Pushing crates")

a_distance = model.addVar(vtype=GRB.CONTINUOUS, name="a_distance")
b_distance = model.addVar(vtype=GRB.CONTINUOUS, name="b_distance")
c_distance = model.addVar(vtype=GRB.CONTINUOUS, name="c_distance")
d_distance = model.addVar(vtype=GRB.CONTINUOUS, name="d_distance")
e_distance = model.addVar(vtype=GRB.CONTINUOUS, name="e_distance")

model.setObjective(a_distance + b_distance + c_distance + d_distance + e_distance, GRB.MAXIMIZE)

alice_efficiency = 3
alice_payment_limit = 35
alice_crate_limit = 2

bob_efficiency = 2

budget_for_a = 20
budget_for_b = 20
budget_for_c = 20
budget_for_d = 20
budget_for_e = 20

dollars_to_alice_for_a = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_a", lb=0, ub=budget_for_a)
dollars_to_alice_for_b = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_b", lb=0, ub=budget_for_b)
dollars_to_alice_for_c = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_c", lb=0, ub=budget_for_c)
dollars_to_bob_for_a = model.addVar(vtype=GRB.INTEGER, name="dollars_to_bob_for_a", lb=0, ub=budget_for_a)
dollars_to_bob_for_d = model.addVar(vtype=GRB.INTEGER, name="dollars_to_bob_for_d", lb=0, ub=budget_for_d)
dollars_for_e = model.addVar(vtype=GRB.INTEGER, name="dollars_for_e", lb=0, ub=budget_for_e)

value_1_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_1_for_alice_crate_limit", lb=0, ub=1)
value_2_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_2_for_alice_crate_limit", lb=0, ub=1)
value_3_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_3_for_alice_crate_limit", lb=0, ub=1)

model.addConstr(dollars_to_alice_for_a + dollars_to_bob_for_a <= budget_for_a)
model.addConstr(dollars_to_alice_for_a + dollars_to_alice_for_b + dollars_to_alice_for_c <= alice_payment_limit)
model.addConstr(value_1_for_alice_crate_limit + value_2_for_alice_crate_limit + value_3_for_alice_crate_limit <= alice_crate_limit)

model.addConstr(a_distance <= alice_efficiency * dollars_to_alice_for_a * value_1_for_alice_crate_limit + bob_efficiency * dollars_to_bob_for_a)
model.addConstr(b_distance <= alice_efficiency * dollars_to_alice_for_b * value_2_for_alice_crate_limit)
model.addConstr(c_distance <= alice_efficiency * dollars_to_alice_for_c * value_3_for_alice_crate_limit)
model.addConstr(d_distance <= bob_efficiency * dollars_to_bob_for_d)
model.addConstr(e_distance <= 0 * dollars_for_e)

model.optimize()

for var in model.getVars():
    print(f"{var.varName}: {var.x}")

print(model.ObjVal)

And the last step would be to generalize this to handle various inputs, and format the final variable values into the desired output.