INDR $220$: Introduction to Computing for Operations Research Homework $3$: The Set Covering Problem Deadline: April $29,2024,11$:$59$ PM

In this homework, you will implement a Python script that solves the set covering problem using CPLEX. As a specific example, consider the scheduling of airline flight personnel. The airline has M $$legs$$ to be flown. The airline must schedule its K crews on N routes to cover these flights. One crew, for example, might be scheduled to fly a route containing two legs just mentioned. The decision variables, then, specify the scheduling of the crews to routes:

Let

$1$ xj $=0$

$1$ aij $=0$

if a crew is assigned to route j$,$ otherwise.

if leg i is included on route j$,$ otherwise,

and cj is the cost for assigning a crew to route j$.$

The coefficients aij define the acceptable combinations of legs and routes, taking into ac$-$

count such characteristics as sequencing of legs for making connections between flights and for including in the routes ground time for maintenance. The model becomes:

Legs $1231.$SFtoLA $1$

$2.$SF to Denver $13.$SF to Seattle

$451$

$11$

$11$

$111$

$67$

$6$

$11$

$15$

$9101112$

$10.$Seattle to SF $11.$Seattle to LA Cost $($in $$1000$s$)$

$1234$

$11119989$

minimize subject to:

N

z $=$ cj xj j$=1$

N

$$aijxj $>=1$

j$=1$ N

$$xj $=$K j$=1$

i $=1,2,...,$M

xj in $\{0,1\}$

An example of a set covering problem with eleven legs, twelve flights, and three crews is

given as

$1$

$11$

$111$

$78$

$11$

$11$

$111$

$1$

$1$

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

Routes

$78$

$11$

$4.$LA to Chicago $5.$LAtoSF $16.$Chicago to Denver $7.$Chicago to Seattle $8.$Denver to SF

$9.$Denver to Chicago

$1$

$1$

$11$

$11111$

$1$

minimize subject to:

z $=+2000$x$1+3000$x$2+4000$x$3+6000$x$4+7000$x$5+5000$x$6$

$+7000$x$7+8000$x$8+9000$x$9+9000$x$10+8000$x$11+9000$x$12$

$+$ x$1+$x$4$

$+$x$2+$x$5$

$+$x$3+$x$6+$x$4$

$+$x$1+$x$6+$x$4+$x$5$

$+$x$7$

$+$x$8$

$+$x$7$

$+$x$7+$x$8+$x$8$

$+$x$7+$x$8+$x$7+$x$8$

$+$ x$10$

$+$x$9$

$+$x$9+$ x$10$

$+$ x$11$

$+$ x$11$

$+$ x$11$

$+$ x$11$

$+$ x$11+$x$11$

$>=1$

$>=1+$ x$12>=1+$ x$12>=1>=1>=1+$ x$12>=1>=1>=1+$ x$12>=1+$ x$12>=1+$x$12=3$

$+$x$2+$x$4+$x$5+$x$5$

$+$x$3$

$+$x$1+$x$2+$x$3+$x$4+$x$5$ x$1,$x$2,$x$3,$x$4,$x$5,$x$6,$x$7,$x$8,$x$9,$x$10,$x$11,$x$12$ in $\{0,1\}.$

$+$x$6$

$+$x$9+$ x$10$

$+$x$6$

$+$x$9+$x$10$

This problem will be represented using two $.$txt files, namely, flights.txt$,$ costs.txt and the crew count parameter K$,$ which is equal to $3$ for the example problem. The first file contains the leg$-$route matchings $($i$.$e$.,$ where aij$$s are nonzero$),$ and it is composed of the following lines for the example problem:

flights.txt $-----------11$

$14$

$1711022252821133363931244474941041251565105116465$

$2$

$+$x$9+$x$9$

$+$ x$10+$ x$10$

$697778$

$710711712828485899598$

$9111031071081012116119111011111112$

The second file contains the route costs $($i$.$e$.,$ cj$),$ and it is composed of the following lines for the example problem:

costs.txt

$---------$

$12000$

$23000$

$34000$

$46000$

$57000$

$65000$

$77000$

$88000$

$99000$

$109000$

$118000$

$129000$

One optimum solution of the example problem is as follows:

x $1=0$ x $2=0$ x $3=1$ x $4=1$ x$7=0$ x$8=0$ x$9=0$ x$10=0$ z$=18000.$

Another optimum solution of the example problem is as follows:

x $5=0$ x$11=1$

x $5=1$ x$11=0$

x $6=0$ x$12=0$

x $6=0$ x$12=1$

x $1=1$ x $2=0$ x $3=0$ x$7=0$ x$8=0$ x$9=0$ z$=18000.$

x $4=0$ x$10=0$

$3$

Implement your algorithm to solve the set covering 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 two input files and the crew count as parameters and returns the solution found.

def set$\_$covering$\_$problem$($flights$\_$file, costs$\_$file, K$)$:

# your implementation starts below

# your implementation ends above

return$($x$\_$star, obj$\_$star$)$

What to submit: You are provided with a template file named as $0099999$ hw$03.$ipynb, where $99999$ should be replaced with your $5-$digit student number. You are allowed to change the template file between the following lines.

# your implementation starts below

# your implementation ends above

You need to submit your source code in a single file $(0099999$ hw$03.$py file that you will download from Azure Lab Services by following $$File$/$Save and Export Notebook As$.../$Executable Script$$ menu items$).$

How to submit: Submit the file you edited to Blackboard by following the exact style mentioned. Submissions that do not follow these guidelines will not be graded.

Late submission policy: Late submissions will not be graded. Cheating policy: Very similar submissions will not be graded.

$4$