Solving Multi Knapsack problem using Linear Programming
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.
One of the Solutions can be
Hence total time taken is 9.
This problem can be solved by Dynamic Programming but let us try solving it using linear programming.
Linear Programming Solution
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.
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.
Here are the additional constraints:
(Variables starting with “if_” are of type boolean. They can take value of either 0 or 1)
When I run this code, I get this output:
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.