1

私は CBC の C++ API を学んでいますが、MPS ファイルをロードして CbcModel クラスを使用して解決するコンパイル済み C++ プログラムのパフォーマンスを、CBC コマンド ライン ユーティリティを開いて同じものをインポートする場合と比較して一致させるのに問題があります。ファイルと使用solve. コマンド ライン ユーティリティは 1 秒で MIP を解決し、C++ プログラムは 10 分以内に終了しません。

問題は、C++ API を使用しているときに、すべてのパラメーターを明示的に構成する必要があることです。cmd ライン ユーティリティで使用される既定のパラメーターは、平均的な MIP モデルに対してかなり適切に丸められているようです。

cmd ライン ユーティリティで使用され、パフォーマンスを一致させるために 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 モデルは、 HEREからダウンロードできます。最適な目標値: -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
4

3 に答える 3

0

公式コードのこの部分が役立つかもしれません。それはlinedocと呼ばれていますSet up likely cut generators and defaults

CBC のコードは読みにくく、時間をかけずにデフォルトの動作がどのようなものであるかを分析するのは困難です。

しかし、上記のリンクされたコードは、一部の cmd 呼び出し内でアクティブ化されたデフォルトに少し似ています。

于 2017-03-15T11:05:39.103 に答える
0

どのコンパイラを使用していますか? デバッグが有効になっています。最適化無効？たとえば、Visual Studio の場合、これはパフォーマンスに大きな違いをもたらし、コンパイルされたコードが大幅に遅くなる理由になる可能性があります。

于 2017-03-16T07:01:02.010 に答える