왜 CPlex는이 혼합 정수 선형 프로그램을 매우 빠르게 해석합니까?

Question

기술 요구 사항 (모든 리소스가 요구 사항에 대해 모든 기술을 가지고있는 것은 아님), 리소스 제한 (리소스가 제한된 상태 임) 및 할당 제한에 따라 리소스 - 활동 할당을 찾고 싶은 최적화 문제에 착수하고 있습니다. l 활동에 할당 된 자원의 수를 제한합니다. 내가 선택한 모든 활동의 무게 w를 최대화하고 싶습니다.

가 지금은 CPLEX로이 공급 그것은 한 내가 추론 (1,000 활동, 50 개 자원에 대한 내 5 개 기술을 허용하는 매우 짧은 시간에 거대한 인스턴스를 해결 : 모델은 여기에 묘사되어있다 10 초). 엄청난 수의 선택된 쟁점이 있고 각 활동에 대한 많은 수의 가능한 과제가 있지만.

CPlex에서이 문제가 너무 쉬운 이유는 무엇입니까? 내가 풀지 않고 쉽게 해결할 수있는 근본적인 문제가 있습니까?

편집 : 내 해결사 실행 중 하나의 전형적인 출력 :

Tried aggregator 1 time. 
MIP Presolve eliminated 3051 rows and 64954 columns. 
MIP Presolve modified 49950 coefficients. 
Reduced MIP has 52001 rows, 236046 columns, and 662190 nonzeros. 
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators. 
Presolve time = 0.61 sec. (276.60 ticks) 
Probing time = 0.38 sec. (12.12 ticks) 
Tried aggregator 1 time. 
MIP Presolve eliminated 1323 rows and 62181 columns. 
MIP Presolve modified 3366 coefficients. 
Reduced MIP has 50678 rows, 173865 columns, and 474324 nonzeros. 
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators. 
Presolve time = 0.78 sec. (334.49 ticks) 
Probing time = 0.26 sec. (9.19 ticks) 
Tried aggregator 1 time. 
Reduced MIP has 50678 rows, 173865 columns, and 474324 nonzeros. 
Reduced MIP has 47952 binaries, 0 generals, 0 SOSs, and 0 indicators. 
Presolve time = 0.49 sec. (220.07 ticks) 
Probing time = 0.36 sec. (10.46 ticks) 
MIP emphasis: balance optimality and feasibility. 
MIP search method: dynamic search. 
Parallel mode: deterministic, using up to 8 threads. 
Root relaxation solution time = 2.86 sec. (1101.00 ticks) 
    Nodes           Cuts/ 


Node Left  Objective IInf Best Integer Best Bound ItCnt  Gap 

*  0+ 0       7.0000  5631.0000  3104  --- 
     0  0  2265.4000  2  7.0000  2265.4000  3104  --- 
*  0+ 0       2265.0000  2265.4000  3107 0.02% 
*  0  0  integral  0  2265.0000  2265.4000  3107 0.02% 
Elapsed time = 7.59 sec. (2779.25 ticks, tree = 0.00 MB, solutions = 2) 

Cover cuts applied: 1 

Root node processing (before b&c): 
    Real time    = 7.61 sec. (2792.47 ticks) 
Parallel b&c, 8 threads: 
    Real time    = 0.00 sec. (0.00 ticks) 
    Sync time (average) = 0.00 sec. 
    Wait time (average) = 0.00 sec. 
          ------------ 
Total (root+branch&cut) = 7.61 sec. (2792.47 ticks) 

Answer 1

나는 모델의 형태는 목적 함수로, 비교적 간단하고 모델 규모가 작은 편이기 때문에 그 생각합니다. 보다 복잡한 예제를 사용하여 CPLEX를 테스트 할 수 있습니다. 저는 800,000 개 이상의 제약과 30 만 개의 변수를 가진 MIP 모델을 풀어 왔습니다.