I

In this homework, you will implement a Python script that solves the

multiple knapsack problem using CPLEX. The multiple knapsack problem

is defined as follows: Given a set of N items and a set of M knapsacks

$($M $<=$ N$),$ with

wj $=$ weight of item j$,$

vj $=$ value of item j$,$

Ci $=$ capacity of knapsack i$,$

select M disjoint subsets of items so that the total profit of the selected items

is a maximum, and each subset can be assigned to a different knapsack whose

capacity is no less than the total weight of items in the subset. Formally,

maximize z $=$

X

M

i$=1$

X

N

j$=1$

vjxij

subject to: X

N

j$=1$

wjxij $<=$ Ci i $=1,2,...,$ M$,$

X

M

i$=1$

xij $<=1$ j $=1,2,...,$ N$,$

xij in $\{0,1\}$ i $=1,2,...,$ M$,$ j $=1,2,...,$ N$.$

where

xij $=$

$($

$1$ if a item j is assigned to knapsack i$,$

$0$ otherwise.

When M $=1,$ the multiple knapsack problem reduces to the standard knapsack problem.

$1$

This problem will be represented using three $.$txt files, namely, weights.txt$,$

values.txt$,$ and capacities.txt$.$ The first file contains the item weights

$($i$.$e$.,$ wj $)$ in a single row, and it is composed of the following line for an example problem with five items $($N $=5)$:

weights.txt

$--------------$

$1020304050$

The second file contains the item values $($i$.$e$.,$ vj $)$ in a single row, and it

is composed of the following line for the example problem with five items

$($N $=5)$:

values.txt

$--------------$

$5040302010$

The third file contains the knapsack capacities $($i$.$e$.,$ Ci$)$ in a single row,

and it is composed of the following line for the example problem with two

knapsacks $($M $=2)$:

capacities.txt

$--------------$

$4050$

The optimum solution of the example problem is as follows:

x

$$

$11=1$ x

$$

$12=1$ x

$$

$13=0$ x

$$

$14=0$ x

$$

$15=0$

x

$$

$21=0$ x

$$

$22=0$ x

$$

$23=1$ x

$$

$24=0$ x

$$

$25=0.$

Implement your algorithm to solve the multiple knapsack problem in a

single interactive Python notebook using Azure Lab Services. Your notebook

should include at least the following function definition that takes the file

paths of three input files as parameters and returns the solution found.

def multiple$\_$knapsack$\_$problem$($weights$\_$file, values$\_$file, capacities$\_$file$)$:

# your implementation starts below

# your implementation ends above

return$($X$\_$star$)$