이산 최적 제어에서 총 변동 정규화에 관한 이차원 하위 문제

우리는 총 변동 정규화가 적용된 혼합 정수 최적 제어 문제에 대한 신뢰 구간 알고리즘에서 발생하는 이차원 하위 문제를 이산화한 후 얻은 정수 선형 프로그램을 분석합니다. 우리는 이산화된 문제의 NP-어려움과 그래프 기반 문제와의 연관성에 대해 논의합니다. 우리는 기저 다면체가 동시에 분수 값을 취할 수 있는 변수에 대해 정점의 구조적 제약을 나타낸다는 것을 보여줍니다. 이 속성을 기반으로 우리는 최단 경로 및 최소 이분 문제와의 관계를 활용하여 절단 평면을 도출합니다. 우리는 이전에 발견된 실현 가능한 점을 개선하는 분기 규칙과 원시 휴리스틱을 제안합니다. 우리는 표준 정수 선형 프로그래밍 솔버에서 수치 벤치마크를 통해 제안된 도구를 검증합니다. 우리는 중간 크기의 문제에 대한 상당한 속도 향상을 관찰합니다. 우리의 결과는 미래에 더 큰 사례로 확장하기 위한 힌트를 제공합니다.