선형 프로그램에서 장벽 해소 후 크로스 오버를 피할 때의 단점

Question

큰 LP (약 5M이 아닌 숫자)를 실행 중입니다. 해결 프로세스의 속도를 높이고 싶습니다. 나는 어느 알고리즘이 내 문제를 가장 빨리 해결하는지 테스트하기 위해 동시 해결을 시도했으며 장벽 방법이 확실한 승자 (solver = Xpress MP이지만 다른 솔버와 동일하다고 생각한다)라는 것을 알았습니다.

그러나 속도를 더욱 높이고 싶습니다. 실제 장벽 해결은 전체 솔루션 시간의 1 % 미만을 차지한다는 것을 알았습니다. 나머지 시간은 크로스 오버 (~ 40 %)와 원초적 해결 (새로운 기준의 코너 솔루션을 찾기 위해) (~ 60 %)에 소비됩니다. 불행히도 듀얼 크로스 오버를 할 수있는 설정을 찾을 수 없었습니다 (Cplex에는 하나 있지만 Cplex에는 라이센스가 없습니다). 따라서 나는 이것이 더 빠를지를 비교할 수 없었다.

따라서 나는 커다란 속도 증가를 가져 오는 크로스 오버를 끄려고했지만, 문서에 따르면 몇 가지 단점이 있습니다. 지금까지 내가 아는 단점은 다음과 같습니다.

• 배리어 솔루션은 중층 솔루션 인 경향이 있습니다.
• 크로스 오버가없는 배리어는 기본 솔루션을 생성하지 않습니다 ("크로스 오버가 사용되는지 여부에 관계없이 풀 프라이 머리 및 이중 솔루션을 사용할 수 있습니다.").
  • 기초가 없으면 고급 시작 정보를 사용하여 동일하거나 유사한 문제를 반복적으로 최적화 할 수 없습니다.
  • 기초가 없으면 민감도 분석을 수행하기위한 범위 정보를 얻을 수 없습니다.

내 질문 (들) (입니다) 간단. 매우 비효율적 인 크로스 오버 단계를 정당화하는 데있어 다른 단점이 중요합니다 (Cplex 및 Xpress MP 모두 크로스 오버를 기본 설정으로 사용할 수 있음). 양자 택일로, 내 문제는 예외이며 다른 문제에서 크로스 오버 단계가 매우 빠릅니까? 마지막으로, 미드 페이스 솔루션을 사용하는 것이 잘못된 것입니다 (즉, 모서리 최적 또한 고유하지 않음을 의미).

출처 :

이

• http://www.cs.cornell.edu/w8/iisi/ilog/cplex101/usrcplex/solveBarrier2.html (배리어 알고리즘 높은 수준의 이론)
• http://tomopt.com/docs/xpress/tomlab_xpress008.php (익스프레스 MP 해결사 설정)
이

이

Answer 1

단점 :, 그 해결책은 "추악한"될 것입니다 솔루션 값에 0.000001 및 0.9999999가 많이 있습니다. 둘째로 당신은 다소 다른 이중성을 가질 수 있습니다. 마지막으로 빠른 "핫 스타트 (hot starts)"를 수행하기위한 기반이 필요합니다. 대형 모델의 속도를 높일 수있는 한 가지 방법은 단순한 방법을 사용하고 대표적인 기본 실행에서 고급 기반을 사용하는 것입니다.