Производительность решателя Coin-or-CBC: утилита командной строки и скомпилированная программа на C++
Я изучаю C++ API CBC, и у меня возникают проблемы с сопоставлением производительности скомпилированной программы C++, которая загружает файл MPS и решает его с помощью класса CbcModel по сравнению с простым открытием утилиты командной строки CBC и импортом того же самого файл и использование solve, Утилита cmd line решает MIP за 1 секунду, а программа на C++ не завершает работу в течение <10 минут.
Я понял, что проблема в том, что когда я использую C++ API, мне нужно явно настроить все параметры, и кажется, что параметры по умолчанию, используемые утилитой cmd line, довольно хорошо округлены для вашей средней модели MIP.
Есть ли список параметров по умолчанию для предварительного разрешения, эвристики и срезов, которые используются утилитой cmd line и которые мне следует активировать в моей программе на C++, чтобы соответствовать производительности. Возможно, кто-то поиграл с этими параметрами и нашел хороший набор параметров эмпирически.
Программа на C++:
int main ()
{
OsiClpSolverInterface solver1;
solver1.setLogLevel(0);
// Read in example model in MPS file format
// and assert that it is a clean model
int numMpsReadErrors = solver1.readMps("generic_mip.mps","");
assert(numMpsReadErrors==0);
// Pass the solver with the problem to be solved to CbcModel
CbcModel model(solver1);
model.setLogLevel(0);
// Add clique cut generator
CglClique clique_generator;
model.addCutGenerator(&clique_generator,-1, "Clique");
// Add rounding heuristic
CglMixedIntegerRounding mixedGen;
model.addCutGenerator(&mixedGen, -1, "Rounding");
model.setNumberThreads(4);
model.messageHandler()->setPrefix(false);
model.branchAndBound();
const double * solution = model.bestSolution();
printf("Optimal value is %.2f", *solution);
return 0;
}
Рассматриваемая модель MIP может быть загружена ЗДЕСЬ. Оптимальное объективное значение: -771,2957.
Журнал утилиты командной строки Cbc, в котором указываются все виды расширенных функций (предварительная обработка, первичная эвристика и сильное ветвление):
Continuous objective value is -798.689 - 0.03 seconds
Cgl0002I 21 variables fixed
Cgl0003I 0 fixed, 175 tightened bounds, 1972 strengthened rows, 0 substitutions
Cgl0004I processed model has 3731 rows, 3835 columns (3835 integer (3660 of which binary)) and 37873 elements
Cbc0038I Initial state - 365 integers unsatisfied sum - 129.125
Cbc0038I Pass 1: (0.18 seconds) suminf. 58.66667 (121) obj. -572.133 iterations 510
Cbc0038I Pass 2: (0.18 seconds) suminf. 58.66667 (121) obj. -572.133 iterations 23
Cbc0038I Pass 3: (0.18 seconds) suminf. 58.66667 (121) obj. -572.133 iterations 1
Cbc0038I Pass 4: (0.20 seconds) suminf. 69.00000 (138) obj. -299.496 iterations 589
Cbc0038I Pass 5: (0.20 seconds) suminf. 54.00000 (109) obj. -287.063 iterations 194
Cbc0038I Pass 6: (0.21 seconds) suminf. 54.00000 (109) obj. -287.063 iterations 12
Cbc0038I Pass 7: (0.21 seconds) suminf. 49.00000 (100) obj. -273.321 iterations 33
Cbc0038I Pass 8: (0.22 seconds) suminf. 48.00000 (97) obj. -269.421 iterations 14
Cbc0038I Pass 9: (0.22 seconds) suminf. 48.00000 (98) obj. -268.624 iterations 8
Cbc0038I Pass 10: (0.23 seconds) suminf. 48.00000 (97) obj. -264.813 iterations 4
Cbc0038I Pass 11: (0.23 seconds) suminf. 47.00000 (94) obj. -261.75 iterations 8
Cbc0038I Pass 12: (0.24 seconds) suminf. 47.00000 (94) obj. -261.75 iterations 3
Cbc0038I Pass 13: (0.24 seconds) suminf. 47.00000 (94) obj. -261.75 iterations 3
Cbc0038I Pass 14: (0.25 seconds) suminf. 57.75000 (118) obj. -103.115 iterations 508
Cbc0038I Pass 15: (0.26 seconds) suminf. 49.00000 (98) obj. -97.4793 iterations 163
Cbc0038I Pass 16: (0.26 seconds) suminf. 49.00000 (98) obj. -97.4793 iterations 3
Cbc0038I Pass 17: (0.27 seconds) suminf. 48.75000 (98) obj. -101.421 iterations 24
Cbc0038I Pass 18: (0.27 seconds) suminf. 47.00000 (94) obj. -103.346 iterations 25
Cbc0038I Pass 19: (0.28 seconds) suminf. 47.00000 (94) obj. -103.346 iterations 2
Cbc0038I Pass 20: (0.28 seconds) suminf. 47.00000 (94) obj. -103.346 iterations 21
Cbc0038I Pass 21: (0.29 seconds) suminf. 51.50000 (107) obj. 60.0315 iterations 469
Cbc0038I Pass 22: (0.30 seconds) suminf. 40.00000 (80) obj. 59.913 iterations 168
Cbc0038I Pass 23: (0.30 seconds) suminf. 40.00000 (80) obj. 59.913 iterations 2
Cbc0038I Pass 24: (0.31 seconds) suminf. 39.50000 (79) obj. 59.913 iterations 27
Cbc0038I Pass 25: (0.31 seconds) suminf. 39.00000 (78) obj. 59.913 iterations 23
Cbc0038I Pass 26: (0.32 seconds) suminf. 39.00000 (78) obj. 59.913 iterations 13
Cbc0038I Pass 27: (0.33 seconds) suminf. 50.00000 (101) obj. 124.699 iterations 504
Cbc0038I Pass 28: (0.34 seconds) suminf. 41.00000 (82) obj. 118.624 iterations 174
Cbc0038I Pass 29: (0.34 seconds) suminf. 41.00000 (82) obj. 118.624 iterations 5
Cbc0038I Pass 30: (0.34 seconds) suminf. 41.00000 (82) obj. 118.624 iterations 19
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 2356 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.41 seconds)
Cbc0038I After 0.41 seconds - Feasibility pump exiting - took 0.25 seconds
Cbc0031I 583 added rows had average density of 8.2024014
Cbc0013I At root node, 583 cuts changed objective from -798.68913 to -771.29565 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 541 row cuts average 2.0 elements, 0 column cuts (0 active) in 0.044 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 751 row cuts average 116.6 elements, 0 column cuts (0 active) in 0.108 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 451 row cuts average 2.0 elements, 0 column cuts (0 active) in 0.040 seconds - new frequency is 1
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 155 row cuts average 16.9 elements, 0 column cuts (0 active) in 0.028 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.008 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 1171 row cuts average 20.0 elements, 0 column cuts (0 active) in 0.068 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible -771.29565 (1.18 seconds)
Cbc0004I Integer solution of -771.29565 found after 2671 iterations and 1 nodes (1.24 seconds)
Cbc0001I Search completed - best objective -771.2956521739131, took 2671 iterations and 1 nodes (1.24 seconds)
Cbc0032I Strong branching done 22 times (542 iterations), fathomed 0 nodes and fixed 0 variables
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -798.689 to -771.296
Probing was tried 12 times and created 552 cuts of which 0 were active after adding rounds of cuts (0.044 seconds)
Gomory was tried 12 times and created 756 cuts of which 0 were active after adding rounds of cuts (0.116 seconds)
Knapsack was tried 12 times and created 456 cuts of which 0 were active after adding rounds of cuts (0.044 seconds)
Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.004 seconds)
MixedIntegerRounding2 was tried 12 times and created 155 cuts of which 0 were active after adding rounds of cuts (0.036 seconds)
FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.008 seconds)
TwoMirCuts was tried 12 times and created 1197 cuts of which 0 were active after adding rounds of cuts (0.084 seconds)
ImplicationCuts was tried 2 times and created 11 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: -771.29565217
Enumerated nodes: 1
Total iterations: 2671
Time (CPU seconds): 1.27
Time (Wallclock seconds): 1.30
2 ответа
Я смог использовать те же настройки, что и в утилите командной строки, вызвав решатель с помощью следующего кода:
const char *argv[] = {"", "-solve"};
CbcMain1(2, argv, model);
Конечно, вы можете сначала установить уровень журнала, количество потоков и т. Д. Таким образом, вам не нужно копировать код из CbcSolver.cppЧто можно сделать из ответа Саши.
Может быть, эта часть официального кода помогает. Это линедок называется Set up likely cut generators and defaults
Код Си-би-си трудно читать, и трудно проанализировать, какое поведение по умолчанию существует, не тратя некоторое время.
Но приведенный выше код выглядит немного как настройки по умолчанию, активированные в некоторых вызовах cmd.
Какой компилятор вы используете? Отладка включена или соотв. оптимизация отключена? Например, для Visual Studio это имеет огромное значение для производительности и может быть причиной того, что ваш скомпилированный код работает намного медленнее.