Reference no: EM131210990

Operations Research - Project

Introduction

1. The problems should be formulated as Mixed Integer-Linear Programming problems and computational results obtained using AMPL where necessary.

• Do not try to use the in-built AMPL logical constructions (such as 'if ' 'else if ' etc) - use the binary variable approach instead.
• Since you are asked to formulate the problems as MILP problems, it means you are not allowed to use non-linear functions.

2. Each question is divided into two parts. The first part is about the basic formulation. The second part is open-ended further investigation. You are encouraged to work in groups for the first parts of the questions, but you should work individually on the second parts and the report.

3. Explain in the report the exact commands and the operating system you have used to run the code. Explain the formulation of your models in your report, separately from the code. Do NOT expect me to guess your models from you AMPL code

4. Marks will be awarded for the quality and presentation of your report, mathematical accuracy, your technical approach and originality. See the mark scheme below for more information.

Debugging tips-

If you run into trouble with your AMPL code, probably there are some 'bugs' in the code. The following is a few things you may try to 'debug':

1. Pay attention to the small things: keywords and commands are case sensitive; do not forget the semicolon at the end of a statement.

2. Read the error message. It usually gives you the line number where the first error is detected, sometimes also the nature of the error (although its meaning may not be obvious). The code usually stops at the first error so there would be only one error message. But if the code throws out several messages, start from the first one, because the other errors may disappear after the first one is fixed.

3. Starting from the line reported in the error message, check backwards: check the line, then the line immediately before (sometimes the error is caused by the line before); then check the dentitions of all the variables and parameters involved in the two lines; etc.

4. If you are not sure about some commands or keywords, a good idea is to write a simple code to test them.

5. If you could not find any mistakes in the code, and the code did generate some results, but the results did not make sense, then you will have to check your formulation of the problems: cost function correct? Any missing constraints? etc. You could use examples in notes, handout, lab sheet, examples sheets and anything you can find to help.

6. If you are really desperate, do not hesitate to ask. However, I will only correct the coding mistakes. Questions about the formulation of the problems would not get direct answers.

1. Credit Card Company Financial Problem

A collection and processing service is provided to a credit card company. Payments are received at dedicated postal boxes to which the credit card company directs its customers to send their payments. The service makes several collections per day, processes the payments immediately, and deposits the funds into the bank accounts of the credit card company.

The credit card company receives payments into its collection service from credit card account holders in seven regions (A to G) of the country. The average amounts sent from each region each day are respectively (in k£) (65 - a), (60 + b), (50 + c), 80, 60, 70, 60 where a, b and c are the final three digits of your student number. Six different banks (1 to 6) are under consideration for the deposit of the payments. The whole collection of the payments from a region are sent to a single postal box linked with a single bank. On the other hand, more than one regions could deposit their collections into a same bank account.

Money in a bank account earns simple interest at a rate equivalent to 20 percent per annum. The average duration in days from mailing to clearance, and the associated losses in interest (listed in parentheses, in k£) for each possible assignment, are given in Table 1.1. In the table, losses have been calculated for a = b = c = 0. The annual cost of the company maintaining an account at a bank is £50k.

	1	2	3	4	5	6
A	3 (39)	4 (52)	5(65)	4 (52)	5 (65)	2 (26)
B	3 (36)	4 (48)	2 (24)	3 (36)	4 (48)	6 (72)
C	5 (50)	3 (30)	5(50)	6 (60)	4 (40)	7 (70)
D	4 (64)	4 (64)	3 (48)	3 (48)	2 (32)	3 (48)
E	2 (24)	2 (24)	7 (84)	5 (60)	5 (60)	3 (36)
F	6 (84)	3 (42)	5 (70)	4 (56)	3 (42)	4 (56)
G	2 (24)	3 (36)	2 (24)	8 (96)	6 (72)	3 (36)

Table 1.1 - Losses of interests due to mailing

1. Determine the optimal bank account (1 to 6) for each region (A to G), so that the overall cost for the credit card company is minimised.

2. Are there any other questions of practical concerns? Explore and support your arguments with computational results.

2. Optimal Allocation of Operating Theatres

The allocation takes place in a Sheffield hospital where the use of health resources, particularly operating theatres, must be controlled effectively. The hospital has 10 staffed operating theatres serving 6 departments: surgery, gynaecology, ophthalmology, otolaryngology, oral surgery and emergency. There are 8 main surgery theatres and 2 elective outpatient surgery (EOPS) theatres. An operating theatre is either 'short' or 'long', depending upon the daily number of hours the room is available. Because of the socialized nature of health care, all surgeries are scheduled during work days only (Monday through Friday).

Table 2.1 summarizes the daily availability of the different types of operating theatres and Table 2.2 provides the weekly demands of operating theatres in terms of hours. The numbers of under allocated hours for each department cannot exceed the maximum numbers given in Table 2.2.

weekday	Main short	Main long	EOPS short	EOPS long
Monday	08:00-15:30	08:00-17:00	08:00-15:30	08:00-16:00
Tuesday	08:00-15:30	08:00-17:00	08:00-15:30	08:00-16:00
Wednesday	08:00-15:30	08:00-17:00	08:00-15:30	08:00-16:00
Thursday	08:00-15:30	08:00-17:00	08:00-15:30	08:00-16:00
Friday	09:00-15:30	08:00-17:00	09:00-15:30	09:00-16:00
Number of rooms	4 per day	4 per day	1 per day	1 per day

Table 2.1 - Surgery Room Availability

Department	Weekly target hours hj	Limits of Under allocated hours uj
Surgery	189.0	10.0
Gynaecology	117.4	10.0
Ophthalmology	39.4	10.0
Oral surgery	19.9	10.0
Otolaryngology	26.3	10.0
Emergency	5.4	3.0

Table 2.2 - Weekly Demand for Operating Theatres Hours

Let

u_j = maximum number of under allocated hours allowed in department j

h_j = requested weekly target hours for department j

x_ijk = number of rooms of type i assigned to department j on day k

In other words, x_ijk represents the schedule of the rooms. Our goal is to find an optimal solution for x_ijk.

1. As a first attempt, we assume that, if a room is assigned to a department, it will be occupied by that department for the whole day. As a result x_ijk is an integer. The ideal solution would satisfy exactly the weekly target hours for all departments. However, we recognise that it may not be possible. Therefore, we introduce sj to denote the difference between the target hours and the actually allocated hours for department j, i.e.,

s_j = h_j the actually allocated hours for department j,

and decide that our objective should be finding a schedule x_ijk that minimizes the total relative under-allocation of all departments. We observe that, positive sj represents under-allocation, whereas negative s_j represents over-allocation. Thus, when s_j ≥ 0, the ratio s_j = h_j measures the relative under-allocation for the jth department.

Establish the mathematical formulation of the above model, and then use AMPL to find the solution with provided data. Briefly discuss the computational experiences and the results. (Hint: Only under-allocation needs to be minimised. You may need to introduce auxiliary variables)

2. Explore other possible models and/or questions of practical concerns. Support your discussion with computations where possible.