혼합 정수 선형 프로그램의 전역 해결을 위한 분해 방법

. 이 논문은 두 개의 블록 혼합 정수 선형 프로그램(MILP)을 위한 두 가지 분해 기반 방법을 소개하며, 이는 원래 문제의 분리 가능한 구조를 활용하기 위해 저차원 MILP의 연속적인 해결을 목표로 합니다. 첫 번째 방법은 \ (₁\) -증강 라그랑주 방법에 기초하고, 두 번째 방법은 수정된 교차 방향 승법자 방법에 기초합니다. 특정 블록-각형 구조가 존재할 경우, 두 방법 모두 한 블록의 변수에서 병렬 하위 문제를 생성하고 다른 블록을 업데이트하기 위해 비볼록 컷을 추가합니다. 이들은 적절한 조건 하에 원래의 MILP에 대한 전역 최적 솔루션으로 수렴합니다. 세 가지 유형의 MILP에 대한 수치 실험은 제안된 방법들이 기존의 MILP 솔버에 비해 구조화된 문제에서의 이점을 보여줍니다. 키워드: 혼합 정수 선형 프로그램, 분해 방법, 증강 라그랑주 방법, 교차 방향 승법자 방법, MSC 코드 49M2790, C1190, C26