연결된 최대-k-컷 문제에 대한 혼합 정수 프로그래밍 기법

초록 우리는 그래프 분할의 부분들이 연결되어야 하는 조건을 추가한 고전적인 최대-k-컷 문제의 확장된 버전을 고려한다. 이 문제에 대해 우리는 두 가지 대체 혼합 정수 선형 공식을 연구하고, 기존 기법을 검토하며 새로운 가지치기 기법인 컷, 분기 규칙, 전파, 본질적인 휴리스틱 및 대칭 깨기를 개발한다. 이 논문의 주요 초점은 다양한 테스트 세트에 대한 다른 기법의 영향을 분석하는 광범위한 수치 연구이다. 기존 문헌의 기법만으로는 적절한 비율의 테스트 세트를 해결하는 데 충분하지 않다는 것이 밝혀졌다. 그러나 우리의 새로운 기법은 실행 시간과 해결 가능한 전체 인스턴스 수 측면 모두에서 기존 기법을 크게 능가한다.