Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
from Numberjack import *
from validator import read_instance_day3, MAX_NUMBER_INTERVIEWS, MAX_ACCEPTABLE_PREF_VALUE
import csv
 
 
def get_day2_model(all_student_preferences, company_data):
    num_students = len(all_student_preferences)
    assert num_students > 0
    num_companies = len(all_student_preferences[0])
    assert len(company_data) == num_companies
 
    model = Model()
    all_student_rows, all_student_variables = [], []
    obj1_variables, obj1_coefficients = [], []
 
    for student_id, student_preferences in enumerate(all_student_preferences):
        num_expected_interviews = MAX_NUMBER_INTERVIEWS
        num_valid_preferences = sum(
            1 if pref_val < MAX_ACCEPTABLE_PREF_VALUE else 0 for pref_val in student_preferences
        )
        num_expected_interviews = min(num_expected_interviews, num_valid_preferences)
 
        if num_expected_interviews == 0:
            print "Ignoring student", student_id+1
            all_student_rows.append([])
            continue
 
        # FD variable 0..num_companies-1 deciding which company this student interviews, for
        # each one of their 'num_expected_interviews'
        student_variables = VarArray(
            num_expected_interviews, num_companies, "student%d" % (student_id+1)
        )
        all_student_rows.append(student_variables)
        all_student_variables.extend([x for x in student_variables])
 
        # Each of the assignments for a student must be different, redundant with ordering below
        model += AllDiff(student_variables)
 
        # Break symmetry by enforcing ordering on the row
        for i in range(len(student_variables)-1):
            model += student_variables[i] < student_variables[i+1]
 
        student_regret_vars, student_regret_coeffs = [], []
        for company_id, preference_value in enumerate(student_preferences):
            for cell in student_variables:
                obj1_variables.append(cell == company_id)
                obj1_coefficients.append(preference_value)
 
                student_regret_vars.append(cell == company_id)
                student_regret_coeffs.append(preference_value)
 
        # Enforce that the regret is 1 (i.e. the sum of pref == vbregret+1)
        virtual_best_regret = sum(sorted(student_preferences)[:num_expected_interviews])
        model += Sum(student_regret_vars, student_regret_coeffs) <= virtual_best_regret + 1
 
    # Cardinality constraint limiting the number of students assigned to each company
    gcc_cap_limits = {}
    for company_id, (dissappointment_cost, min_assignment, max_assignment, attendance_cost) in \
            enumerate(company_data):
        gcc_cap_limits[company_id] = [min_assignment, max_assignment]
    model += Gcc(all_student_variables, gcc_cap_limits)
 
    obj = Sum(obj1_variables, obj1_coefficients)
    model += Minimise(obj)
 
    return model, all_student_rows, obj
 
 
def output_assignments(all_student_rows, filename):
    with open(filename, "wt") as f:
        writer = csv.writer(f)
        writer.writerow(["StudentNr", "CompanyNr"])
        for student_id, student_row in enumerate(all_student_rows):
            for assigned_variable in student_row:
                # +1 for one-based indexing instead of zero-based
                writer.writerow([student_id + 1, assigned_variable.get_value() + 1])
 
 
def main(param):
    all_student_preferences, company_data = read_instance_day3(param['instance'])
 
    model, all_student_rows, obj = get_day2_model(all_student_preferences, company_data)
 
    if param['verbosity'] >= 3:
        print model
 
    solver = model.load(param['solver'])
    solver.setVerbosity(param['verbosity'])
    solver.setTimeLimit(param['timelimit'])
    solver.solve()
 
    if solver.is_sat():
        print "SAT"
        print "Obj:", obj.get_value()
        for row in all_student_rows:
            print row
        output_assignments(all_student_rows, param['solution'])
    elif solver.is_unsat():
        print "UNSAT"
    else:
        print "Unknown"
 
 
if __name__ == '__main__':
    default = {
        'instance': 'testproblems/2/preferences.csv',
        'solution': 'njsolution-day2.csv',
        'solver': 'CPLEX',
        'verbosity': 1,
        'timelimit': 60,
    }
    param = input(default)
    main(param)