●  사용방법 · 배정 · 적재

이차 할당 (QAP)

물동량이 많은 시설끼리 가까이 놓이도록 위치를 정합니다. 설비 배치, 배선, 창고 로케이션 배정 같은 문제에 씁니다.

무엇을 정하나요

위치마다 시설 하나를 정합니다. 그래서 시설은 저마다 정확히 한 위치에 놓입니다.

최소 실행 예제

from optimaru.quadratic_assignment import solve
from optimaru.quadratic_assignment.models import QuadraticAssignmentProblemModel

problem = QuadraticAssignmentProblemModel(
    facilities=["F1", "F2", "F3"],
    locations=["L1", "L2", "L3"],
    flows=[[0, 5, 2], [5, 0, 3], [2, 3, 0]],
    distances=[[0, 8, 15], [8, 0, 13], [15, 13, 0]],
)

solve(problem, time_limit_seconds=1.0, random_seed=42)  # 그 자리에서 풉니다
print(problem.assignment, problem.total_cost)

같은 유스케이스를 그림과 실행 결과가 담긴 Jupyter 노트북으로도 볼 수 있습니다. examples/quadratic-assignment.ipynb ↗

입력 파라미터

ForbiddenAssignmentModel

필드 의미
facility 필수 입력 시설 id입니다. location 필수 입력 쓰면 안 되는 위치입니다.

QuadraticAssignmentProblemModel

필드 의미
facilities 필수 입력 시설 id 목록입니다. locations 필수 입력 위치 id 목록입니다. 시설 수와 같아야 합니다. flows 필수 입력 시설 간 물동량 행렬입니다. distances 필수 입력 위치 간 거리 행렬입니다. assignment_costs 시설×위치의 직접 비용 행렬입니다. 선택 사항입니다. fixed_assignments 위치 id별로 꼭 놓아야 할 시설입니다. forbidden_assignments 피해야 할 시설과 위치의 쌍입니다. facility_demands 시설별 수요입니다. location_capacities 위치별 용량입니다.

풀이 파라미터

풀이를 호출할 때 넘기는 값입니다. 시간 제한, 시드, 병렬 수가 여기에 있습니다.

파라미터 기본값 의미
time_limit_seconds None 탐색 시간(초)이며, 0부터 1e9까지 줄 수 있습니다. 지정하지 않으면 설정의 spent_limit_seconds를 쓰며, 기본값은 30입니다.
random_seed None 탐색에 쓰는 난수 시드입니다. 지정하지 않으면 설정값을 쓰며, 기본값은 0입니다.
parallel_solver_count None 독립적으로 동시에 돌리는 탐색 수입니다. 탐색마다 시드가 다르고 시간은 똑같이 쓰며, 가장 좋은 결과를 고릅니다. 지정하지 않으면 설정값을 쓰며, 기본값은 1입니다.
stop_at_first_feasible False 필수 점수가 0이 되는 즉시 멈춥니다.
on_new_best None 새 최고 해를 찾을 때마다 부르는 콜백입니다. 콜백이 예외를 내면 풀이를 멈추고 그 예외를 그대로 냅니다.
config None 기본으로 쓸 SolverConfig입니다. 여기서 준 키워드 인자는 이번 풀이에만 이 값을 덮어쓰며, 넘긴 객체 자체는 바뀌지 않습니다.
constraints None 점수에 넣을 제약과 그 설정입니다. 지정하지 않으면 기본 제약을 씁니다.

탐색은 두 시설을 맞바꾸기만 합니다. 다른 유스케이스가 정체를 벗어날 때 쓰는 파괴·재구성은 일대일 대응을 깨기 때문입니다. 그래서 기본값인 늦은 수락(late acceptance)은 교환으로는 더 나아지지 않는 국소 최적해에 이르면 개선을 멈춥니다. 그러면 긴 탐색 시간의 상당 부분이 헛돌 수 있고, 돌려받은 해를 다시 풀어도 좀처럼 나아지지 않습니다. unimproved_spent_limit_seconds나 unimproved_step_count_limit으로 일찍 멈추거나, parallel_solver_count로 독립적인 탐색을 여럿 돌리거나, acceptor_type을 RECORD_TO_RECORD_TRAVEL이나 SIMULATED_ANNEALING으로 바꾸세요. 모의 담금질(simulated annealing)은 온도가 내려가는 동안에도 나빠지는 교환을 일부 받아들이므로 그 국소 최적해를 벗어날 수 있습니다. 시작 온도는 시작 해 선호 점수의 절댓값에 simulated_annealing_temperature_fraction을 곱한 값이고, simulated_annealing_starting_temperature를 주면 그 값을 씁니다. 온도는 시간 제한에 맞춰 0까지 내려가며, step_count_limit이 더 많이 진행됐다면 걸음 수에 맞춰 내려갑니다. ENTITY_TABU는 점수를 나쁘게 하지 않는 교환만 받아들입니다.

탐색 옵션 전체 (14)

SolverConfig에 값을 넣어 config=로 넘기세요.

파라미터 기본값 의미
acceptor_type LATE_ACCEPTANCE 이동을 받아들일지 판단하는 규칙입니다.
best_score_limit — 최고 점수가 이 값에 닿으면 일찍 멈춥니다. 기본값으로는 작동하지 않습니다.
entity_tabu_size 7 ENTITY_TABU 수락 방식의 타부 기간(tabu tenure)입니다.
full_assert False 증분 점수를 전체 재계산과 매번 비교합니다. 느리므로 디버깅할 때만 씁니다.
late_acceptance_size 0 늦은 수락(late acceptance) 기록의 길이입니다. 0이면 문제 크기에 맞춰 정합니다.
on_new_best None 새 최고 해를 찾을 때마다 부르는 콜백입니다. 콜백이 예외를 내면 풀이를 멈추고 그 예외를 그대로 냅니다.
parallel_solver_count 1 독립적으로 동시에 돌리는 탐색 수입니다. 탐색마다 시드가 다르고 시간은 똑같이 쓰며, 가장 좋은 결과를 고릅니다.
random_seed 0 탐색에 쓰는 난수 시드입니다.
simulated_annealing_starting_temperature (0, 0.0) SIMULATED_ANNEALING 수락 방식의 시작 온도를 (hard, soft)로 줍니다. (0, 0.0)이면 시작 해를 보고 자동으로 정합니다. 필수는 0, 선호는 시작 해 선호 점수의 절댓값에 simulated_annealing_temperature_fraction을 곱한 값이며, 1보다 작아지지 않습니다. 온도는 시간 제한에 맞춰 0까지 내려가고, step_count_limit이 더 많이 진행됐다면 걸음 수에 맞춰 내려갑니다.
simulated_annealing_temperature_fraction 0.01 시작 온도를 자동으로 정할 때 시작 해 선호 점수의 절댓값에 곱하는 비율입니다. 0보다 커야 합니다.
spent_limit_seconds 30.0 탐색 시간(초)이며, 0부터 1e9까지 줄 수 있습니다.
step_count_limit 0 이 걸음 수에 도달하면 멈춥니다. 0이면 제한이 없습니다.
unimproved_spent_limit_seconds 0.0 새 최고 해 없이 이 시간(초)이 지나면 멈춥니다. 0이면 제한이 없습니다.
unimproved_step_count_limit 0 새 최고 해 없이 이 걸음 수가 지나면 멈춥니다. 0이면 제한이 없습니다.

돌아오는 결과

solve는 problem을 그 자리에서 채우고 엔진 Score를 돌려줍니다. 값은 .hard와 .soft로 읽습니다. problem.to_core()로 만든 엔진 객체도 받습니다.

QuadraticAssignmentProblemModel

필드 의미
assignment 위치 id별로 놓인 시설 id입니다. total_cost 물동량에 배정된 거리를 곱해 더한 값입니다. score_hard 필수 점수입니다. 0이면 가능한 해입니다. score_soft 선호 점수입니다.

제약

optimaru.quadratic_assignment.constraints에서 클래스를 가져와 PinnedAssignmentsCost()처럼 호출해서 넘깁니다. 넘긴 제약만 점수에 들어가고, 아무것도 넘기지 않으면 기본 제약을 씁니다. 목록에 같은 제약을 여러 번 넣을 수 있으며, 넣은 것마다 따로 점수에 들어갑니다. 제약마다 다음 파라미터를 받습니다.

파라미터 기본값 의미
weight None 제약 비용에 곱하는 값이며, 적용되는 수준의 단위로 셉니다. 지정하지 않으면 아래 기본 가중치를 씁니다. 기본 가중치가 0인 제약은 가중치를 줘야 작동합니다.
level None "hard"면 필수, "soft"면 선호로 바꿉니다. Level.HARD, Level.SOFT도 됩니다. 지정하지 않으면 아래 수준을 그대로 씁니다. 이 유스케이스에는 중간 수준이 없어서 "medium"을 주면 ValueError가 납니다. 보상에 "hard"를 주거나 수준이 고정된 제약의 수준을 바꾸려 해도 ValueError가 납니다.
exponent 1.0 부호를 유지한 채 비용에 거듭제곱을 적용하며, 0보다 커야 합니다. offset을 반영한 뒤에 적용합니다. 2.0이면 제곱이라 한곳에 몰린 위반의 비용이 크게 늘어납니다. 차량이나 날짜 같은 단위마다 적용하고, 합계 하나로 계산하는 제약에는 그 합계에 적용합니다.
offset 0.0 거듭제곱 전에 비용 x에서 빼는 값입니다. exponent처럼 단위마다, 합계로 계산하는 제약은 그 합계에 적용하며, 비용과 같은 척도(초, 분, 개수 등)로 셉니다. 부호와 상관없이 유한한 수면 되고, 키워드로만 줄 수 있습니다. 이 값 아래에서 어떻게 계산할지는 clip이 정합니다.
clip True True면 offset을 문턱값으로 씁니다. 넘은 부분만 계산하므로(max(0, x - offset) ** exponent) 그 이하의 비용은 아무것도 더하지 않습니다. False면 부호를 유지한 채 (x - offset) ** exponent를 그대로 계산하므로, 오프셋보다 작은 단위는 비용이 0이어도 음수, 곧 보상으로 들어갑니다. 하드 점수에 들어가는 수준에서는 clip=False에 0이 아닌 오프셋을 주면 ValueError가 납니다. 하드 0이 위반 없음이라는 뜻을 지키기 위해서입니다. 키워드로만 줄 수 있습니다.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.quadratic_assignment.constraints import FlowDistanceCost, PinnedAssignmentsCost

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=1.0, random_seed=42,
            constraints=[PinnedAssignmentsCost(), FlowDistanceCost(weight=2)]))
이름 수준 기본 가중치 하는 일
pinned_assignments_cost 필수 1 고정된 위치 배정을 어기면 벌점을 줍니다.
forbidden_assignments_cost 필수 1 금지된 시설과 위치 쌍을 쓰면 벌점을 줍니다.
location_capacity_cost 필수 1 시설 수요가 위치 용량을 넘으면 벌점을 줍니다.
assignment_cost 선호 1 시설과 위치의 직접 비용을 줄입니다.
flow_distance_cost 선호 1 물동량에 배정된 위치 사이의 거리를 곱한 값의 합을 줄입니다.

제약 사용법 →

기존 해에서 시작하기

최신 버전이 필요합니다. pip install -U optimaru로 올려 주세요.

with_initial_solution(problem, solution)은 solution에서 탐색을 시작하는 problem의 복사본을 돌려줍니다. solution은 풀린 모델이나 그 JSON 딕셔너리입니다.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.quadratic_assignment import with_initial_solution

warm = with_initial_solution(problem, problem.model_dump(mode="json"))
solve(warm, time_limit_seconds=1.0, random_seed=42)
print(warm.assignment, warm.total_cost)
  • 다른 유스케이스와 달리 여기서는 일부만 넣은 해로 시작할 수 없습니다. assignment는 위치와 시설이 일대일로 모두 대응해야 합니다. 일부만 있거나, 모르는 id가 있거나, 시설이 반복되면 ValueError가 납니다. 탐색은 두 시설을 맞바꾸기만 하므로 거치는 해는 모두 일대일 대응을 유지합니다.
  • time_limit_seconds=0을 주면 바로 멈추므로 완전한 해는 넣은 그대로 돌아옵니다. step_count_limit = 0은 제한이 없다는 뜻이므로, 바로 멈추려면 시간 제한을 쓰세요.

예외와 제한

  • facilities, locations, flows, distances는 크기가 같고 행렬은 정사각이어야 합니다.