Mathematical Programming IB2070
IB2070_Mathematical Programming 2_Exam Paper [January] 2021-2022 2 hours
Fixed time – Open Book
STUDENT INSTRUCTIONS
1. Read all instructions carefully. We recommend you read through the entire paper at least once before writing.
2. There are three questions. All candidates should attempt every question.
3. You should not submit answers to more than the required number of questions.
4. Question 1 is worth 34 marks, Question 2 is worth 33 marks and Question 3 is worth 33 marks.
The weighting of each question’s subpart (given in %) is stated in the paper.
5. Where handwritten answers are permitted, please ensure you write legibly, preferably in dark blue or black ink. If you use a pencil, please ensure it is not too faint to be captured by scan or photograph. It is your responsibility to ensure your work can be read.
6. If uploading photographs or scanned copies of your work, please check for legibility before uploading. It is your responsibility to ensure your work can be read.
7. Add your student number to all uploaded files.
8. You are permitted to access module materials, notes, resources, references and the internet during the online assessment.
9. You must not communicate with any other candidate during the assessment period, unless instructed to do so as part of the assessment requirement(s).
Page 1 of 7
10. By starting this assessment, you are declaring yourself fit to undertake it. You are expected to make a reasonable attempt at the assessment by answering the questions in the paper.
IMPORTANT INFORMATION
• We strongly recommend you use Google Chrome or Mozilla Firefox to access the Alternative Exams Portal.
• You must have completed and uploaded the assessment within the period of time provided.
• You are granted an additional 45 minutes beyond the stated duration (2 hours) of this assessment to allow for downloading/uploading your assessment, your files and any technical delays.
• Late submissions are not accepted. Once started, you must complete the assessment within 2 hours and 45 minutes.
• If you are unable to submit your assessment, you can record Mitigating Circumstances and the Board of Examiners will consider your case.
• Students with approved Alternative Exam Arrangements (Reasonable Adjustments) that permit extra time and/or rest breaks will have this time added on to the stated duration.
Operational Support
• Use the Alternative Exams Portal to seek advice immediately if during the assessment period:
o you cannot access the online assessment
o you believe you have been given access to the wrong online assessment
Operational support will be available between 09:00 and 17:00 UK Time for each examination (excluding Sunday)
Technical Support
• If you experience any technical difficulties with the Alternative Exam Portal please contact
SUPPORT DURING THE ASSESSMENT
Page 2 of 7
• If you experience technical difficulties with Questionmark Perception (QMP) please contact
• If you experience technical difficulties with myWBS, please contact
Technical support will be available between 09:00 and 17:00 UK Time for each examination (excluding Sunday)
Academic Support
• If you have an academic query, contact the invigilator (using the ‘Contact an Invigilator’ tool in AEP) to raise your issue. Please be aware that two-way communication in AEP is not currently possible
Academic support will normally be provided for the duration of the examination (i.e. for a 2 hour (+45 min) exam starting at 09:00 UK Time, academic support would normally be provided between 09:00 and 11:45 UK Time). Academic support beyond this time is at the discretion of the department
Other Support
• Write to your department immediately if you cannot complete your assessment
for the following reasons:
o you lose your internet connection
o your device fails
o you become unwell and are unable to continue
o you are affected by circumstances beyond your control
• If you experience technical difficulties with Moodle please contact
Your assessment starts below.
Page 3 of 7
[Question 1] The total marks available for this question is 34. The weighting of each subpart is indicated in %.
CBU International is interested in building new detached houses in three areas of Coventry. To start building new houses the company must first redevelop the area, which incurs significant investments as shown in the table below. After the redevelopment of an area is completed, a number of houses can be built in that area. The construction costs per house and the maximum number of houses in each area are also shown below.
The total budget for area redevelopment and building new houses is £5 million. The company does not have to build houses in all three areas. However, if an area is used, the number of houses built in it must be at least 5.
(a) Formulate an integer linear programming (ILP) model aiming to maximize the total number of houses built. Do not solve the model.
(b) Modify the model in part (a) to incorporate the following condition: houses in area 3 cannot be built if the number of houses built in area 2 is 20 or more.
(c) Ignore parts (a) and (b). An integer linear program was solved using the branch-and-bound algorithm, in which the corresponding linear program (LP) relaxation problems were solved by the simplex-method. The seven printouts on page 5 below show the optimal solutions to all these LPs. Unfortunately, the printouts are in disorder. It is known that six variables were used in the formulation, of which X1, X2 and X3 were integer, and Y1, Y2 and Y3 binary. The objective function was maximized. It is also known that branching was performed only on binary variables Y1, Y2 and Y3, and not on X1, X2 and X3.
Draw the tree representing the solution process, incorporating the printouts shown and indicating the additional constraints added to the model at different stages.
Is the assumption that the model was completely solved consistent with the solution tree?
What is the maximum value of the objective function in the original ILP problem? Provide explanations for each of your answers.
(Question 1 continues on the next page…/)
Redevelopment cost (£000)
Construction cost per house (£000)
houses in the area
Maximum number of
Page 4 of 7
(Continued…/)
Page 5 of 7
[Question 2] The total marks available for this question is 33. The weighting of each subpart is indicated in %.
A company’s production process depends on a supply of a special component. Demand for the component is shown in the table below:
MONTH 1 MONTH 2 MONTH 3 MONTH 4 1 unit 2 units 1 unit 4 units
The company can order units at the beginning of each month. Orders are delivered immediately. It costs £60 to place an order, no matter how many units are ordered. However, it costs £30 to store a unit for one month in a warehouse. Assume the company has no unit in store at the very beginning.
(a) Use dynamic programming (DP) to define an ordering policy with the minimal total cost. Solve the DP and provide all the details.
How many stages are there in the DP formulation?
What are the state variables at each stage?
What is the total cost?
What is the optimal ordering policy?
(b) Nowconsiderageneralcase.Supposethatthecompanyknowsthedemandsfor𝑇months,which are 𝑑1, 𝑑2, … , 𝑑𝑇. It costs £𝑎 to place an order regardless of order quantity and £𝑏 to keep one unit in store for a month.
Formulate dynamic programming recursions to find an optimal ordering strategy for this general case.
(Continued…/)
Page 6 of 7
[Question 3] The total marks available for this question is 33. The weighting of each subpart is indicated in %.
A company produces and sells seven types of boxes, ranging in volume from 17 to 33 cubic metres. The demand (number of boxes) and size of each box is given in the following table. The variable cost (in Sterling pounds) of producing each box is equal to the volume of the box. A fixed cost of £1000 is incurred when producing any number of boxes of a particular size. If the company desires, demand for a box may be satisfied by a box of larger size.
1234567 Size 33 30 26 24 19 18 17 Demand 400 300 500 700 200 400 200
(a) Formulate a shortest-path problem whose solution will minimize the cost of meeting the demand for boxes.
(b) Solve the problem formulated in part (a).
End of Paper
[70%] [30%]
Page 7 of 7