OR-Tools Day9

실습 코드

# ------------------ Day8(25.06.15) ------------------
'''
간단한 시간표 문제를 해결하기 위한 예시 데이터
'''

# 교사 목록
teachers = ['T1', 'T2', 'T3']

# 과목 목록
subjects = ['Math', 'English', 'Science']

# 학급 목록
classes = ['1A', '1B']

# 교실 목록
rooms = ['R1', 'R2']

# 시간 슬롯(교시)
time_slots = [1, 2, 3, 4, 5]

# 각 반의 시수
class_subject_requirements = {
    '1A': {'Math': 2, 'English': 2, 'Science': 1},
    '1B': {'Math': 2, 'English': 1, 'Science': 2}
}

# 교사별 담당 과목
teacher_subjects = {
    'T1': ['Math'],
    'T2': ['English'],
    'T3': ['Science']
}

from ortools.sat.python import cp_model

model = cp_model.CpModel()
x = {}

for c in classes:
    for t in time_slots:
        for s in subjects:
            for teacher in teachers:
                if s in teacher_subjects[teacher]: # 교사가 해당 과목을 가르칠 수 있을 때만
                    for room in rooms:
                        x[c, t, s, teacher, room] = model.NewBoolVar(f'x_{c}_{t}_{s}_{teacher}_{room}')

# 한 반은 한 시간에 한 과목
for c in classes:
    for t in time_slots:
        model.Add(sum(x[c, t, s, teacher, room]
                      for s in subjects
                      for teacher in teachers if s in teacher_subjects[teacher]
                      for room in rooms
                      ) <= 1
                  )

# 반별 시수
for c in classes:
    for s in subjects:
        model.Add(sum(x[c, t, s, teacher, room]
                      for t in time_slots
                      for teacher in teachers if s in teacher_subjects[teacher]
                      for room in rooms
                      ) == class_subject_requirements[c][s]
                  )

# 한 교사는 한 시간에 한 반만 가르칠 수 있다.
for teacher in teachers:
    for t in time_slots:
        model.Add(sum(x[c, t, s, teacher, room]
                      for c in classes
                      for s in subjects if s in teacher_subjects[teacher]
                      for room in rooms
                      ) <= 1
                  )

# 한 교실은 한 시간에 한 반만 사용
for room in rooms:
    for t in time_slots:
        model.Add(sum(x[c, t, s, teacher, room]
                      for c in classes
                      for s in subjects
                      for teacher in teachers if s in teacher_subjects[teacher]
                      ) <= 1
                  )

solver = cp_model.CpSolver()
status = solver.Solve(model)

# if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
#     for c in classes:
#         print(f'\n{c} 시간표:')
#         for t in time_slots:
#             for s in subjects:
#                 for teacher in teachers:
#                     if s in teacher_subjects[teacher]:
#                         for room in rooms:
#                             if solver.Value(x[c, t, s, teacher, room]):
#                                 print(f'   {t}교시: {s} ({teacher}, {room})')
# else:
#     print('해를 찾을 수 없습니다.')



# ------------------ Day9(25.06.15) ------------------

# 1. 시간표 출력 가독성 높이기(해당 시간 수업 없는 경우)
for c in classes:
    print(f'\n{c} 시간표:')
    for t in time_slots:
        found = False
        for s in subjects:
            for teacher in teachers:
                if s in teacher_subjects[teacher]:
                    for room in rooms:
                        if solver.Value(x[c, t, s, teacher, room]):
                            print(f'   {t}교시: {s} ({teacher}, {room})')
                            found = True
        if not found:
            print(f'   {t}교시: 수업 없음')

'''
1A 시간표:
   1교시: Science (T3, R1)
   2교시: Math (T1, R2)
   3교시: Math (T1, R2)
   4교시: English (T2, R1)
   5교시: English (T2, R2)

1B 시간표:
   1교시: Math (T1, R2)
   2교시: English (T2, R1)
   3교시: Science (T3, R1)
   4교시: Science (T3, R2)
   5교시: Math (T1, R1)
'''

# 2. 여러 해 탐색

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, x, classes, time_slots, subjects, teachers, rooms, teacher_subjects, limit=5):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.x = x
        self.classes = classes
        self.time_slots = time_slots
        self.subjects = subjects
        self.teachers = teachers
        self.rooms = rooms
        self.teacher_subjects = teacher_subjects
        self.solution_count = 0
        self.limit = limit

    def on_solution_callback(self):
        self.solution_count += 1
        print(f'\n=== Solution {self.solution_count} ===')
        for c in self.classes:
            print(f'\n{c} 시간표:')
            for t in self.time_slots:
                found = False
                for s in self.subjects:
                    for teacher in self.teachers:
                        if s in self.teacher_subjects[teacher]:
                            for room in self.rooms:
                                if self.Value(self.x[c, t, s, teacher, room]):
                                    print(f'  {t}교시: {s} ({teacher}, {room})')
                                    found = True
                if not found:
                    print(f'  {t}교시: 수업 없음')
        if self.solution_count >= self.limit:
            print(f'--- {self.limit}개 해까지만 출력합니다 ---')
            self.StopSearch()

solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(x, classes, time_slots, subjects, teachers, rooms, teacher_subjects, limit=3)
solver.SearchForAllSolutions(model, solution_printer)

'''
=== Solution 1 ===

1A 시간표:
  1교시: Math (T1, R2)
  2교시: English (T2, R1)
  3교시: English (T2, R2)
  4교시: Science (T3, R2)
  5교시: Math (T1, R2)

1B 시간표:
  1교시: Science (T3, R1)
  2교시: Science (T3, R2)
  3교시: Math (T1, R1)
  4교시: Math (T1, R1)
  5교시: English (T2, R1)

=== Solution 2 ===

1A 시간표:
  1교시: Science (T3, R1)
  2교시: Math (T1, R1)
  3교시: English (T2, R2)
  4교시: English (T2, R1)
  5교시: Math (T1, R2)

1B 시간표:
  1교시: Math (T1, R2)
  2교시: Science (T3, R2)
  3교시: Science (T3, R1)
  4교시: Math (T1, R2)
  5교시: English (T2, R1)

=== Solution 3 ===

1A 시간표:
  1교시: Science (T3, R1)
  2교시: English (T2, R2)
  3교시: English (T2, R2)
  4교시: Math (T1, R2)
  5교시: Math (T1, R2)

1B 시간표:
  1교시: Math (T1, R2)
  2교시: Science (T3, R1)
  3교시: Math (T1, R1)
  4교시: Science (T3, R1)
  5교시: English (T2, R1)
--- 3개 해까지만 출력합니다 ---
'''

# 3. 해가 없을 때(UNSATISFIABLE) 원인 분석 및 대처
if status == cp_model.INFEASIBLE:
    print('해를 찾을 수 없습니다.')
'''
원인:

제약조건이 너무 빡빡하거나,

데이터(수업시수, 교실/교사 수, 시간 수 등)가 현실적으로 불가능한 경우

대처법:

제약조건을 하나씩 풀어보며 원인 찾기
(예: 과목별 수업시수를 줄이거나, 교사/교실 수를 늘려보기)

충돌이 많은 제약조건에 대해 로그 출력
(예: 어떤 반이 어떤 시간에 수업이 배정되지 못하는지 확인)

OR-Tools의 model.Validate() 사용
(명시적으로 오류를 알려주진 않지만, 제약조건 오류를 미리 점검 가능)
'''