| DM841 (E23) - | Heuristics and Constraint Programming for |
| Discrete Optimization |
This is the first obligatory assignment of DM841. The assessment will be pass/fail by the teacher. It will not affect the final grade but a pass is necessary to complete successfully the course. The assignment has to be carried out in groups of two members. In case the number of members is different from two discuss, the situation with the teacher.
The deadline is Friday, October 6, at 17:00.
Each group has to submit the following elements:
The submission is made by one member of the group only. The PDF document
containing the report must be anonymous. The full name of the group
members and their SDU usernames must appear in file with name README.md
inside the directory asg1/.
See this page for details on the submission system. A git repository has been made available to you with a set of data for the problem of this assignment. The same set of data is also available here.
The project sGreenplay, financed by the SDU Climate Cluster, has the goal of developing tools to enable story-tellers to design plots for their movies and TV-series that are sustainable. Becoming aware of the CO2 impact of certain decisions early in the process of film making can yield considerable savings in the final CO2 footprint of a movie production. Examples of decisions that have an impact are the selections of actors and locations: which specific actors must we engage? which actors must be present on each scene? where must each scene be shot?
In order to assess such decisions, it can be helpful providing the story-teller with an assessment of the CO2 impact of ongoing decisions. However, knowing actors and locations is not enough to infer the impact. Indeed, for a fixed play, producers can schedule the scenes of the movie on a set of locations in an order that differ from the order in the final version of the movie, if this can improve the CO2 emissions. Thus scheduling the shooting of the scenes while minimizing the CO2 emissions related to moving actors and troupes to the locations corresponds to solving a combinatorial optimization problem.
In this assignment, we want to address this combinatorial optimization problem. More specifically, we are given a set of scenes that make up a movie.
Each scene has a duration (the days it takes to shoot it), takes place in a specific location and requires some subset of the cast to be on location.
Locations, where scenes take place, have a fixed CO2 footprint due to moving the cast there. We assume the whole cast gets back to the production center after every location visit so the footprint does not depend on the specific locations that are visited consecutively.
Actors have a CO2 footprint (for example, for food consumption) for each day they are required to be on a location from the day the first scene they are in is shot, to the day the last scene they are in is shot, even though some of those days they might not be required by the scene currently being shot (i.e., they will be on the location waiting for the next scene they are in to be shot). Each cast member has a different CO2 footprint.
The planning horizon is given by the project time-frame and is specified as a set of consecutive time periods with a period length of one day. Each scene must be planned to be shot for a number of days equal to the scene duration.
There can be precedence constraints between scenes, stating that a scene must be shot before another.
Our aim (and the one of the film producer) is to find the sequence of scenes that satisfies the precedence constraints and minimizes the total CO2 emissions.
Location Footprint: every time a location is visited to shoot a set of scenes, the footprint of the location is added once, independently of the number of consecutive scenes shot there before changing location.
Actor Footprint: The footprint of the actor is determined by the length (in number of days) of the sequence of scenes going from the first one in which the actor appears to his/her last one (extremes included). The footprint is present also if the actor is not taking part to the scene, because it is assumed that the actor remains in the set between scenes that he/she has to play.
We wish to develop a tool that will provide to the story-teller a fast assessment of the CO2 footprint of the play in the current status. Therefore solving time matters.
Given that any location must be visited at least once anyway, what matters is only the cost of the sequences excluding the first visit to any location.
Similarly, since actors must be present in the scenes where they are required, the only footprint that matters is the extra cost, which is the cost of the scenes in which the actor does not play.
Hence, in the best known best solutions provided below and in the tables you are asked to report (see below) you must also remove from the Location Footprint, the footprint of the first visit and from the actor footprint the footprint of the days in which they are playing.
The data files are provided already in MiniZinc data format, with the structure that can be deduced from the following example.
NumActors = 4;
NumScenes = 10;
NumLocations = 5;
NumPrecedences = 2;
ActorCost = [14, 4, 10, 6];
LocationCost = [0, 32, 26, 33, 25];
SceneDuration = [5, 3, 3, 5, 3, 3, 2, 5, 3, 1];
SceneLocation = [1, 2, 4, 0, 2, 4, 2, 3, 4, 1];
Presence = [|1, 0, 0, 0, 1, 1, 0, 1, 0, 1
|1, 1, 1, 0, 0, 1, 0, 1, 1, 1
|1, 0, 0, 1, 0, 1, 0, 1, 0, 0
|1, 1, 1, 0, 1, 0, 1, 1, 1, 0|];
Precedences = [|8, 5
|3, 2|];
Let’s simplify slightly the example assuming:
SceneDuration = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
That is, all durations have been set to 1. The Presence
matrix states if an actor plays (value 1) or not (value 0) in a
scene. The precedence pairs state that, for example, 8 must be planned
before 5. The actor costs are the daily footprint.
The requested output file format is in the form of a MiniZinc array, containing
the order of the scenes. For example, the array
[3, 1, 2, 8, 5, 7, 9, 0, 4, 6] represents a solution (note that
here we assume that both indexes of scenes and locations start from 0).
The given solution does not violate any precedence constraint and has a total footprint of 78, divided into 26 location footprint and 52 actor footprint.
The footprints are highlighted in the table below that shows the
location of the scenes in the sequence and the participants for the
solution [3, 1, 2, 8, 5, 7, 9, 0, 4, 6]. We see that the sequence
returns to location 2, for scenes 4 and 6 after having been there
earlier for scene 1. In addition, actor 2 is unnecessarily on stage for
scenes 1, 2, 8, and 9, and actor 3 is unnecessarily on stage for scenes
5 and 9. Thus, the solution has 6 scenes with an unnecessary actor on stage.
Scene [3, 1, 2, 8, 5, 7, 9, 0, 4, 6]
Location 0 2 4 4 4 3 1 1 2 2
Actor 0 X X X X X
Actor 1 X X X X X X X
Actor 2 X - - - X X - X
Actor 3 X X X - X - X X X
The solution [3, 2, 8, 5, 7, 0, 9, 4, 1, 6], shown in the table below,
also does not violate constraints and is optimal. It has a footprint
equal to 36. It has no location footprint and actor footprint of 36. It
has 5 scenes with an unnecessary actor on stage but the footprint
of these actors is less than it was with the previous solution.
Scene [3, 2, 8, 5, 7, 0, 9, 4, 1, 6]
Location 0 4 4 4 3 1 1 2 2 2
Actor 0 X X X X X
Actor 1 X X X X X X - X
Actor 2 X - - X X X
Actor 3 X X - X X - X X X
Reintroducing the original durations, the previous optimal solution remains accidentally optimal but has now CO2 footprint of 96.
| instance | num_locations | precedence_density | num_actors | actor_presence_density | num_scenes | best_solution |
|---|---|---|---|---|---|---|
| example | 5 | 0.09 | 4 | 0.58 | 10 | 96 |
| mss5.dzn | 3 | 0.60 | 3 | 0.47 | 5 | 9 |
| mss10.dzn | 5 | 0.13 | 6 | 0.58 | 10 | 128 |
| mss12.dzn | 6 | 0.03 | 3 | 0.58 | 12 | 43 |
| mss15.dzn | 2 | 0.10 | 11 | 0.44 | 15 | 910 |
| mss20.dzn | 3 | 0.06 | 5 | 0.56 | 20 | 774 |
| mss30.dzn | 3 | 0.02 | 12 | 0.40 | 30 | 2744 |
| mss50.dzn | 2 | 0.01 | 25 | 0.44 | 50 | 13675 |
| mss100.dzn | 18 | 0.00 | 30 | 0.46 | 100 | 28786 |
| mss200.dzn | 23 | 0.00 | 35 | 0.43 | 200 | 92185 |
| mss300.dzn | 15 | 0.00 | 40 | 0.44 | 300 | 165354 |
You are recommeded not to run your scripts for longer than 10 minutes per instance.
In MiniZinc you can ask to output the current best solution found during the search by outputting all solutiuons found with the -a flag.
You must approach the problem described with the following tasks:
Report the results in tables containing at least the following columns:
In international productions it may be restrictive to consider, as we did above, that the travel expenses to get to the locations are the same for all actors and for all locations. Instead, we might need to take into account the CO2 footprint of the travels that each different actor has to accomplish. To this purpose we might have a location for each actor, which is the home of the actor and from where he/she departs. We may assume that no scene has to be shot in these locations. Further we have a matrix of CO2 emissions between any two locations in the problem. We want to minimize the total footprint which is given by the footprint due to all the traveling that the shooting plan implies (hence, the sum of the footprint of the travel of each individual actor) plus, as before, the actor footprint for the days in which they are kept idle.
Envisioning the further needed data being available, can you provide a MiniZinc model for this alternative formulation of the problem?
To ensure that you comptue correctly the solution value there is a validator available from here. It accepts both 0-indexed and 1-indexed solutions.
$ make
$ ./TaS_Validator.exe example.dzn example1.txt