Problem $3$ Formulating IP $(50$ points$)$

A$.$ You have $n$ items with sizes $A_1,$cdots,$A_n$ to be packed into some bins. Each bin has capacity $C.$ Formulate an integer program to find the packing method that uses the least number of bins. $($Hint: $y_j$ is a binary variable specifying whether bin $i$ is utilized or not, and $x_{ij}$ is a binary variable specifying whether item $i$ is packed in bin $j).$ Now consider a real case where you have items with sizes $4,4,5,$ and $7,$ and the capacity of each bin is $10.$ Formulate the IP in that case. Use Gurobi to solve both IP and its LP relaxation. Specify the optimal solution and objective value in both cases. Also, mention the integrality gap.

B$.$ The Government is planning to put bus stops in a city. Let $N$ be the set of candidate stop locations decided by the Govt. agency, and let $M$ be the set of demand points in the city. The matrix $A=\{a_{ij}\}$ tells whether the demand point i can be covered by stop $j($meaning that $a_{ij}=1$ if passenger at point i can easily walk to stop $j).$ Find the least number of bus stops located in the city so that each demand point is covered.