Homework 8: More integer programs

CS/ECE/ISyE 524 Introduction to Optimization 
Homework 8: More integer programs

See the course website for instructions and submission details.
1. [15 pts] Voting. 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 five congressional representatives. To form the five 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. [15 pts] Paint production. As part of its weekly production, a paint company produces five batches
of paints, always the same, for some big clients who have a stable demand. Every paint batch is
produced in a single production process, all in the same blender that needs to be cleaned between each
batch. The durations of blending paint batches 1 to 5 are 40, 35, 45, 32 and 50 minutes respectively.
The cleaning times depend of the colors and the paint types. For example, a long cleaning period is
required if an oil-based paint is produced after a water-based paint, or to produce white paint after a
dark color. The times are given in minutes in the following matrix A where Aij denotes the cleaning
time after batch i if it is followed by batch j.
A =






0 11 7 13 11
5 0 13 15 15
13 15 0 23 11
9 13 5 0 3
3 7 7 7 0






Since the company has other activities, it wishes to deal with this weekly production in the shortest
possible time (blending and cleaning). What is the corresponding order of paint batches? The order
will be applied every week, so the cleaning time between the last batch of one week and the first of the
following week needs to be accounted for in the total duration of cleaning.
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
3. [15 pts] 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 satisfied. 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 find a placement of the 8 queens that has point symmetry. In other
words, find a placement that looks the same if you rotate the board 180◦
.
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 find a placement of the queens that also has point symmetry. Does
the minimum number of queens required change? Show a possible optimal placement.
2 of 2