두 배정이 함께 만드는 비용
시설 사이의 이동량과 위치 사이의 거리가 주어진 배치 문제를 생각할 수 있다. 시설 i와 j를 어느 위치에 두느냐에 따라 이동량에 곱해지는 거리가 달라진다. 이 대칭적인 예제 모형에서는 서로 다른 시설 쌍을 한 번씩 세어 이동량과 거리의 곱을 더한다. 배정 하나의 비용을 미리 고정하는 선형 할당과 다른 점이다.
세 시설의 배치 예제
위치가 직선 위의 0,1,5이고 시설 A와 B 사이 이동량은 10, 나머지 두 쌍은 각각 1이라고 하자. A,B,C를 각각 0,1,5에 두면 총비용은 10×1+1×5+1×4=19이다. A,B,C를 0,5,1에 두면 10×5+1×1+1×4=55이다. 이동량이 큰 두 시설을 멀리 배치한 선택이 다른 쌍의 거리에도 영향을 준다.
행렬과 그래프의 대응
이동량과 거리를 각각 행렬로 나타내고 배정을 순열 행렬로 표현할 수 있다. 행렬의 행과 열 순서를 함께 바꾸는 구조는 두 그래프의 꼭짓점 대응을 찾는 문제와도 관련된다. 다만 목적값을 최소화하는 배치 문제와 유사성을 최대화하는 그래프 대응에서는 부호와 목적을 확인해야 한다. 대칭 비용을 양방향으로 모두 더하면 앞 예제처럼 한 번씩 센 값과 수치가 달라진다.
해법과 보장
일반적인 이차 할당 문제는 NP 난해하다. 작은 문제는 순열을 모두 비교할 수 있지만 시설 수가 커지면 경우의 수가 빠르게 늘어난다. 근사법이나 국소 개선 방법은 좋은 배치를 찾을 수 있어도 항상 전역 최적해를 보장하지는 않는다. 초기값과 반복 조건을 바꾸어 결과를 비교하고, 더 낮은 비용을 찾지 못했다는 사실과 최적성이 증명됐다는 사실을 구분한다.