Prof Dr Jo¨rg Fliege Semester 1, 2021/2022
Mathematical Sciences
University of Southampton
Coursework MATH6002/MATH6161 — Mathematical Programming
MATH6002: Deterministic OR Methods
MATH6161: Deterministic OR Methods for Data Scientists
Introduction
This piece of work will count for 50% of the overall mark for MATH6002/6161. It is
intended that you carry out most of the analysis using the Xpress-IVE modeling and
optimisation software system.
Completed work should be submitted electronically via the Blackboard assignment
feature by
16:00 on Friday, 10th of December, 2021.
The deadline is strict.
Please refer to the Student Handbook for the penalties applied to late assignments.
Your report should be word processed. Ensure that you take frequent and multiple
backups of your work, since excuses concerning lost or corrupted files will not be treated
sympathetically.
As a very rough guide, I would like about six to ten A4 sides of description, with any
extra material (e.g., diagrams, tables or computer output) attached at the end. Your
report should include:
• an introduction;
• the formulation of your model with a statement of any assumptions made;
• an explanation of your model;
• a brief description of how you solved it;
• a presentation of the results;
• a summary of recommended policies that should be followed (and possible sug-
gestions for further investigations);
• printouts of the XPress-IVE model(s) and any other code, and corresponding
output in one or more appendices.
1
It should be written from the point of view of you, the analyst, describing some work
that you have done to a manager (who will know the mathematical programming ter-
minology).
Marks will be awarded on the basis of
• quality of the analysis;
• clarity of the presentation;
• originality.
Your work must be written up independently. The model and report must
be your own work. You are reminded of the University policy on plagiarism.
Your report must acknowledge clearly all people with whom you have dis-
cussed any part of the coursework, as well as any references you might have
used.
You are expected to complete the coursework without help from staff.
Electoral Shenanigans
In a small backward country in Europe, the dark lord Joris Bohnson has finally risen
to power. Bohnson now plots to consolidate his power by redefining the electoral con-
stituencies of the country. You have been pressed into being one of his court advisors.
Each constituency will send one representative to parliament. If 50% or more voters in
a constituency vote for Bohnson, then the constituency will sent one of Bohnson’s evil
lackeys to parliament.
The country is divided into 14 shires. Figure 1 shows a schematic map of the country
and its shires. These are numbered 1 to 14 (in boldface). The two other numbers given
per shire are the forecast of favourable votes for Bohnson and the total number of
electors per shire.
2
Figure 1. Schematic map of the country with its 14 shires. Legend: shire number,
Bohnson voters / total electorate.
A valid constituency consists of one or more shires and must have in total between
30,000 and 100,000 voters. Each shire in a constituency must be adjacent to another
shire in the same constituency, i. e. they must share a boundary. (Two shires that only
touch each other at one point, like shire no. 12 and shire no. 13, are not considered
adjacent.) A constituency consisting of a single shire is permitted, if it has at least
50,000 voters. To keep appearances up, Bohnson will not allow shire no. 10 to become
a single constituency, as this is where he lives.
The evil court jester Cuminic has proposed to use mathematical programming tech-
niques to determine a partition of the country such that Bohnson maximises the num-
ber of his representatives in parliament. Bohnson turns to you. . . and with an evil grin,
Cuminic tells you to start working immediately! You should find an optimal partition
of the country into five constituencies. If that does not work, consider the case of six
constituencies.
You may consider the following helpful hints:
1. Begin by listing all possible constituencies. You can write a small computer pro-
gram for that, or list them manually. You do not need to use XPress for this.
(Tip: you should arrive at 48 different possible constituencies.)
2. From this, build a matrix M with one row per shire and one column per possible
constituency, and set Mi,j = 1 if and only if shire no. i is in constituency j. Set
Mi,j = 0 else.
3. Use this matrix to set up a mathematical programming formulation of the prob-
lem. Then proceed with the actual tasks set out in the introduction.