Google OR-Tools 도구로 해집합 프로그래밍하기
팀의 완벽한 일정을 직접 짜 보거나 배송 경로를 계획해 본 적이 있습니까? 이럴 때 Google OR-Tools가 등장합니다. 이 무료 툴킷은 이처럼 골치 아픈 최적화 문제를 해결해 주는 맥가이버 칼 같은 도구입니다. 제약 프로그래밍부터 선형 프로그래밍, 특화된 경로 탐색 솔버에 이르기까지, 컴퓨터 과학의 복잡한 퍼즐을 푸는 데 필요한 모든 도구를 갖추고 있습니다. 또한 Google이 유지 관리하고 개선하므로, 최적화 알고리즘을 처음부터 다시 만들 필요 없이 여러분의 구체적인 문제를 해결하는 데 집중할 수 있습니다.
다음은 여러 제약 조건을 만족하면서 팀원을 선발해야 하는 간단한 예제입니다:
from ortools.sat.python import cp_model
model = cp_model.CpModel()
persons = ['Tony', 'Bob', 'Ann', 'Carl', 'Amber', 'Peter']
person_vars = {p: model.NewBoolVar(p) for p in persons}
# Select exactly 2 people from group1
group1 = ['Bob', 'Ann', 'Carl', 'Amber', 'Peter']
model.Add(sum(person_vars[p] for p in group1) == 2)
# Select exactly 1 person from group2
group2 = ['Bob', 'Amber']
model.Add(sum(person_vars[p] for p in group2) == 1)
# Amber must be selected
model.Add(person_vars['Amber'] == 1)
# Total team size must be 4
model.Add(sum(person_vars.values()) == 4)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print("Solution found:")
for person, var in person_vars.items():
if solver.Value(var):
print(person)
else:
print("No solution found.")
이런 종류의 문제의 또 다른 대표적인 예는 강의 시간표 작성입니다:
from ortools.sat.python import cp_model
def create_course_schedule():
model = cp_model.CpModel()
# Parameters
num_time_slots = 5 # Time slots per day
num_rooms = 3
courses = ['Math', 'Physics', 'Chemistry', 'Biology', 'English']
teachers = ['Smith', 'Johnson', 'Williams']
# Decision variables
slots = {}
for course in courses:
for time in range(num_time_slots):
for room in range(num_rooms):
slots[(course, time, room)] = model.NewBoolVar(f'{course}_{time}_{room}')
# Each course must be scheduled exactly once
for course in courses:
model.Add(sum(slots[(course, t, r)]
for t in range(num_time_slots)
for r in range(num_rooms)) == 1)
# Only one course per room per time slot
for time in range(num_time_slots):
for room in range(num_rooms):
model.Add(sum(slots[(c, time, room)] for c in courses) <= 1)
# Solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print("\nSchedule:")
for time in range(num_time_slots):
print(f"\nTime Slot {time + 1}:")
for room in range(num_rooms):
for course in courses:
if solver.Value(slots[(course, time, room)]):
print(f"Room {room + 1}: {course}")
else:
print("No solution found.")
create_course_schedule()
거리 행렬은 각 위치 쌍 사이의 거리를 나타내며, 각 행과 열은 하나의 위치(창고 또는 고객)에 대응합니다. 예를 들어 distances[1][2] = 6은 고객 1에서 고객 2까지 이동하는 데 6단위가 걸린다는 뜻입니다. 이 행렬은 대칭 행렬이므로, A에서 B까지의 거리는 B에서 A까지의 거리와 같습니다. 첫 번째 행/열(인덱스 0)은 창고를 나타내고, 그 이후의 인덱스는 고객을 나타냅니다.
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_delivery_route():
# Distance matrix
distances = [
[0, 2, 9, 10], # Depot
[2, 0, 6, 8], # Customer 1
[9, 6, 0, 3], # Customer 2
[10, 8, 3, 0], # Customer 3
]
manager = pywrapcp.RoutingIndexManager(len(distances), 1, 0)
routing = pywrapcp.RoutingModel(manager)
def distance_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return distances[from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
solution = routing.SolveWithParameters(search_parameters)
if solution:
print("Optimal delivery route:")
index = routing.Start(0)
route = ['Depot']
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
if not routing.IsEnd(index):
route.append(f'Customer {manager.IndexToNode(index)}')
route.append('Depot')
print(' -> '.join(route))
create_delivery_route()