algorithmoptimizationdynamic-programminggraph-theorymaximize

Reputation: 644

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.

Upvotes: 3

Answers (3)

ravenspoint

Reputation: 20596

The problem can be formulated as a generic mathematical optimization.

subscripts

e an employee

c a crate

variables

Pec the amount paid to e to push c

parameters

Fe employee efficiency

Cec 1 if e can push c, 0 otherwise

PLe pay limit for e

CLe crate limit for e

constraints

(sum over all c ) Pec < PLe

Iec = 0 if Pec = 0, 1 otherwise

(sum over all c) Iec < CLe

optimize

Max: (sum over all e, c ) Pec * Fe

This formulation makes the problem solvable by many different algorithms: simplex, annealing, ... It can even by solved by a straightforward search through the solution space.

Complete application code for an exhaustive solution space searcher at https://github.com/JamesBremner/so79058180

Results for the example problem ( Optimum found in ~ 1 microsecond )

Employee 0 (  20 for crate 1  15 for crate 2  )
Employee 1 (  20 for crate 0  20 for crate 3  )
total Distance 185
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        1.1e-06 1.1e-06 cSSex::search

The sample solution space is 160 points.

If you would tell me the maximum problem size you expect ... and the performance you need.

I have added an option to use the simulated annealing algorithm. For such a small solution space, this algorithm behaves poorly, so I won't post it here. If you provide a larger sample problem, then it might be worthwhile.

Upvotes: 0

ravenspoint

Reputation: 20596

This problem can be solved using the Edmonds–Karp implementation of the Ford–Fulkerson method to compute the maximum flow in a flow network

https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

The flow network for the example problem in the question looks like this

As usual, this problem has some special constraints which need care to be handled successfully.

Crate Budgets

Set the capacity of the links between the crate and the sink to the crate budget. ( Shown in above image )

Employee Efficiencies

When creating the flow graph, create the employee nodes in order of decreasing efficiency. This ensures the high efficiency employees are employed preferentially

Employee Pay Limits

Set the capacity of the links between source and employee to the employee pay limit ( Shown in above diagram )

Employee Crate Limits

This is tricky. An iterative approach is required. Run the max flow algorithm on the graph shown above. If any employee exceeds their crate limit, zero the capacity of the link between the employee and the crate with the smallest budget. If the employee is linked to crates all with the same budget, then zero the link to the crate with the fewest alternative pushers. Run the max flow algorithm again and repeat until no employees exceeds their crate limit.

Test Application

I have developed a test application to demonstrate this solution to the example problem. The user can test different crate budgets and employee pay limits. The complete C++ code for the application is at the github repository https://github.com/JamesBremner/so79058180. V1.0.0 release is available at https://github.com/JamesBremner/so79058180/releases/tag/v1.0.0

Screenshot of application run

Upvotes: 1

Zevgon