정수 SDP에 대한 Chvátal–Gomory 절차와 조합 최적화의 응용

초록 본 논문에서는 정수 반정수 프로그램(ISDP) 클래스에 대해 잘 알려진 Chvátal–Gomory(CG) 절차를 연구합니다. 우리는 이 절차를 반복하여 얻은 완화의 계층 구조에 관한 여러 결과를 증명합니다. 또한 스펙트라헤드라의 기본 폐쇄에 대한 다양한 공식화를 연구합니다. 특정 유형의 스펙트라헤드라에 대한 기본 폐쇄의 다면체 설명은 SDP에 대한 전체 이중 완전성을 이용하여 유도됩니다. 더불어, ISDP를 위한 분기 및 절단 프레임워크에서 (강화된) CG 컷을 어떻게 활용할 수 있는지 보여줍니다. 기존 문헌의 알고리즘과는 다르게, 우리 접근법의 분리 루틴은 반정수 제약 조건과 반정수 제약 조건 둘 다를 활용합니다. 우리는 조합 최적화 문제로부터 발생한 여러 일반적인 이진 SDP 클래스에 대한 분리 루틴을 제공합니다. 논문의 두 번째 부분에서는 이 접근법을 이차적 외판원 문제(QTSP)에 포괄적으로 적용한 사례를 제시합니다. 지향된 해밀토니안 사이클의 대수적 연결성을 기반으로, QTSP를 모델링하는 두 개의 ISDP를 소개합니다. 우리는 이러한 공식화로부터 나온 CG 컷이 여러 잘 알려진 절단 평면 가족을 포함하고 있음을 보여줍니다. 수치 결과는 대안 ISDP 솔버보다 성능이 우수하고 큰 QTSP 인스턴스를 최적화할 수 있는 우리의 분기 및 절단 알고리즘에서 CG 컷의 실제 강도를 보여줍니다.