1. Goal
Lab assignment 1: Modeling Linear Programming Tasks Heuristics and Optimization
Computer Science, 2019Ð2020
The goal of this assignment is to learn to model linear programming (LP) and mixed integer program- ming tasks, and to solve them with two different tools: The LibreOffice spreadsheet and a modeling language, MathProg.
2. Problem statement
A renowned museum has contacted the students of Heuristics and Optimization of UC3M. After a number of meetings you and your partner have been selected to solve various optimization problems using Linear Programming.
2.1. Part 1: Basic Modelling with LibreOffice Calc
The museum that hired us is now involved in the renovation of all its infrastructure. One of the major con- cerns of the museum is the entrance management. The museum has three different entrances: the main entrace (located to the east) and two secondary entrances located to the north and west respectively, see Figure 1(a).
Currently, only one person takes care of each entrance who is in charge of selling tickets, introducing the visitors to the museum and also the access control. However, these three people are not enough to satisfy the demand and every day long lines of people await to get in so that in the end, some visitors quit. The museum is reporting the average waiting time of visitors for getting into the museum, see Table 1. It is important to take into account that every entrance is open 8 hours every day.
The museum is considering the possibility of acquiring vending machines, turnstiles and to hire more staff to speed up the input process. Each one of these resources reduce the average waiting time to get into the museum as described in the first row of Table 2. For example, with one vending machine the average waiting time of each visitor decreases from 130 to 128 minutes; if two vending machines are installed and, additionally,
Figura 1: (a) View of the base floor and the entrances; (b) View of the first floor of the museum
1
East entrance
West entrance
North entrance
Average waiting time pero visitor in minutes
130
100
90
Tabla 1: Average waiting time per visitor in every entrance.
Tabla 2: Reduction of the average waiting time and cost of the different available resources.
an employee is hired, the average waiting time is reduced now from 130 to 122 minutes. The second row of Table 2 shows the hourly rate of each resource.
The museum imposed a number of constraints for effectively solving this problem.
Firstly, the total investment for purchasing vending machines, turnstiles and hiring employees for all
entrances should not be larger than 1000e per day.
Secondly, the main entrance should not require an expenditure greater than 10 % over the expenditure of
any of the secondary entrances.
Also, the sum of the number of vending machines and turnstiles of every secondary entrance shall be less than the sum of the number of vending machines and turnstiles of the main entrance, and the number of turnstiles in the north entrance shall be less than in the west entrance.
Additionally, there shall be at least two vending machines, two turnstiles and two employees in the main entrance, and one vending machine, one turnstile and one employee in each of the secondary entrances.
Finally, it is expected that the reduction in the average waiting time is larger in the main entrance than in any of the secondary entrances.
It is therefore requested to determine the number of vending machines, turnstiles and employees that the museum has to acquire to minimize the average waiting time in all queues while satisfying all constraints.
1. Model the problem as an Integer Linear Integer Programming task. 2. Implement the model in a spreadsheet (LibreOffice Calc).
2.2. Part 2: Advanced modeling with GLPK
The museum is very satisified with the results obtained in the previous problem so that they decided to introduce you to a new optimization problem.
Figura 2: Ejemplo de robot adquirido por el museo.
The museum has recently acquired 8 robots (see Figure 2) that can be used to introduce the visitors to any of the 17 galleries that the museum offers in the west and east sides of the first floor Ñdenoted with a letter in Figure 1(b). Table 3 describes the specifications of each robot.
Vending machine
Turnstile
Employee
Reduction of the average waiting time (minutes per visitor)
2
3
4
Cost (e/hour)
4
5
8
2
R1
R2
R3
R4
R5
R6
R7
R8
Presentation (min./item)
4
6
5
3
2
3
4
5
Energy (unit/item)
7
5
3
1
2
4
4
5
Max. energy (units)
100
90
95
40
45
75
85
60
Tabla 3: Specification of each robot.
Tabla 4: Number of items in each gallery.
The first row of Table 3 describes the time it takes each robot to introduce a visitor to one item in the same hall where it is located. Notice that robot R5 is the fastest whereas R2 is the slowest; the second row of the table describes the units of energy consumed by each robot to introduce a visitor to a single item; the third row shows the maximum capacity of the battery of each robot. The museum wants to decide the halls where these robots should be located.
Table 4 shows the number of objects in each gallery. For instance, halls A, B and C have 5 items each, and galleries D and E offer 6 items each. A gallery is said to have been introduced if the robot assigned to that gallery has introduced all items in it.
To assign robots to each gallery, a number of constraints shall be observed:
It is not allowed to have more than one robot assigned to the same gallery, and each gallery shall have one robot assigned.
Each robot shall be assigned to at least two galleries and never more than three.
Robots R3, R5 and R6 can not be assigned to any of the halls in the west side of the museum.
Likewise, robots R2 and R4 can not be assigned to any of the galleries in the east side.
Only robots assigned to either gallery A, B or both, can be assigned to the halls C, D or both.
Obviously, each gallery requires a specific amount of energy to introduce all objects in it, so that only robots that can support such amount shall be assigned to it.
Finally, the galleries of the west side are larger and thus, it is required that presentations there take 10 % longer than presentations in the east side.
The goal of this part is to minimize the average waiting time of visitors to access the museum using vending machines, turnstiles and employees and, also to minimize the time required to introduce all objects in each gallery of the museum while considering all constraints of the problem.
1. Model the new problem as an Integer Linear Programming task. 2. Implement the new model in MathProg.
2.3. Part 3: Analysis of results
All results obtained in the previous parts have to be analyzed in this one. The solutions obtained have to be properly described (verifying that all contraints are verified). It is also requested to check what constraints are more relevant.
Analyze the problem complexity: how many variables and constraints have you defined? Modify the pro- blem, varying the parameters and adding/removing robots and explain if these changes affect the difficulty for solving the resulting problem.
A, B, C
D, E
F, G, H
I, J
K, L, M
N, O, P, Q
Number of Items
5
6
4
7
3
2
3
Also, address the following question: what is the average waiting time of a visitor through the main entran- ce? and through the secondary entrances? how long will it take a visitor to visit all galleries? what robots will be in charge of the presentation in each gallery?
Likewise, discuss the pros and cons of using the proposed tools: LibreOffice and GLPK.
2.4. Optional part: Dynamic Programming
Given the success of the models proposed to the museum, they have contacted us again to solve an entirely different new optimization problem: the delivery of works of art to temporal exhibitions in other museums. For the delivery, the museum only has one truck which, nonetheless, has capacity enough to attend all the demand.
The goal is to set up a delivery path starting from the museum and returning to it after delivering to all the temporal exhibitions. It is requested to use Dynamic Programming for minimizing the path length. The program shall receive an input text file with a matrix describing the distance between each pair of museums, including the museum hiring us which is denoted as M0, e.g.:
MO M1 M2 M3 M4 MO 0 24 16 23 24 M1 16 0 27 14 11 M2 15 14 0 16 27 M3 14 22 19 0 23
M4 13 11 26 18 0
To test your algorithm, it is recommended to generate input data randomly with a different number of museums and assuming a uniform distribution of distances ranging from 10 to 30 kilometers. Of course, the main diagonal of all matrices shall be made of zeroes, as the minimum distance from any location to itself is 0 kilometers.
The program can be implemented in any programming language and it should be submitted along with a shell script named itinerario.sh that automates its execution. The script shall receive the input text file as its first argument and it should return two lines: the first one indicating the overall distance of the shortest delivery path, and the second one explicitly describing the itinerary, e.g.:
Overall distance: 78 Itinerary: MO, M2, M3, M1, M4, MO
As it can be seen, all delivery paths start and end in our museum and they visit each temporal exhibition only once. The report shall mention explicitly the Bellman equations used for solving this problem and also any other possible optimizations that make your program more efficient. Also address the following questions:
If it is required to deliver works of art to 100 different locations, what is the number of combinations that should be considered by a brute-force approach? What is the number of combinations considered by your solution?
Would it be more efficient for your algorithm if museums are sorted according to any specific criteria? If so, why and which criteria?
Is it possible to use Dynamic Programming to enumerate all solutions of the minimum path length instead of just returning one? Justify your answer
3.
the cover, table of contents and back cover. It should contain, at least:
Requirements for the Report
The report must be delivered in PDF format and it should consist of a maximum of 15 pages, including
1. Brief introduction explaining the contents of the document. 4
2. Description of the models, discussing the decisions carried out. 3. Analysis of results.
4. Conclusions.
The report should not include source code in any case. 4. Grading
This lab assignment will be graded over 10 points. Nevertheless, it is possible to get an additional point by submitting the extra partÑhence, scoring for a maximum of 11 points. It is mandatory to perform at least the first part and to write the report.
To assure that the assignment is graded you must do at least the first part and the report. Points are distributed as follows:
1. Part 1 (3 points)
Problem Modeling (1 point) Model Implementation (2 points)
2. Part 2 (5 points)
Problem Modeling (3 points) Model Implementation (2 points)
3. Part 3 (2 points)
4. Optional part: Dynamic Programming (1 point)
When grading the model proposed, a correct model will make half of the points. To get all points, the model must:
Be correctly formalized in the report.
Be simple and concise.
Be properly explained (it should be clear what is the purpose and meaning of each variable/constraint). Justify in the report all your design decisions.
When grading the model implementation, a correct model will make half of the points. To get all points, the implementation must:
Make use (in the implementation) of the features that the tools provide to facilitate that implementing/up- dating the model is as easy as possible (concretely, use sumproduct in the case of the spreadsheet or use sets in MathProg).
Keep the code (spreadsheet or Mathprog files) correctly organized and commented. The names should be descriptive. You should also add comments in those cases that are needed to improve readability.
When grading the results analysis, it will be positively valued to include in the report personal conclusions about the assignment difficulty and about what you learnt while carrying it out.
Important: The models in the spreadsheet and GLPK must be correct. That is, they must run and obtain optimal solutions to the problem provided. Otherwise, the maximum achievable score for the implementation is 1 point. This is, if part 1 is not correctly implemented, the maximum score is 1; if part 2 is not correctly solved, the maximum score is 4 points.
5
5. Submission
The deadline for submitting the assignment is October, 27 at 23:55. This is a hard deadline and it will not be extended.
Only one student from each team must submit:
A single .zip file to the assignment section of ÕAula GlobalÕ through the submission entry point named
ÒFirst lab assignmentÓ.
This file must be named p1-NIA1-NIA2.zip, where NIA1 and NIA2 are the last 6 digits of each
studentÕs NIA padding with 0s if necessary. Example: p1-054000-671342.zip.
The report in pdf format shall be submitted through the Turnitin submission entry point enabled in Aula Global named ÒFirst lab assignment (only pdf)Ó.
The report in pdf format and shall be named NIA1-NIA2.pdf Ñafter properly substituting the NIA of each student.
Example: 054000-671342.pdf.
Uncompressing the .zip file submitted through the first entry point must generate a directory named NIA1-NIA2, where NIA1 and NIA2 are the last 6 digits of each studentÕs NIA padding with 0s if necessary. This directory shall contain: first, the same pdf submitted through Turnitin, and shall be named NIA1-NIA2.pdf Ñafter properly substituting the NIA of each student; second, a file named autores.txt that identifies the membersofthemteam,oneperlinewiththeformat:NIA Surname, Name.Forexample:
054000 Von Neumann, John
671342 Turing, Alan
In addition, this directory shall contain also the directories called Òpart-1Ó and Òpart-2Ó. If the optional part is submitted also, then a third directory should be generated with the name Òpart-3Ó. The solutions (either source code or the spreadsheet) should be included in their corresponding directories.
The following figure shows a plausible distribution of files after decompressing the .zip file:
6
p1-054000-671342/
054000-671342.pdf
autores.txt
part-1/
part-1.ods
part-2/
part-2.dat
part-2.mod
part-3/
part-3.cc
itinerario.sh
Important: ignoring these guidelines one way or another might result in a loss of up to 1 point in the final score.
7