algorithmoptimizationdynamic-programminggraph-theorymaximize# Maximize distance while pushing crates

#### Problem

#### Input

#### Output

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

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

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?

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
},
]
```

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.

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.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?