Proposed by Helmut Simonis

This problem was used for the programming competition of the ACP Summer School 2016 in Cork. The problem was defined in multiple stages, adding constraints and problem data as the competition progressed.

This is a totally made-up problem. None of the companies mentioned have been contacted, there are no interviews that will be arranged. Sorry! But there are conferences which run such a scheme, as well as some universities. The companies mentioned are interested in Constraint Programming, many are sponsoring the CP 2016 conference, or have participants in the ACP Summer School.

Initial Problem Statement

You have been asked to provide a tool that helps match students to companies in an interview session at the next major Constraint Programming conference. A number of companies have expressed interest in participating, there are currently 15 companies in the scheme.

Each student from set $S$ can express a preference to interview with each company, with values ranging from 1 (very interested) to 5 (not at all interested). We provide a comma separated text file that shows the answers that have been collected through a Google Forms document (test.csv). Each student should have three interviews during the conference, with different companies. The companies have expressed limits on how many interviews they want to perform during the conference. We want to find an assignment of students to companies that stays within the capacity limits for each company, while providing the best match to the student preferences. Overall quality will be measured by two quality indicators:

  1. If the preference of student $i$ for company $j$ is $p_{ij}$ , and the three companies selected for student $i$ are $s_{ik}$ with $k \in [1, 3]$, the first overall quality indicator is the sum of the preferences for the selected assignments, i.e. $\sum_{i \in S} \sum_{k=1}^{3} p_{is_{ik}}$ . We want to minimize this sum.

  2. We do not want to have a solution that satisfies all preferences for some students, but not for others. As a secondary criterion, we want to minimize the maximum of the total preference costs per student, adding the preference values for their assignments, i.e. $\min \max_{i \in S} \sum_{k=1}^{3} p_{is_{ik}}$ .

The capacities for the companies are given in Table 1.

Nr Company Capacity
2 SAS 5
3 Keelvar 3
4 Microsoft 10
5 Google 10
6 IBM 10
7 Cadence 5
8 Quintiq 10
9 Siemens 10
10 Cosling 3
12 LocalSolver 3
13 N-side 3
14 UTRC-I 5
15 Zoomer 5

Updated Problem (Day 2)

More students are signing up to the process, there is now an updated file test2.csv with a larger number of participating students.

In the data yesterday there were some students that had only negative preferences (5,…,5). This made it impossible to optimize the second criterion on balancing the assignment between students. As a first change we reduce the number of interviews to the minimum of three and the number of preferences given with a value less than 4. If a student only assigns preference value five, then no interviews should be scheduled. If a student only gives two preferences of value three or better, then only two interviews should be scheduled for the student.

Today, we also change the objective:

We first want to minimize the maximum regret over all students. This is the difference between the sum of the assigned preferences, and the three best indicated preferences. If a student had stated two preferences with cost one, and two with cost two, the best three choices have value four (1+1+2). If he is assigned to one interview with preference one, and two with preference two, then the assigned cost is five (1+2+2), a resulting regret of value 1. Minimizing the maximal regret is the highest priority, and then the total cost (sum of all assigned preferences) should be minimized as secondary criterion.

The companies have replied to the increased demand by also increasing the number of slots available. But they are worried that not enough student are assigned to their interviews, and they wont participate if less than half of their slots are taken. This leads to two scenarios:

  1. We can assign no students to a company, and incur a disappointment cost $d_{j}$ for the company.
  2. The number of students assigned is between a given lower and an upper bound. In this case the company is happy without extra cost.

For companies $j$, they should either be assigned no student, at a disappointment cost $d_{j}$, or be assigned at least a given minimum number of students $l_{j}$, and at most a maximum number $u_{j}$ so that they are satisfied. The data for the companies is given in Table 2.

Nr Company Disappointment Cost Min Assignment Max Assignment
1 AIMMS 10 5 10
2 SAS 10 5 10
3 Keelvar 10 3 6
4 Microsoft 10 10 20
5 Google 20 10 20
6 IBM 10 10 20
7 Cadence 5 5 10
8 Quintiq 10 10 20
9 Siemens 10 10 20
10 Cosling 5 3 6
11 COSYTEC 5 3 6
12 LocalSolver 5 3 6
13 N-side 5 3 6
14 UTRC-I 5 5 10
15 Zoomer 5 5 10

Updated Problem (Day 3)

The interview assignment process seems to be working fine, but the conference organizers see a problem with the scheduling of the interviews. The conference is run over five days (Mon-Fri), with four time periods on each day. The sessions are numbered from 1 (Monday, early morning), to 20 (Friday, late afternoon). The students can indicate five of these twenty slots, when they are available for interviews. They are not available during any other period. Otherwise the conference organizers are worried that nobody will attend the talks of the conference.

Mon Tue Wed Thu Fri
AM Early 1 5 9 13 17
AM Late 2 6 10 14 18
PM Early 3 7 11 15 19
PM Late 4 8 12 16 20

Students can only have one interview during one session, so their three interviews will occupy three of their five time slots. Companies can perform two interviews in one session. All interviews are scheduled in a set of suites, with each suite costing 200 units per week. Using a small number of suites is a good idea, as if even just one interview is scheduled in a suite, then the complete weekly rate has to be paid. Of course, each suite can hold only one interview at a time. There are at most 12 suites available.

If an interview of a company is scheduled in a period, then the company representative has to attend the conference for that day. Indeed, the company has to pay for all days between their earliest and the latest interview. If for example the first interview is in session 7 (Tue), and the latest interview in session 18 (Fri), then the company has to attend for four days (Tue, Wed, Thu, Fri), even if no interviews for them are scheduled on the Thursday. It therefore pays to group all interviews for a company together. The daily rate varies with each company, and is given in the company data below.

As the best solution yesterday allowed for a maximum of one regret only, this is now imposed as a hard constraint, so the maximal preference regret for each student is one. As all companies could be satisfied in yesterday’s optimal solution, we now have to plan for all companies getting between their lower and their upper bound of interviews, we can no longer disappoint them.

The objective now consists of the sum of the preference cost for the students, the attendance cost for the companies, and the rental cost for the interview suites. Using more suites might decrease the number of days that the companies have to attend, as more interviews can be performed in parallel, but increases the rental fee.

Data Format

The time slots for the students are given in a new file slots.csv, which on each line, lists the possible five time slots for each student.


The cost of attendance for each company is given is Table 4, which is otherwise unchanged.

Nr Company DisappointmentCost Min Assignment Max Assignment Attendance Cost
1 AIMMS 10 5 10 20
2 SAS 10 5 10 20
3 Keelvar 10 3 6 10
4 Microsoft 10 10 20 30
5 Google 20 10 20 30
6 IBM 10 10 20 30
7 Cadence 5 5 10 10
8 Quintiq 10 10 20 10
9 Siemens 10 10 20 20
10 Cosling 5 3 6 5
11 COSYTEC 5 3 6 5
12 LocalSolver 5 3 6 5
13 N-side 5 3 6 5
14 UTRC-I 5 5 10 10
15 Zoomer 5 5 10 10

Updated Problem (Day 4)

Success! People have heard about your assignment tool, and want to use it for their next conference. You can be proud of your modelling skills! There is only a small problem: This is for a major conference, with 15 companies participating, and up to 400 students that should be assigned. The corresponding preference file is testNNN.csv, the slot data are given in slotsNNN.csv, and the company data are in a file companyNNN.csv.

The file companyNNN.csv contains the company specific data in a .csv file. We’ve added a field to tell how many interviews the company can perform in parallel in each session. The data from yesterday are in the file company.csv shown in Table 5. The disappointment value is not used.

Company Disappointment Lower Upper DailyRate Parallel
AIMMS 10 5 10 20 2
SAS 10 5 10 20 2
Keelvar 10 3 6 10 2
Microsoft 10 10 20 30 2
Google 20 10 20 30 2
IBM 10 10 20 30 2
Cadence 5 5 10 10 2
Quintiq 10 10 20 10 2
Siemens 10 10 20 20 2
Cosling 5 3 6 5 2
COSYTEC 5 3 6 5 2
LocalSolver 5 3 6 5 2
N-side 5 3 6 5 2
UTRC-I 5 5 10 10 2
Zoomer 5 5 10 10 2

The new datasets are given in Table 6.

Preferences Slots Company
test2.csv slots.csv company2.csv
test100.csv slots100.csv company100.csv
test200.csv slots200.csv company200.csv
test400.csv slots400.csv company400.csv

We also may need more than 12 suites to schedule all the interviews.

Can you still provide a good assignment?