Assignment 2
MSc Business Analytics 2021/22
Optimisation and Decision Models
Wolfram Wiesemann
Exercises 2
(1) In-Class: Johnson Electric has three different plants, each of which produces electric motors
for four different clients. The unit production costs and capacities for each plant are as follows.
For the next months, the clients have submitted the following orders:
The unit transportation costs (£/motor) to each of the clients is shown in the following table:
Johnson Electric must decide how many motors to produce in each plant, as well as how much
of each customer’s demand to supply from each plant, so as to minimise the overall costs (that
is, the sum of production and transportation costs).
(a) Construct a linear program that determines the production and distribution plans that
minimise the overall costs.
Hint: Introduce one decision variable for each plant-customer pair, such as AO for
Aberdeen-Onyx or CT for Cardiff-Treble. The decision variable AO should determine
how many motors Johnson Electric produces in Aberdeen that are to be shipped to
Onyx Inc. You will then require constraints for the capacity of each plant as well as for
the demand of each customer.
(b) Solve the linear program using AMPL. What managerial actions would you recommend
based on the optimal solution and the shadow price information?
Plant Production costs
(£/motor)
Monthly capacity
(# of motors)
Aberdeen 17 800
Birmingham 20 700
Cardiff 24 700
Customer
Onyx Inc. Treble Co. Hilton Appliances Dean Electric
Demand 300 500 400 600
Plant
Customer
Onyx Inc. Treble Co. Hilton Appliances Dean Electric
Aberdeen 3 2 5 7
Birmingham 6 4 8 3
Cardiff 9 1 5 4
(2) In-Class: Dualising linear programs.
(a) Using the “indirect method” from class, find the dual to the linear program:
minimise 3 x1 + 5 x2 – x3
subject to x1 + x3 = 4
x2 – 2 x3 ≤ 2
x1, x2 ≥ 0, x3 unrestricted
(b) Using the “direct method” from class, find the dual to the linear program:
maximise x1 – x3
subject to x1 + x2 = 4
x3 ≤ 2
x1, x2 ≤ 0, x3 unrestricted
(3) Homework: In class we have defined that the dual of the linear program
maximise cTx
subject to Ax ≤ b
x ≥ 0
is
minimise bTy
subject to ATy ≥ c
y ≥ 0
Show that this definition is symmetric, that is, the dual of the linear program
minimise bTy
subject to ATy ≥ c
y ≥ 0
is
maximise cTx
subject to Ax ≤ b
x ≥ 0
Make sure you explain what you are doing! [30 marks]
Hint: Bring the dual problem into the form of the primal problem (that is, change the
objective into a maximisation and change the constraints), use the above definition to
determine the dual of the resulting problem, and finally show that this dual is actually
equivalent to the primal problem.
(4) Homework: The Graduate Admissions dataset from Kaggle (https://www.kaggle.com/
mohansacharya/graduate-admissions) has the independent variables
as well as the dependent variable
[70 marks]
(a) Formulate the 1-norm regression problem for this data set (with Chance as the dependent
variable and GRE, TOEFL, …, Res as independent variables) as a linear program. You can
“index” the data by writing “GRE”, “TOEFLi” etc. in your model. Make sure you explain what you
are doing! [5 marks]
(Please also include an intercept in your regression problem!)
(b) Construct an AMPL file that solves the 1-norm regression problem. To this end, you can use the
Graduate_Admissions.dat file in the exercises folder (which only involves the first 100 records,
to comply with the size limitations of the AMPL demo version) and import the data as follows:
set NUM ordered; # candidate number
param GRE {NUM}; # GRE Score
param TOEFL {NUM}; # TOEFL Score
param Univ {NUM}; # University Rating
param SOP {NUM}; # Statement of Purpose Strength
param LOR {NUM}; # Letter of Recommend. Strength
param CGPA {NUM}; # Undergraduate GPA
param Res {NUM}; # Research Experience
param Chance {NUM}; # Chance of Admission
data Graduate_Admissions.dat;
In your model, you can access the i-th element of GRE via GRE[i]. Also, you can create
variable vectors that are indexed by NUM (the candidate number) via
var x {NUM};
GRE: GRE Scores (out of 340)
TOEFL: TOEFL Scores (out of 120)
Univ: University Rating (out of 5)
SOP: Statement of Purpose Strength (out
of 5)
LOR: Letter of Recommendation Strength
(out of 5)
CGPA: Undergraduate GPA (out of 10)
Res: Research Experience (either 0 or 1)
Chance: Chance of Admission (ranging from 0 to 1)
Graduate Admission 2
Graduate Admission 2
Similarly, the i-th component of x can be access via x[i]. You can sum over all elements of x via
sum {i in NUM} x[i]
Finally, you can create a set of constraints, one for each candidate NUM, via
subject to constr {i in NUM}: …
You may want to consult the AMPL book (available online for free) for further information on
sets and indexing.
Solve the problem. Make sure you use CPLEX as a solver (“option solver cplex;”), as other
solvers have stricter size limitations in the demo version. What is your optimal objective value,
and what are the regression coefficients? (You do not need to interpret the regression
coefficients in this part of the question.) [15 marks]
(c) Formulate the infinity-norm regression problem for this data set (again with Chance as the
dependent variable and GRE, TOEFL, …, Res as independent variables — plus an intercept)
as a linear program. You can “index” your data as in part (a). Justify why your model gives the
correct solution (similar to our argumentation for the 1-norm problem in the lecture)!
[20 marks]
(d) Construct an AMPL file that solves the infinity-norm regression problem.
Solve the problem. Make sure you use CPLEX as a solver (“option solver cplex;”).
What is the optimal objective value, and what are the regression coefficients?
Please provide an interpretation to your regression coefficients — what conclusions
do you draw from them? [15 marks]
(e) What are the differences between a 1-norm regression, a 2-norm regression (i.e., the standard
regression) and an infinity-norm regression? When would you use which one? [15 marks]