You have n items with sizes a$1,...,$ an to be packed into some bins. Each bin

has capacity V $.$ Assume that V $$ ai$,$ i $=1,...,$ n$.$ That is$,$ at most, you need n bins to pack all

items.

$($i$)$ Formulate an integer linear program to find the item allocation that uses the fewest number

of bins. Hint: Use a binary variable yj to denote whether bin j is used; use another binary

variable xij to denote whether item i should be placed in bin j$.($This is called bin packing

problem.$)$

$($ii$)$ Now consider a case where you have five items with size $2,3,4,5,7$ and the capacity of each

bin is $10.$ Formulate the IP in that case. Use CVX to solve the IP and its LP relaxation. $($In

CVX$,$ you may want to use MOSEK or Gurobi as solver to solve IP problems$)$ What are the

optimal solutions to the IP and its LP relaxation? Is there an integrality gap in this case?