2차 할당 문제

2차 배정 문제(QAP)는 구피만과 벡만이 처음 도입한 설비 위치 문제의 범주에서 수학의 최적화나 운영 연구의 분과의 기본적인 결합 최적화 문제 중 하나이다.^[1]

이 문제는 다음과 같은 실제 문제를 모델링한다.

n개의 시설과 n개의 장소가 있다. 각 위치 쌍에 대해 거리를 지정하고 각 시설 쌍에 대해 중량이나 흐름을 지정한다(예: 두 시설 간에 운송되는 공급물량). 문제는 거리 합계에 해당 흐름을 곱한 값을 최소화하는 것을 목표로 모든 설비를 서로 다른 위치에 배정하는 것이다.

직관적으로 비용함수는 서로 간에 흐름이 높은 시설을 가깝게 배치하도록 유도한다.

비용함수가 2차적 불평등이라는 관점에서 표현된다는 점을 제외하면, 문제성명은 과제 문제의 그것과 유사하다.

형식수학적 정의

2차 배정 문제의 공식 정의는 다음과 같다.

무게함수 w : P × P → R, 거리함수 d : L × L → R과 함께 크기가 같은 P("시설")와 L("배치")의 두 세트가 주어진다. 비용함수가 다음과 같은 바이어스 f : P → L("배정")를 찾는다.

${\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b)}$

최소화한다.

일반적으로 중량 및 거리 함수는 제곱 실제 값 매트릭스로 간주되므로 비용 함수는 다음과 같이 기록된다.

${\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}}$

행렬 표기법:

${\displaystyle \min \Pi _{n}\operatorname {trace}(WXDX^{T})$

여기서 ${\displaystyle {\pi n}_{}}$ ${\$는 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ n$\times n}$ 순열$$ 매트릭스 집합이고$$, $W{\displaystyle }$ ${\displaystyle W}$은 중량 매트릭스, D ${\displaystystyle D}$은 거리 매트릭스 집합이다.

계산 복잡성

문제는 NP-hard이기 때문에 다항식 시간에는 이 문제를 해결하기 위한 알려진 알고리즘이 없으며, 작은 인스턴스라도 긴 계산 시간이 필요할 수 있다. 또한 P = NP가 아닌 한, 문제의 근사 알고리즘이 (정수) 인자에 대해 다항 시간 내에 실행되지 않는다는 것도 입증되었다.^[2] 이동 중인 판매원 문제는 흐름이 단일 링을 따라 모든 시설을 연결한다고 가정할 경우 QAP의 특별한 경우로 볼 수 있으며, 모든 흐름은 0이 아닌 (정수) 값이 동일하다. 표준 조합 최적화 문제의 다른 많은 문제들은 이 형식으로 쓰여질 수 있다.

적용들

QAP는 원래의 발전소 위치 제형에 덧붙여, 전자 산업에서 컴퓨터 보조 설계의 장소와 경로 단계의 일부인 인쇄 회로 보드나 마이크로칩에 상호 연결된 전자 부품의 배치 문제에 대한 수학 모델이다.

참고 항목

• 2차 병목 현상 할당 문제

참조

메모들

원천

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, 페이지.218.

외부 링크

• https://www.opt.math.tugraz.at/qaplib/ QAPLIB - 2차 할당 문제 라이브러리
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Java 기반 2차 할당 문제 해결사
• https://CRAN.R-project.org/package=qap - R 패키지 qap: 2차 할당 문제에 대한 경험적 접근