조합 최적화

조합 최적화는 유한한 ^[1]객체 집합에서 최적의 객체를 찾는 것으로 구성되는 수학적 최적화의 하위 필드이며, 여기서 실현 가능한 솔루션 집합은 이산적이거나 이산 집합으로 축소될 수 있습니다.일반적인 조합 최적화 문제로는 출장 세일즈맨 문제("TSP", 최소 스패닝 트리 문제("MST") 및 배낭 문제가 있습니다.앞서 언급한 것과 같은 많은 문제에서 완전한 검색은 다루기 어렵기 때문에 검색 공간의 많은 부분을 신속하게 배제하는 전문화된 알고리즘이나 근사 알고리즘을 대신 사용해야 합니다.

조합 최적화는 연산 연구, 알고리즘 이론 및 계산 복잡성 이론과 관련이 있습니다.그것은 인공지능, 기계학습, 경매 이론, 소프트웨어 공학, 응용 수학, 이론 컴퓨터 과학을 포함한 여러 분야에서 중요한 응용 분야를 가지고 있다.

일부 연구 문헌은^[2] 이산 최적화를 조합 최적화와 함께 정수 프로그래밍(그래프 구조를 다루는 최적화 문제로 구성됨)으로 구성된다고 간주하지만, 이러한 모든 주제는 밀접하게 얽혀 있다.이는 종종 수학적 ^{[clarification needed]}문제에 대한 해결책을 찾는 데 사용되는 자원을 효율적으로 할당하는 방법을 결정하는 것과 관련이 있습니다.

적용들

조합 최적화의 응용 프로그램에는 다음이 포함되지만 이에 한정되지 않습니다.

• 실행 계획^[3]
• 공급망 최적화^[4]
• 스포크 및 목적지 최고의 항공사 네트워크 구축
• 운임을 픽업하기 위해 비행대에서 어떤 택시를 이용할지 결정하다
• 최적의 패키지 전송 방법 결정
• 최적의 작업 할당
• 배수망 설계
• 지구 과학 문제(예: 저장유량)^[5]

방법들

이산 최적화의 특정 특수 클래스를 위한 다항 시간 알고리즘에 대한 많은 문헌이 있다.그 중 상당수는 선형 프로그래밍 이론에 의해 통합된다.이 프레임워크에서 다루는 조합 최적화 문제의 예로는 최단 경로 및 최단 경로 트리, 흐름 및 순환, 스패닝 트리, 일치 및 매트로이드 문제 등이 있습니다.

NP-완전 이산 최적화 문제의 경우, 현재 연구 문헌에는 다음과 같은 주제가 포함되어 있습니다.

• 다항식 시간 정확히 해결 가능한 당면 문제의 특수한 경우(예: 고정 매개 변수 추적 가능한 문제)
• "실행" 인스턴스에서 잘 작동하는 알고리즘(예: 출장 세일즈맨 문제)
• 다항 시간에 실행되어 최적에 가까운 해법을 찾는 근사 알고리즘
• 실제로 발생하고 NP-완전 문제(예를 들어 수만 개의 노드가^[6] 있는 실제 TSP 인스턴스)에서 최악의 경우 동작을 보일 필요는 없는 실제 인스턴스를 해결합니다.

조합 최적화 문제는 일부 이산 항목 집합의 최상의 요소를 찾는 것으로 볼 수 있습니다. 따라서 원칙적으로, 그것들을 해결하기 위해 어떤 종류의 검색 알고리즘이나 메타 휴리스틱을 사용할 수 있습니다.아마도 가장 보편적으로 applicable[애매 모호한 말.]접근법이 있branch-and-bound(어떤 시점에서 휴리스틱으로 작용하고 중단될 수 있는 정확한 알고리즘),branch-and-cut(범위를 발생시키기 위해 선형 최적화를 사용한다), 동적 프로그래밍(제한된 검색 창을 가진 귀납적인 해결책 건설)과tabu 검색 화면greedy-type sw.algori apping그러나 일반 검색 알고리즘이 먼저 최적의 솔루션을 찾는다는 보장도 없고, 빠른 실행(다항식 시간)도 보장되지 않습니다.일부 이산 최적화 문제는 이동 판매원(^[7]판매원) 문제와 같이 NP-완전이기 때문에, P=NP가 아닌 한 예상할 수 있습니다.

형식적 정의

형식적으로 조합 최적화 $문제{\displaystyle }$A({$displaystyle$A})는$$ 4배^{[citation needed]}$($이다.

• $\displaystyle$I은$$ 일련의 인스턴스입니다.
• $인스턴스{\displaystyle }$ x${\displaystyle i}$I { $displaystyle$x \ $in$I$$},${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$) { $displaystyle$ f$(x)}$는 실현 가능한 솔루션의 유한 세트이다.
• $인스턴스{\displaystyle }$x(\$displaystyle$$$x) 및$$ 실행 가능한 $솔루션{\displaystyle }$y$(\displaystyle$$$y$)$가 지정되면 m${\displaystyle (x,}$ $)$은 y$$$(\displaystyle$m$(x,y$$)$의 측도를 나타내며, 이는 보통 양의 실수입니다.
• $\displaystyle$g는 목표 함수이며$$ min$\displaystyle\min$${\displaystyle 또는<img\; alt="\backslash min\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/695d28931288a686335c3969dfd15bb76ea873db"\; style="vertical-align:\; -0.338ex;\; width:3.875ex;\; height:2.176ex;">}$ max$\backslash$$displaystyle\max$ 중 ${\displaystyle 하나}$입니다.

$다음$으로 최적의 솔루션$,$ 즉 $실행$ 가능한 $y를$$특정$하는 것이 목표입니다$.$

${\displaystyle m(x,y)=g\{m(x,y')\mid y'\in f(x)\}$

각 조합 최적화 문제에 대해 특정 $측정값{\displaystyle {}_{}}$ ${\displaystyle {m\mathrm{}}_{}}$ 0$({$에 대해 실행 가능한 솔루션이 있는지 묻는 해당 결정 문제가 있습니다. 예를 들어 $u$와 $v{displaystyle$ v$\}$를 포함하는 $그래프{\displaystyle }$G({$displaystyle$G})가$$ 있는 경우,최적화 문제는 "가장 적은 에지를 사용하는 사용자$(\displaystyle$u)에서 v$(\displaystyle$ v$)$로의 경로 찾기"일 수 있습니다.이 문제의 답은 예를 들어 4일 수 있습니다.해당하는 결정 문제는 "10개 이하의 엣지를 사용하는 u$\$$displaystyle$ $v$$\displaystyle$에서 $v{\displaystyle }$$\$displaystyle v로의$$$$ $경로$가 있습니까?"입니다.이 문제는 간단히 '예' 또는 '아니오'로 대답할 수 있습니다.

근사 알고리즘 분야는 어려운 문제에 대한 거의 최적의 해결책을 찾기 위한 알고리즘을 다룬다.일반적인 의사결정 버전은 허용 가능한 해결책만 지정하기 때문에 문제의 정의가 불충분합니다.적절한 의사결정 문제를 도입할 수 있지만, 그 문제는 보다 자연스럽게 최적화 ^[8]문제로 특징지어집니다.

NP 최적화 문제

이 섹션은 독자들에게 혼란스럽거나 불분명할 수 있습니다.특히, 이 섹션에서 소개하는 표기법은 잘 설명되지 않고 표준적이지 않을 수 있습니다. 섹션을 명확하게 하는 데 도움을 주세요. 토크 페이지에 이 건에 대한 논의가 있을 수 있습니다.( 2021년 12월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

NP 최적화 문제(NPO)는 다음과 같은 추가 ^[9]조건을 수반하는 조합 최적화 문제입니다.아래 참조된 다항식은 각 함수의 입력 크기 함수이며, 암묵적인 입력 인스턴스 집합의 크기가 아닙니다.

• 모든 실현 가능한 $솔루션$의 크기 ${\displaystyle \mathrm{y\theta }}$f${\displaystyle }$(${\displaystyle x}$ ) ${\displaystyle y\in$ f$(x)}$는 주어진 $인스턴스{\displaystyle }$x {\$displaystyle$x$\}$의 크기로 다항식적으로 한정됩니다.
• ${\displaystyle 언어}{\displaystyle }${ x${\displaystyle x}$ x${\displaystyle }$$i$ I $}$${\displaystyle }${ $displaystyle$\ {${\displaystyle }$,$x$ , x , \ mid \ , x \ $in$ $I$ ,$$\ }${\displaystyle 및}$ {${\displaystyle }$( x , ${\displaystyle y}$ )$}$ f ( $x$ ) ${\displaystyle \}}$ { \ displaystyle \ , ( x ,$y$ ) 、 \$mid$ \ , y$f$( x ) }는 다항식 시간으로 인식됩니다.
• $\displaystyle$m은$$ 다항식 시간 계산 가능합니다.

이는 대응하는 결정 문제가 NP에 있음을 의미합니다.컴퓨터 과학에서, 흥미로운 최적화 문제는 보통 위의 속성을 가지고 있기 때문에 NPO 문제입니다.다항식 시간에 최적의 솔루션을 찾는 알고리즘이 있는 경우 문제를 추가로 P 최적화(PO) 문제라고 합니다.클래스 NPO를 다룰 때 의사결정 버전이 NP-완전인 최적화 문제에 관심을 갖는 경우가 많습니다.경도 관계는 항상 일부 감소와 관련이 있습니다.근사 알고리즘과 계산 최적화 문제 사이의 연관성 때문에, 어떤 면에서 근사치를 보존하는 감소는 일반적인 튜링과 카르프 감소보다 이 주제에 선호된다.그러한 감소의 예로는 L-축소가 있다.따라서 NP-complete ^[10]결정 버전의 최적화 문제를 반드시 NPO-complete라고 부르지는 않습니다.

NPO는 ^[9]근사성에 따라 다음과 같은 하위 클래스로 나뉩니다.

• NPO(I): FPTAS와 동일합니다.배낭 문제가 포함되어 있습니다.
• NPO(II): PTAS와 동일합니다.Makespan 스케줄링 문제가 있습니다.
• NPO(II):최적 비용(최소화 문제)의 최대 c배 또는 최적 비용($최대화$ 문제)의 $최소{\displaystyle \mathrm{}}$1/$(\displaystyle$1/$c)$의 비용으로 솔루션을 계산하는 다항식 시간 알고리즘을 사용하는 NPO 문제의 클래스.Hromkovicc의 책에서는^[which?] P=NP일 경우 이 분류에서 제외되는 모든 NPO(II) 문제는 제외된다.제외하지 않으면 APX와 동일합니다.MAX-SAT 및 메트릭 TSP가 포함됩니다.
• NPO(IV):NPO 클래스는 다항식 시간 알고리즘이 입력 크기의 로그에서 다항식 비율로 최적 솔루션을 근사하는 데 문제가 있습니다.Hromkovicc의 책에서는 P=NP가 아닌 한 모든 NPO(II) 문제는 이 클래스에서 제외된다. 세트 커버 문제가 포함되어 있다.
• NPO(V):NPO의 클래스는 n의 일부 함수에 의해 제한되는 비율에 의해 최적 솔루션에 근사하는 다항식 시간 알고리즘에서 문제를 일으킵니다.Hromkovic의 책에서는 P=NP가 아닌 한 모든 NPO(IV) 문제는 이 클래스에서 제외된다. TSP 및 파벌 문제가 포함되어 있다.

NPO 문제는 모든 $인스턴스{\displaystyle }$x {\$displaystyle$ x$}$ 및$$ 모든 $솔루션{\displaystyle }$ y$f$ f$($$x)$에 대해 $측정값{\displaystyle }$ m$($ $)$ {$displaystyle$m(x,y$)}$이 x${displaystyle$x$\}$ $크기$의 다항 함수에 의해 제한될 경우 다항식 경계(PB)라고 불립니다.NPOPB 클래스는 다항식으로 바인딩된 NPO 문제의 클래스입니다.

특정 문제

• 할당 문제
• 폐쇄 문제
• 제약 만족 문제
• 절삭재고문제
• 지배적인 집합 문제
• 정수 프로그래밍
• 배낭 문제
• 선형 시스템의 최소 관련 변수
• 최소 스패닝 트리
• 간호사 일정 설정 문제
• 커버 설정 문제
• Job shop 스케줄 설정
• 출장 세일즈맨 문제
• 차량 일정 변경 문제
• 차량 배선 문제
• 무기 목표 할당 문제
• 휴지통 패킹 문제

「 」를 참조해 주세요.

• 제약 조건 합성 그래프

메모들

레퍼런스

• Beasley, J. E. "Integer programming" (lecture notes).

• Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (1997). Combinatorial Optimization. Wiley. ISBN 0-471-55894-X.

• Cook, William (2016). "Optimal TSP Tours". University of Waterloo. (현재까지 해결된 가장 큰 TSP 인스턴스에 대한 정보).

• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (eds.). "A Compendium of NP Optimization Problems". (이것은 NP 최적화 문제에 대한 근사성 결과의 연속적으로 갱신된 카탈로그입니다).

• Das, Arnab; Chakrabarti, Bikas K, eds. (2005). Quantum Annealing and Related Optimization Methods. Lecture Notes in Physics. Vol. 679. Springer. Bibcode:2005qnro.book.....D.

• Das, Arnab; Chakrabarti, Bikas K (2008). "Colloquium: Quantum annealing and analog quantum computation". Rev. Mod. Phys. 80 (3): 1061. arXiv:0801.2193. Bibcode:2008RvMP...80.1061D. CiteSeerX 10.1.1.563.9990. doi:10.1103/RevModPhys.80.1061. S2CID 14255125.

• Lawler, Eugene (2001). Combinatorial Optimization: Networks and Matroids. Dover. ISBN 0-486-41453-1.

• Lee, Jon (2004). A First Course in Combinatorial Optimization. Cambridge University Press. ISBN 0-521-01012-8.

• Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). Combinatorial Optimization : Algorithms and Complexity. Dover. ISBN 0-486-40258-4.

• Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. ISBN 9783540443896.

• Schrijver, Alexander (2005). "On the history of combinatorial optimization (till 1960)" (PDF). In Aardal, K.; Nemhauser, G.L.; Weismantel, R. (eds.). Handbook of Discrete Optimization. Elsevier. pp. 1–68.

• Schrijver, Alexander (February 1, 2006). A Course in Combinatorial Optimization (PDF).

• Sierksma, Gerard; Ghosh, Diptesh (2010). Networks in Action; Text and Computer Exercises in Network Optimization. Springer. ISBN 978-1-4419-5512-8.

• Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice. CRC Press. ISBN 978-1-498-71016-9.

• Pintea, C-M. (2014). Advances in Bio-inspired Computing for Combinatorial Optimization Problem. Intelligent Systems Reference Library. Springer. ISBN 978-3-642-40178-7.

외부 링크

• 조합 최적화 저널
• Ausois 조합 최적화 워크숍
• Java Combinatorial Optimization Platform(오픈 소스 코드)
• 왜 사람들 스케줄 잡는 게 어렵죠?
• 최적화 문제에 대한 복잡도 클래스 / Stefan Kugle