어떤 경우에 이진 선형 프로그램을 쉽게 해결하는 것 (즉, ** P ** 복잡성)을 쉽게 해결할 수 있습니까?나는 특히 예약 문제를 찾고 있습니다

Question

이진 선형 프로그램을 쉽게 해결하는 경우 (즉, p 복잡성)

내가 묻는 이유는 내가 현재 합리적인 시간 내에 글로벌 최적을 찾는 것을 보장하는 방법으로 현재 일하고있는 일정 문제를 해결할 수있는 일을 이해하는 것입니다. 그래서 그 방향의 조언은 가장 환영합니다. < / P>

나는 일정 문제를 해결할 때, 1의 변수 값이 특정 (타임 슬롯 x 인칭) 쌍이 일정의 일부인 경우, 결과에 비 정수가 포함되어 있으면 존재 함을 의미한다는 것을 의미한다. 여러 유효한 일정이며 결과는 이러한 스케줄의 선형 조합입니다. 유효한 정수 솔루션을 얻으려면 실제 값 변수 중 하나와 동일한 0 또는 1과 같은 추가 제약 조건으로 현재 솔루션에서 알고리즘을 다시 실행해야합니다.

나는이 이해에 착각하고 있습니까? 유효한 전략이 될 수있는 특별한 (스케줄링) 문제의 하위 집합이 있습니까? 모든 논문 / 교과서 장 제안도 가장 환영합니다.

Answer 1

분수 솔루션이 반드시 필수 솔루션으로 바뀔 수 있다는 것은 사실이 아닙니다.예를 들어, 1은 슬롯 A와 B 또는 슬롯 D 및 E를 필요로한다고 가정합니다.2는 슬롯 B 및 C 또는 슬롯 E 및 F;3은 슬롯 A와 C 또는 슬롯 D와 F를 필요로합니다. 확인하기 쉽습니다 (A, B, C는 함께 대부분을 수용 할 수 있으며, D, E, F를 함께 수용 할 수 있습니다)하나).그러나 모든 사람들이 그들을 수용 할 수있는 모든 슬롯 중 1/2를 모두주는 소수의 솔루션이 있습니다.

최적의 필수 솔루션이 있음을 보장하는 총 유선과 같은 조건이 있습니다.이 경우 문제는 p 다항식에서 수행 할 수있는 LP 이완을 해결하는 것입니다.