CS524- Homework 9-More Integer Programs Solved

1.   V oting. Governor Blue of the state of Berry is attempting to get the state legislator to gerrymander Berry’s congressional districts. The state consists of ten cities, and the numbers of registered Republicans and Democrats (in thousands) in each city are shown below

City
Republicans
Democrats
1
80
34
2
60
44
3
40
44
4
20
24
5
40
114
6
40
64
7
70
14
8
50
44
9
70
54
10
70
64
Berry has ve congressional representatives. To form the ve congressional districts, cities must be grouped together according to the following restrictions:

Districts cannot subdivide cities; all voters in a city must be in the same district.

Each district must contain between 150,000 and 250,000 voters (there are no independent voters).

Governor Blue is a Democrat. Assume 100% voter turnout and that each voter always votes according to their registered party. Formulate and solve an optimization problem to help Governor Blue maximize the number of congressional districts that have a Democratic majority.

2.   The Queens problem. You are given a standard 8 8 chess board. The following problems involve placing queens on the board such that certain constraints are satised. For each of the following problems, model the optimization task as an integer program, solve it, and show what an optimal placement of queens on the board looks like.

a)   Find a way to place 8 queens on the board so that no two queens threaten each other. We say that two queens threaten each other if they occupy the same row, column, or diagonal. Show what this placement looks like.

b)   Repeat part (a) but this time nd a placement of the 8 queens that has point symmetry. In other words, nd a placement that looks the same if you rotate the board 180 .

1 of 2

CS/ECE/ISyE 524  Introduction to Optimization                 L. Roald,  Spring 2020 c) What is the smallest number of queens that we can place on the board so that each empty cell is threatened by at least one queen? Show a possible optimal placement.

d) Repeat part (c) but this time nd a placement of the queens that also has point symmetry. Does the minimum number of queens required change? Show a possible optimal placement.

3.   Relay Race. A new running team is planning for a 5 400 meters relay race. The team coach Fannie has decided that the following ve people will run the race: Alice, Bob, Cindy, David and Elisa. However, Fannie has not yet decided the order in which they will run. The average time for each of them to nish running 400 metres are 82:5s; 77:1s; 81:3s; 74:9s; 80:6s, respectively. In the taking-over zone, the runner who just nished must pass the baton to the next runner. The time it takes to pass the baton depends on the runners, and are listed for each combination of runners in seconds in the table below (the column gives the name of the runner who is passing the baton, and the row gives the name of the runner who receives the baton).

Taking-over time (seconds)
A lice
B ob
C indy
David
E lisa
A lice
0
1.1
1.3
1.9
2.1
B ob
1.2
0
1.7
1.0
1.8
C indy
1.7
1.4
0
0.9
1.7
David
2.1
0.8
1.6
0
2.4
E lisa
1.5
1.2
1.9
2.3
0
The team is using a special baton to track their performance during the race. This baton is quite expensive, and Fannie is worried that one of the runners might loose it. Therefore, Fannie takes care of bringing the baton to the race. She gives the baton to the rst runner before the start of the race and gets it back from the last runner when the race is over (the time it takes for Fannie to give and receive the baton is not counted as part of the racing time).

Please help Fannie decide the order of the ve runners. What is the optimal runner sequence? What is the optimal total time for this race?

2 of 2