optimaru 사용방법

설치

pip install optimaru

Python 3.11 이상이 필요합니다. Linux, macOS, Windows용 CPython 3.11~3.14 휠을 제공하며 pydantic도 함께 설치됩니다.

유스케이스는 저마다 optimaru.<name> 하위 패키지입니다. 처음 쓸 때 불러오므로 import optimaru 자체는 가볍습니다.

이 문서는 optimaru 0.3 기준입니다. 이전 버전은 pip install -U optimaru로 올리세요.

기본 흐름

1. optimaru.<name>.models의 모델로 문제를 만듭니다. 학교 시간표는 일반 딕셔너리를 받습니다.
2. 시간 제한과 시드를 주고 솔버를 호출합니다. 시간 제한을 주지 않으면 탐색 시간은 30초입니다.
3. 점수와 결정 필드를 읽습니다. 유스케이스 페이지마다 어떤 필드인지 적어 두었습니다.
4. 제약을 조정하거나, 결과에서 이어서 풉니다.

from optimaru.knapsack import solve
from optimaru.knapsack.models import ItemModel, KnapsackProblemModel

problem = KnapsackProblemModel(
    capacity=10,
    items=[
        ItemModel(id="A", weight=6, value=9),
        ItemModel(id="B", weight=4, value=7),
        ItemModel(id="C", weight=5, value=8),
    ],
)

score = solve(problem, time_limit_seconds=1.0, random_seed=42)
print(score, [item.id for item in problem.items if item.selected])

점수는 필수를 먼저 비교하고, 중간 수준이 있는 유스케이스는 그다음 중간을, 마지막으로 선호를 비교합니다. 필수 점수가 0이면 필수 제약을 모두 지킨 것입니다. 탐색은 시간 안에 찾은 가장 좋은 해를 돌려줄 뿐, 그 해가 최적임을 증명하지는 않습니다.

점수에는 범위가 있습니다. 가중치를 곱한 기여분은 차량이나 날짜 같은 단위마다 따지고, 합계 하나로 계산하는 제약은 그 합계로 따집니다. 기여분은 모두 유한해야 하고, 필수 기여분은 2^62(약 4.6e18)보다 작아야 합니다. 그렇지 않으면 풀 때든 점수를 계산할 때든 그 제약의 이름을 담은 OverflowError가 납니다. 필수 점수의 합은 범위를 넘어도 부호가 뒤집히지 않고 −(2^63 − 1)에서 멈추므로, 벌점이 더 큰 해가 더 좋아 보이는 일은 없습니다.

호출 방식은 유스케이스마다 조금씩 다릅니다.

파라미터

유스케이스 페이지마다 입력 모델 필드, 풀이 파라미터, 탐색 옵션 전체를 기본값과 함께 적어 두었습니다.

가장 자주 쓰는 것은 시간 제한, 시드, 병렬 수입니다.

time_limit_seconds, spent_limit_seconds, unimproved_spent_limit_seconds 같은 시간 제한은 0 이상 1e9초(약 31.7년) 이하의 유한한 값이어야 합니다. 무한대를 비롯해 그 밖의 값은 ValueError를 냅니다. step_count_limit으로만 멈추려면 그 걸음 수를 다 채울 만큼 넉넉한 시간 제한을 주세요.

on_new_best 콜백이 예외를 내면 solve도 그 예외를 냅니다. 병렬로 돌리는 중이면 다른 탐색도 다음 걸음에서 멈추므로 오류가 곧바로 전달됩니다.

모의 담금질(simulated annealing)은 반도체 팹 스케줄링의 기본 수락 방식이고, 이차 할당에서는 acceptor_type으로 고를 수 있습니다. 온도는 시간 제한에 맞춰 내려가고, step_count_limit이 더 많이 진행됐다면 걸음 수에 맞춰 내려갑니다. 그래서 시드와 걸음 수 제한을 준 풀이는 걸음 수가 시간보다 앞서 가는 한 매번 같은 결과를 냅니다.

제약 사용법

업무 규칙과 선호 조건은 모두 이름, 수준, 가중치를 가진 제약 플러그인입니다. 제약은 비용으로 계산하므로 이름이 모두 _cost로 끝나며, 비용이 0이면 제약을 지켰다는 뜻입니다. 유스케이스의 list_constraints()로 이름을, constraint_info()로 제약마다 기본 수준과 가중치를 볼 수 있습니다.

제약은 클래스를 호출해 고릅니다. optimaru.vehicle_routing.constraints의 VehicleCapacityCost()처럼 씁니다. 클래스는 모두 같은 다섯 설정을 받습니다. weight=None, level=None, exponent=1.0과, 키워드로만 주는 offset=0.0, clip=True입니다. None이면 그 제약의 기본값을 씁니다.

• 켜고 끄기. 목록을 넘기면 그 제약만 점수에 들어갑니다. 빠진 제약은 점수에서 사라집니다. 빈 목록은 오류입니다.
• 가중치 바꾸기. TravelTimeCost(weight=10)은 비용에 가중치 10을 곱하며, 가중치는 적용되는 수준의 단위로 셉니다. exponent=2.0은 비용을 제곱하므로 한곳에 몰린 위반의 비용이 커집니다.
• 수준. level="hard"는 필수, level="soft"는 선호로 바꿉니다. 같은 모듈의 Level.HARD, Level.SOFT도 됩니다. 지정하지 않으면 기본 수준을 그대로 씁니다. "medium"은 중간 수준이 있는 8개 유스케이스(차량 경로 최적화 (VRP), 픽업 · 배송 (PDPTW), 프로젝트 일정 (RCPSP), 생산 라인 순서 계획, 업무 배정, 회의 일정, 대회 일정, 병상 배정)에만 있고, 여기서는 어느 제약이든 중간으로 옮길 수 있습니다. 다른 유스케이스에서 "medium"을 주면 ValueError가 납니다. 수준이 고정된 제약은 수준을 바꿀 수 없습니다.
• 보상. 일부 제약은 보상입니다. 비용이 0 이하여서 가중치를 올리면 점수가 올라갑니다. 보상에 level="hard"를 주면 ValueError가 납니다. 페이지마다 제약 표에 표시해 두었습니다.
• 오프셋과 클립. offset은 거듭제곱 전에 비용 x에서 빼는 값입니다. exponent처럼 단위마다 적용하며, 초나 개수처럼 비용과 같은 척도로 셉니다. 기본값인 clip=True면 오프셋은 문턱값입니다. TravelTimeCost(offset=10, exponent=3)은 차량마다 max(0, x - 10)**3을 매기므로, 10 이하인 차량은 아무것도 더하지 않습니다. clip=False면 식을 그대로 계산해 부호를 유지한 (x - 10)**3을 매기므로, 10보다 작은 차량은 쉬는 차량까지 음수, 곧 보상으로 들어갑니다. 보상 제약에 문턱값을 주면 오프셋을 넘은 부분만 보상합니다. offset=0이면 두 방식 모두 원래 비용과 같습니다. 하드 제약은 clip=False에 0이 아닌 오프셋을 주면 ValueError로 거절합니다. 하드 0이 위반 없음이라는 뜻을 지키기 위해서이니, 하드에서는 문턱값을 쓰거나 제약을 소프트로 옮기세요.
• 여러 번 고르기. 같은 제약을 목록에 여러 번 넣을 수 있습니다. 넣은 것마다 설정과 수준을 따로 가진 별개의 제약으로 계산하고 결과를 더합니다. [TravelTimeCost(exponent=2), TravelTimeCost(exponent=3)]은 x**2 + x**3을 매깁니다. constraint_costs()는 첫 번째를 이름 그대로, 그다음부터는 travel_time_cost#2, travel_time_cost#3처럼 구분합니다. 학교 시간표의 Assembly는 예외로, 이름마다 하나만 두고 add()하면 그 항목을 바꿉니다.
• 기본 가중치가 0인 제약은 가중치를 줘야 작동합니다.

from optimaru import vehicle_routing as vrp
from optimaru.vehicle_routing.constraints import (
    MaxEndTimeCost, TravelTimeCost, UnassignedVisitsCost, VehicleCapacityCost, get_constraints,
)
from optimaru.vehicle_routing.models import (
    RoutePlanRequest, RoutingInput, VehicleModel, VisitModel, solve_request,
)

print(vrp.list_constraints())  # 이 유스케이스의 제약 이름 전체

request = RoutePlanRequest(
    timelimit=2,
    model_input=RoutingInput(
        vehicles=[VehicleModel(id="V1", capacity=10, depot=(37.5665, 126.9780))],
        visits=[VisitModel(id="A", location=(37.5700, 126.9820), demand=3, service_duration=600)],
    ),
)

# 점수에 넣을 제약을 고릅니다. 빠진 제약은 꺼집니다
solution = solve_request(request, constraints=get_constraints([
    VehicleCapacityCost(),                    # 그대로 켭니다
    UnassignedVisitsCost(),                   # 그대로 켭니다
    TravelTimeCost(weight=10),                # 가중치를 바꿉니다
    MaxEndTimeCost(level="soft"),             # 필수를 선호로 바꿉니다
    TravelTimeCost(exponent=2, offset=3600),  # 한 번 더 고릅니다: (차량마다 1시간을 넘은 운전 시간)**2
]))
print(solution.score, solution.routes)

유스케이스마다 constraints 모듈에 get_constraints가 있고, constraints=에는 일반 목록을 넘겨도 됩니다. 학교 시간표는 Assembly도 받고, 직원 근무표는 규칙을 model_input.rules에 넣습니다. 실제 호출은 페이지마다 보여 드립니다.

constraints=를 쓰면 탐색 하나로만 풀기 때문에 병렬 수가 적용되지 않습니다.

기존 해에서 시작하기

모든 유스케이스는 해를 새로 만드는 대신 이미 있는 해에서 시작할 수 있습니다. 이전 풀이의 결과를 모델 그대로 넘기거나 JSON으로 넘기면 됩니다. 최신 버전이 필요합니다.

pip install -U optimaru

from optimaru.vehicle_routing.models import with_initial_solution

first = solve_request(request)
better = solve_request(with_initial_solution(request, first))  # first.model_dump(mode="json")도 됩니다
print(better.score)

• 완전한 해를 넣으면 구성 단계를 건너뛰고 그 해에서 바로 탐색을 시작합니다.
• 일부만 넣으면 넣은 부분은 그대로 두고, 빠진 부분만 새로 구성합니다.
• 풀이가 돌려준 결과라면 필수 제약을 어긴 해도 받습니다. 다만 픽업 · 배송은 픽업과 배송의 짝이 깨진 경로를 받지 않습니다.
• 항목은 위치가 아니라 id로 맞춥니다. 모르는 id나 범위를 벗어난 값은 ValueError를 냅니다.
• with_initial_solution은 새 문제를 돌려주고 입력은 바꾸지 않습니다.
• 고정된 부분은 문제의 일부입니다. 대부분의 유스케이스는 해의 내용을 무시하고 문제에 있는 값을 유지합니다. 생산 라인 순서 계획, 픽업 · 배송, 맥스컷, 학교 시간표, 직원 근무표는 해가 그 값과 어긋나면 ValueError를 냅니다.
• 시작 해는 한 번만 쓰입니다. 결과를 고쳐서 다시 풀면 구성 단계부터 시작하므로, with_initial_solution을 다시 거쳐야 합니다.
• 학교 시간표는 딕셔너리를 쓰므로 키워드로 넘깁니다. solve(problem, initial_solution=previous)처럼 씁니다.
• 시간 제한을 0으로 주면 바로 멈춥니다. step_count_limit = 0은 제한이 없다는 뜻이므로, 바로 멈추려면 시간 제한을 쓰세요.

예외는 페이지마다 적어 두었습니다. 두 가지를 더 기억해 두세요. 이차 할당은 완전한 해만 받습니다. 생산 라인 순서 계획은 1ms 이하면 구성 단계 전에 돌아오므로 일부만 넣은 해가 그대로 남습니다.

예제 노트북

optimaru 저장소에는 유스케이스마다 Jupyter 노트북이 하나씩 있습니다. 노트북마다 작은 문제를 만들어 풀고, 결과를 그림으로 보여 주고, 검증한 다음 규칙을 바꿔 봅니다. 실행 결과까지 저장되어 있어 직접 실행하지 않아도 GitHub에서 바로 읽을 수 있습니다. 노트북은 optimaru 0.3이 필요하며, 저장된 결과도 0.3으로 실행한 것입니다.

pip install "optimaru>=0.3" matplotlib jupyter

GitHub에서 노트북 전체 보기 ↗

유스케이스 전체