The Bayside Art Gallery is considering installing a video camera security system to reduce its insurance premiums. A diagram of the eight display rooms that Bayside uses for exhibitions is shown in the figure below; the openings between the rooms are numbered $1$ through $13.$

A blueprint of a gallery with eight rooms, one entrance and thirteen doorways is shown. The gallery is laid out in a grid of three columns and four rows. Some rooms take up more than one row. The left$-$hand side contains rooms $1$ and $2,$ the middle column rooms $3,4,5,$ and $6,$ and the right$-$hand side rooms $7$ and $8.$ The following list contains each doorway and the rooms it connects.

Entrance: Room $1$

Opening $1$: Rooms $1$ and $3$

Opening $2$: Rooms $3$ and $7$

Opening $3$: Rooms $3$ and $4$

Opening $4$: Rooms $1$ and $4$

Opening $5$: Rooms $4$ and $7$

Opening $6$: Rooms $1$ and $2$

Opening $7$: Rooms $4$ and $5$

Opening $8$: Rooms $2$ and $5$

Opening $9$: Rooms $5$ and $7$

Opening $10$: Rooms $5$ and $6$

Opening $11$: Rooms $7$ and $8$

Opening $12$: Rooms $2$ and $6$

Opening $13$: Rooms $6$ and $8$

A security firm proposed that two$-$way cameras be installed at some room openings. Each camera has the ability to monitor the two rooms between which the camera is located. For example, if a camera were located at opening number $4,$ rooms $1$ and $4$ would be covered; if a camera were located at opening $11,$ rooms $7$ and $8$ would be covered; and so on$.$ Management decided not to locate a camera system at the entrance to the display rooms. The objective is to provide security coverage for all eight rooms using the minimum number of two$-$way cameras.

$($a$)$

Formulate a $0-1$ integer linear programming model that will enable Bayside's management to determine the locations for the camera systems. $($Let xi be the $0-1$ which is $1$ if a camera is installed at opening i$,$ and $0$ otherwise, for i $=1,2,...,13.)$

Min

s$.$t$.$

Room $1$

Room $2$

Room $3$

Room $4$

Room $5$

Room $6$

Room $7$

Room $8$

xi $=0,1,$ for i $=1,2,,13$

$($b$)$

Solve the model formulated in part $($a$)$ to determine how many two$-$way cameras to purchase and where they should be located.

The gallery should install

cameras with

$($x$1,$ x$2,$ x$3,$ x$4,$ x$5,$ x$6,$ x$7,$ x$8,$ x$9,$ x$10,$ x$11,$ x$12,$ x$13)=$

$.$

$($c$)$

Suppose that management wants to provide additional security coverage for room $7.$ Specifically, management wants room $7$ to be covered by two cameras. Which constraint would have to change?

Room $1$

Room $2$

Room $3$

Room $4$

Room $5$

Room $6$

Room $7$

Room $8$

What should the new constraint be$?$

$($d$)$

With the policy restriction specified in part $($c$),$ determine how many two$-$way camera systems will need to be purchased and where they will be located.

The gallery should install

cameras with

$($x$1,$ x$2,$ x$3,$ x$4,$ x$5,$ x$6,$ x$7,$ x$8,$ x$9,$ x$10,$ x$11,$ x$12,$ x$13)=$

$.$