The State Highway Patrol (SHP) has only 60 officers to patrol j = 1,

c, 10 major highway segments in rural and suburban areas of the state.

Officers work i = 1,

c, 7 different shift patterns across a 24 hour, 7 day work week. Exceptions can be made on late-night shifts i = 1 and 2, but all other shifts require at least 1 officer on each highway segment, and no segment ever receives more than 3.

An SHP goal is to concentrate the patrol resources in times and places of greatest need. One measure of this is ci, j!the traffic density on segment j during shift i. A second is ai, j!the relative accident rate on segment j during shift i. The following table shows values derived from history for both across shifts and segments.

Shift i Highway Segments j 1 2 3 4 5 6 7 8 9 10 1 Cong 0.22 0.26 1.11 1.06 1.80 2.16 1.93 0.98 0.66 0.45 Accid 0.92 2.16 1.18 1.49 0.90 4.11 1.10 1.15 2.18 0.77 2 Cong 0.32 0.36 1.31 1.26 1.90 2.26 2.03 1.05 0.86 0.55 Accid 0.98 2.66 1.48 1.69 1.10 3.91 1.12 1.17 2.48 0.77 3 Cong 0.55 0.66 1.81 1.86 2.20 2.86 2.43 1.95 1.06 0.85 Accid 0.88 3.16 1.88 1.89 1.80 4.11 1.62 1.67 2.88 1.07 4 Cong 0.65 0.76 1.91 1.96 2.30 2.96 2.53 2.05 1.26 0.95 Accid 0.77 2.01 1.03 1.31 1.10 3.11 1.00 1.05 2.08 0.67 5 Cong 0.60 0.70 1.83 1.82 2.22 2.79 2.45 2.00 1.16 0.90 Accid 0.90 2.76 1.38 1.52 0.98 3.81 1.40 1.45 2.48 0.87 6 Cong 0.62 0.68 1.85 1.82 2.25 2.74 2.40 2.02 1.18 0.94 Accid 1.18 4.16 2.48 2.59 2.80 4.61 2.62 1.87 3.28 1.09 7 Cong 0.42 0.48 1.55 1.52 1.95 2.14 2.10 1.92 1.08 0.64 Accid 1.08 5.16 2.28 2.19 2.20 4.11 3.22 1.67 3.58 1.19 SHP would like to decide how to feasibly allocate its officers to shifts and segments to maximize total coverage of congested shifts and segments, as well as total coverage of high accident shifts and coverage.

(a) Formulate the problem as a multi- objective ILP over nonnegative integer decision variables xi, j!the number of officers assigned to each shift i and segment j.

(b) Show how to modify your model of (a)
as a goal ILP with targets for total congestion = 120 and for total accident level = 150. Weight under-satisfaction of the two goals equally, define all new decision variables, and annotate new objectives and constraints to show their meanings.

(c) Enter and solve your goal ILP of

(b) with class optimization software.