Employee to project assignment reward problem

Question

Describe a Branch & Bound algorithm to solve the employee to project assignment reward problem. You are given n employees and n projects. You are also given an array A[i,j] which contains the revenue realized by that assignment of employee i to project j. Describe your B&B solution to maximize the reward.

Answer 1

1.  Setting the solution space

Each node represents a partial solution of the assignment.  For example, the root node represents the solution space where no assignment has been made.  The child node C1 represents: job 1 assigned to employee 1.  The child of C1, denoted as C11, represents that Job 2 is assigned to employee 2 under the constraint that job 1 has been assigned to employee 1. And the similar for others. All none leaf nodes are partial solutions since they do not specify the entire assignment. The leaf nodes are the final options.

2.  Setting the bound

Since this is a maximization problem, the lower bound can be any permutation of employees and projects.

The upper bound asks us how much revenue at most can we achieve. We can consider the upper bound from employee and project perspective separately.

From employee’s perspective, each project has a maximum revenue realized by an employee. From project 1, select the maximum revenue and add it to the accumulative value “maxByEmpl”. Continue to select the maximum revenue for other projects until we traverse all the projects.

From project’s perspective, each employee can achieve a maximum revenue on a certain project. From employee 1, find and select the project with the maximum revenue. Add this revenue to the accumulative value “maxByProj”. Continue to do this until we traverse all the employees.

The assignment strategies above can be invalid. For example, employee 1 can be assigned to 2 projects. This is fine when setting the upper bound. But once we made our decision on which employee does what, we can no longer consider this employee and project in the following upper bound setting process.

3.  Conduct a BFS on the nodes in the revenue graph.

Firstly, assign employee 1 to all the projects. For each assignment choice, calculate the upper bound as described above. Select the assignment strategy with the maximum upper bound. Only explore the probable assignments of employee 2 under this assignment strategy.

4. Repeat step 3 on all employees

Finally, only one probable assignment can be left, since employees and projects cannot be reconsidered. The upper bound of this assignment strategy is the optimal revenue we can get.

Comments

Thank you so much Fangfei.

Answer 2

Problem Formulation: We represent each possible combination of assignments as a node in a decision tree. Each level  d in this tree corresponds to the assignment of  d employees.

Initial Node: Begin with a baseline scenario where no employee is assigned to any project.

Expansion Mechanism: At any given node, create offspring nodes by allocating the next available employee to each possible project. This branching continues until all employees are allocated.

Upper Bound Estimation: For each node, compute the maximum possible revenue that can be achieved from that point onwards. This includes the revenue already secured from current assignments plus the highest possible revenue from remaining unassigned employees, ensuring that no project is repeated in the estimations.

Pruning Strategy: Eliminate any node from further consideration if its upper bound is less than the revenue of the best-known complete assignment. This step is crucial in reducing the search space.

Solution Exploration: Whenever a node represents a full set of assignments, evaluate its total revenue. If this revenue exceeds that of the best solution found so far, update the optimal solution.

Traversal Approach: Implement a systematic traversal method, like Best-First Search, which prioritizes nodes with higher revenue potential, to navigate through the decision tree.

Algorithm Completion: The process concludes once all nodes have been either fully examined or pruned.

Optimal Assignment: The algorithm's output is the best assignment found, representing the optimal allocation of employees to projects for maximum total revenue.