Key points are not available for this paper at this time.
초록 이 논문은 라그랑지 완화가 다목적 정수 프로그램(MOIPs)의 비지배 이미지를 위한 품질 경계를 생성할 수 있는 잠재력을 조사한다. 완화된 제약조건에 대한 몇 가지 조건 하에서, 우리는 라그랑지 완화의 집합이 볼록 껍질 완화에 의해 생성된 모든 경계와 일치하는 경계를 제공할 수 있음을 보인다. 또한 지원되지 않는 해에서 라그랑지 경계의 상대적 품질에 대한 보장을 제공한다. 이러한 결과는 완화 가능한 영역이 유한할 경우, 일부 라그랑지 경계가 일부 볼록 껍질 경계보다 엄격하게 좋을 것임을 시사한다. 우리는 희소하고 보완 여유 속성을 만족하며 지지하는 해에서 긴장을 생성하는 라그랑지 승수가 존재함을 보여준다. 그러나 모든 제약 조건이 이중화되면, 비지지 해에서 긴장은 결코 긴밀할 수 없다. 이러한 결과는 MOIP의 효율적인 해에서 라그랑지 이중의 강도를 특징짓는다.
Brun et al. (Tue,)는 이 질문을 연구했다.