Solving Multi Knapsack problem using Linear Programming

Problem Statement

This is a multi knapsack problem. We have to execute a number of tasks on a fixed number of hosts. Duration of each task and the number hosts on which we want to distribute the tasks is fixed (in this case it is let’s say 3). Individual tasks can not be broken into smaller pieces. We need to distribute tasks into these “3” hosts. The aim is to distribute the tasks in such a way that total time to complete all tasks will be minimum.

Tasks and duration it takes to finish

One of the Solutions can be

Expected output. Total duration 9

Hence total time taken is 9.

Solution

This problem can be solved by Dynamic Programming but let us try solving it using linear programming.

Linear Programming Solution

I have used Pulp https://coin-or.github.io/pulp/ to solve the problem using python. Here is the link to my full code.

First come up with Linear Programming Equations as shown below.

Ideal expected time for all tasks to be executed on each host is (total_time_to_execute_tasks_sequential/number_of_hosts). The number_of_hosts is 3 in our case.

Objective

Aim is to minimize the time tasks took to run on each host minus the ideal time. Objective is to keep running time on each host close to ideal average time.

Objective

Here are the additional constraints:

(Variables starting with “if_” are of type boolean. They can take value of either 0 or 1)

Constraints : Host should not be idle. Each task can be run on maximum one host.

Time taken to run tasks on each host minus ideal time

Calculate absolute difference of deviation from ideal time. Should be minimum as per the objective.

When I run this code, I get this output:

Output shows which task should be run on which host. It matches with our expected outcome of total duration 9.

Conclusion

This problem can be solved by Dynamic Programming but using Linear Programming we can solve problems where even if one or more constraints are not fitting it will try to fit the rest of the constraints.