Tomáš Müller
Dear competitors,
There have been a number of questions sent directly to the organizers of the ITC 2019. To be fair to all the competitors, please see the questions and our answers below.
Best Regards,
Tomas, Hana, and Zuzana
~~~~~~~~~
1. Can a team join also after the first submission deadline of February 1?
Yes, it is definitely possible to join now, I do not think that it is late. The final submission deadline is November 18, 2019, so there is plenty of time to work on the solver.
It is not necessary to submit any milestone submission, we have these deadlines to provide some information about the competition during the long time for which the competition is running. You can learn how other teams are working and how far you are from the current best solution. So, milestone submissions are completely optional! We will add some comments about that to the web site.
2. Are the points only awarded for the final submission on November 18, 2019?
Yes, for the final ordering, points are only awarded based on the final submission. That is according to the best solution for each early, middle, and late instance uploaded by November 18, 2019.
The two milestone submissions are there for the milestone prices only (300 EUR, 200 EUR, and 100 EUR for the first, the second and the third place respectively). As the competition runs for a whole year, we wanted to have some mid-competition ranking to allow the competitors to have some feedback on how well are doing.
3. Does the competition model allow a class to have different starting times for different days of the week?
One class can only have one time and one room assigned. If it is needed to have two (or more) meetings that start at different times or are placed in different rooms, such a class has been split into two (or more) subparts with the appropriate classes in a parent-child relation.
4. The NotOverlap constraint for the class in the same subpart is implicit or needs to be defined in the distribution constraints section?
All distribution constraints that could be deducted from the structure are listed in the constraints section. There are no implicit distribution constraints.
5. Is there any other format of instances?
The competition instances are only available in the XML format described on our website. You need to use this format and transform it if needed.
6. The constraints SameTime and DifferentTime are stated as opposite in Table 1 (of Data Format) but if we follow the explanations downward, we can find a situation where two classes overlap and break both constraints SameTime and DifferentTime. It is safe to assume that the detailed explanations are correct?
Yes, you are right. Some of the distribution constraints are not the true opposite of each other, as the true opposite is often not practical. Who would want two or more classes to only partially overlap in times, days, or weeks?
Please follow the detailed description of each constraint.
7. About the Precedence constraint, it seems that class Ci precedes class Cj if and only if i < j (as noticed in the instances and in the explanations of the constraint). Is it safe to assume this for all the incoming instances as well?
Yes, in the case of the precedence constraints, the classes are to be placed in the order they are listed in the constraint.
8. It seems that classes 24 and 25 of instance muni-pdf-spr16c must satisfy the following hard constraints: SameAttendees, SameDays, SameTime, and SameRoom, which is clearly impossible. Am I wrong in parsing the XML file?
Actually, classes 24 and 25 can never overlap because they are taught on alternate weeks: class 24 is taught on weeks 1,3,6,8,10, and 12 (weeks="1010010101010"), class 25 on weeks 2,4,7,9,11, and 13 (weeks="0101001010101").
So, it is possible, for example, to assign the two classes as follows:
<class id="24" days="0000100" start="112" weeks="1010010101010" room="22">
<class id="25" days="0000100" start="112" weeks="0101001010101" room="22">
These classes are on the same days of the week (Friday), start at the same time (9:20 am -- slot 112), are in the same room (room 22) and do not overlap with each other.
9. Classes 24 and 25 of instance muni-pdf-spr16c must satisfy the soft constraint NotOverlap which seems irrelevant in regard to the hard constraint SameAttendees. Why is that?
Some distribution constraint can be redundant as they come from different sources. In this particular case, these two classes should not overlap because they are of the same scheduling subpart, but they also have the required SameAttendees constraint because they are taught by the same instructor.
10. In instance muni-fi-spr16, we have a MaxBlock(20,9) constraint which is required and involving classes 34, 50 and 110. However, class 110 has one possible time placement and its length is 22. As I understand the constraint now, even if class 110 was 9 slots away from classes 34 and 50 for every overlapping days and weeks, it is still a block itself of length 22 > 20 and so the constraint would be violated. So, should I understand MaxBlock as "every block of 2 or more classes must be of length less than 20"?
Yes, indeed, if a class is too long it forms a block by itself, and such a block does not break the MaxBlock constraint. So, it is fine that the classes are longer, but they cannot form a larger block. That is, they must be placed more than 9 slots apart when they share both days of the week and weeks.
Please note that the MaxBreaks constraint does not have this issue as it only cares about the number of blocks on a day.
11. In instance muni-fi-spr16, class 307 has a limit of 63 students. It seems that is the only class in subpart 157 and this subpart is in configuration 111 which is the only configuration of course 111. There are 63 students that must attend course 111 and so 63 students that must attend class 307. However, this class has only one room available which is room 4, and the capacity of room 4 is 12. I might have missed something, but right now, I don't know how to solve this.
Any room in the domain of the class (listed under the class element) is always big enough for the class. You do not need to compare class limit (or the number of assigned students) with room capacity. As is mentioned in the problem format:
For example, each class has a list of available time and room assignments given in the specified problem, each with a penalty. This means, for example, that only rooms that are big enough for the class and that meet all the other requirements (room type, equipment, building, etc.) are listed. Similarly, all the preferences have been already combined into a single penalty that is incurred when the time or room is assigned (see also details about problem transformations in the paper).
More details about the reasoning are in the mentioned paper, see Chapter 4.2 Transformations of real-life data into the competition problems.