🤖

SCIPのソースコードを読んでみる

Kohji Nishimura

2025/12/17に公開

数理最適化

scip

tech

この記事は数理最適化 Advent Calendar 2025、およびJij Advent Calendar 2025の17日目の記事のクロスポストです。

はじめに

数理最適化のプロセスにおいて、問題を定式化した後にまずは数理最適化のためのソルバーを利用して解を求めることが一般的である。しかし、そのソルバーの中で実際に何が起こっているのかに関しては、しばしばブラックボックスとして扱われがちである。

例えば、以下はフリーで使えるソルバーの中で有名なものの一つであるSCIP (Solving Constraint Integer Programs)のログの一部であるが、多くの場合はこのログにおいてgapがどのように推移していくのか (最適解にどれぐらい)ぐらいしか気に留めないことが多いかもしれない。

original problem has 10 variables (0 bin, 10 int, 0 cont) and 6 constraints

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 6 upgd conss, 0 impls, 0 clqs, 0 implints
   (0.0s) probing cycle finished: starting next cycle
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present (symcode time: 0.00)
presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques, 0 implied integral variables (0 bin, 0 int, 0 cont)
presolved problem has 10 variables (10 bin, 0 int, 0 cont) and 6 constraints
      6 constraints of type <knapsack>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     0 |     - |   locks|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 6.000000e+00 | 816.67%| unknown
i 0.0s|     1 |     0 |     0 |     - |  oneopt|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 1.600000e+01 | 243.75%| unknown
  0.0s|     1 |     0 |     5 |     - |  1397k |   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 1.600000e+01 |  71.09%| unknown
r 0.0s|     1 |     0 |     5 |     - |simplero|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.100000e+01 |  30.36%| unknown
r 0.0s|     1 |     0 |     5 |     - |rounding|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     7 |     - |  1488k |   0 |  10 |   6 |   9 |   3 |  2 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     9 |     - |  1523k |   0 |  10 |   6 |  10 |   4 |  3 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    10 |     - |  1557k |   0 |  10 |   6 |  11 |   5 |  4 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    11 |     - |  1572k |   0 |  10 |   6 |  12 |   6 |  5 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
r 0.0s|     1 |     0 |    15 |     - |randroun|   0 |  10 |   6 |  13 |   0 |  6 |   0 |   0 | 2.737500e+01 | 2.700000e+01 |   1.39%| unknown
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.700000e+01 | 2.700000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes      : 1
Primal Bound       : +2.70000000000000e+01 (15 solutions)
Dual Bound         : +2.70000000000000e+01
Gap                : 0.00 %

しかしながら、たまにはこの挙動をもう少し深掘りしてみるのも良いでしょう。

本記事では、SCIPの内部構造を、実際のコードを追ってみようと思う。

分枝限定法の説明

SCIPをはじめとする混合整数計画ソルバーは、一般に分枝限定法 (Branch-and-Bound)と呼ばれるアルゴリズムをベースとして求解を行う。実装を見る前に、まずはナイーブな分枝限定法を復習する。

混合整数計画問題とLP緩和

混合整数線形計画問題 (Mixed-Integer Linear Programming, MILP) は以下の形式で表される^[1]：

\begin{align} \min \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \\ & x_i \in \mathbb{Z} \quad (i \in I) \end{align}

ここで $I$ は整数制約を持つ変数のインデックス集合である。

分枝限定法を取り扱うにあたり、上記の問題で変数が連続値を取れるようにしたLP緩和 (Linear Programming Relaxation) した問題を取り扱う：

\begin{align} \min \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \end{align}

LP緩和の重要な性質は以下の通りである：

下界の提供: LP緩和の最適値は元のMIPの最適値の下界を与える
効率的な解法: 単体法や内点法で高速に解ける場合が多い

分枝限定法の基本アルゴリズム

分枝限定法は、問題を部分問題に分割し各部分問題を解いて最適解を見つける手法である。
具体的には、整数変数の取りうる範囲をノードで場合分けしながら、以下のようにノードを生成し、探索を進める手法となる。

分枝限定法のイメージ

基本的なアルゴリズムは以下のフローチャートの通りとなる。
分枝限定法の基本アルゴリズム

アルゴリズムの詳細

1. 初期化

ルートノードを作成し、未探索ノードリストに追加
上界（現在の最良解）を $+\infty$ に設定

2. ノード選択

未探索ノードリストからノードを選択する

3. LP緩和の解決

選択したノードのLP緩和を解く
LP緩和問題の最適解とその目的関数値（下界）を得る

4. 枝刈りの判定

LP緩和が実行不可能 → そのノードを枝刈り (Prune) する。
下界 ≥ 上界 → どのように工夫してもこれ以上良い解がそのノードから見つからないため、そのノードを枝刈りする

5. 整数性の確認

LP解が整数なら、新しい実行可能解として保存し、上界を更新

6. 分枝

整数制約を満たさない変数 $x_j$ （値が $f$ で非整数）を選択
ある変数の取りうる範囲を分けた2つの子ノードを作成する：
- $x_j \leq \lfloor f \rfloor$
- $x_j \geq \lceil f \rceil$

この繰り返しで変数の幅を狭めながら上界、下界を更新し、最終的に上界と下界が一致した時点、あるいは一定の差以下になった時点で処理を終了する。

SCIPのアルゴリズム全体像

分枝限定法を復習したところで、SCIPの実装を見ていく。SCIPは単純な分枝限定法に加えて、カット生成、ヒューリスティクス、伝播など多くの機能を統合した 分枝カット法 (Branch-and-Cut) を実装している。これにより、より効率的に枝刈りを行い、求解性能を向上させている。

以後、SCIPの各関数にはGitHub上の対応する実装へのリンクを付与しているので、興味がある方は実際のコードを参照してほしい。

求解処理フロー全体像

SCIPをコマンドラインから起動した場合、以下の流れで求解処理のエントリーポイントであるSCIPsolve()に到達する。

main(): プログラムのエントリーポイント
SCIPrunShell(): SCIPインスタンス作成、プラグイン登録
SCIPprocessShellArguments(): バッチファイル処理
SCIPsolve(): 求解処理開始

このSCIPsolve()関数が、SCIPの求解処理の中核であり、以下で構成されている。
図の赤字はナイーブな分枝限定法には存在しないSCIP独自の要素を示す。

SCIPの求解処理フロー全体像

ナイーブな分枝限定法との違い

前章で説明したナイーブな分枝限定法と比較して、SCIPには以下の追加要素がある。：

追加要素	目的、効果
前処理フェーズ	求解前に問題を簡略化し、変数・制約の削減を行う。例えば $x + y \leq 5$ と $x + y \geq 5$ があれば $x + y = 5$ に統合できる。また、 $2x \leq 3$ で $x$ が整数なら $x \leq 1$ という制約に書き直すことができる
領域伝播	例えば $x, y, z$ が正の決定変数とし、 $x+y\leq10, y+z=3$ という制約があるときに、 $x=9$ に固定した分枝操作を行っているのであれば $y \leq 1$ となるため、 $y = 1$ に固定してしまって問題なく、結果的に $z=2$ と $y, z$ の値も自動的に決定してしまうことがわかる。このようにして変数の関係性を伝搬させ、取りうる範囲を縮小することにより、早期の枝刈りおよび探索空間の削減ができる
カット生成	LP緩和に有効不等式を追加し、下界の改善を行う。例えば $x_1 + x_2 \leq 1.5$ （ $x_i \in \{0,1\}$ ）のLP解が $(0.75, 0.75)$ のとき、 $x_1, x_2$ が整数という条件から $x_1 + x_2 \leq 1$ という制約 (カット)を追加し、LP緩和問題の実行可能解の範囲をより効率よく絞るようにする
ヒューリスティクス	良い実行可能解を早期に発見し、上界の改善、枝刈りの促進を行う。例えばLP緩和問題の解 $(1.3, 2.7)$ をエイヤで $(1, 3)$ に丸めて実行可能解を得る（Rounding）。良い上界があれば多くのノードを枝刈りできる
衝突解析	矛盾の原因を学習し、同じ失敗の回避、探索の高速化を行う。例えば $x_1=1, x_2=1, x_3=1$ の組み合わせで実行不可能になった場合、 $x_1 + x_2 + x_3 \leq 2$ という衝突制約を追加し、以後同じ失敗を回避する

これらの要素が組み合わさることで、ナイーブな分枝限定法と比較して大幅な性能向上を実現している。

各ステップの詳細

前処理フェーズ (SCIPpresolve())

SCIPでは求解前に問題を簡略化することで、探索空間を大幅に削減する特徴がある。
以下のように前処理は複数のステップで構成されている。

SCIPpresolve()
├── SCIPconshdlrPresolve()   制約ハンドラ前処理
├── SCIPpropPresol()         前処理フェーズにおける制約伝播
├── SCIPpresolExec()         前処理実行
└── SCIPprimalHeuristics()   前処理中のヒューリスティクスの実行

主な処理:

関数	役割
SCIPconshdlrPresolve()	制約ハンドラによる前処理（係数強化、冗長制約削除）
SCIPpropPresol()	伝播器による前処理（変数境界の縮小）
SCIPpresolExec()	前処理器の実行（変数固定、制約タイプ変換）
SCIPprimalHeuristics()	前処理中のヒューリスティクス実行

メインループ (SCIPsolveCIP())

前章の「ノード選択→LP解決→分枝判定」のループに対応する。
主に以下のステップで構成されている。

SCIPsolveCIP()
├── SCIPnodeselSelect()   ノード選択
├── SCIPnodeFocus()       ノードアクティベート（内部状態をそのノードを探索するように処理する）
└── solveNode()           ノード処理

主な処理:

関数	役割
SCIPnodeselSelect()	未探索ノードから次に処理するノードを選択
SCIPnodeFocus()	ノードをアクティベートしLP状態を復元
solveNode()	1つのノードを処理

ノード処理 (solveNode())

前章との対比: 前章の「LP緩和を解く→整数解か判定→分枝」に対応する。SCIPでは単純なLP解決の代わりに、伝播→LP→カット生成→ヒューリスティクスのループを繰り返す。これにより下界の改善と実行可能解の早期発見を同時に行う。

solveNodeは以下のステップで構成されている。

solveNode()
├── SCIPnodeselSelect()       次ノード選択
├── SCIPprimalHeuristics()    ノード選択後ヒューリスティクス
├── SCIPtreeSetFocusNodeLP()  LPを解くか判定
│
└── 【外部求解ループ】
    │
    ├── 【内部求解ループ】
    │   └── propAndSolve()
    │       ├── propagateDomains()   領域伝播
    │       ├── solveNodeLP()        LP緩和問題を解く
    │       │   └── priceAndCutLoop() 
    │       │       ├── SCIPpriceLoop()
    │       │       └── separationRoundLP() 
    │       └── SCIPprimalHeuristics() ヒューリスティクス
    │
    ├── SCIPprimalHeuristics()    LPループ後ヒューリスティクス
    └── enforceConstraints()      制約の強制

主な処理:

関数	役割
propAndSolve()	伝播・LP・分離のループ
propagateDomains()	変数境界の縮小（★前章にない処理）
solveNodeLP()	LP緩和を解く
priceAndCutLoop()	列生成とカット生成のループ
SCIPpriceLoop()	列生成（Pricerを登録しない限りこちらはスキップされる）
separationRoundLP()	カット生成
SCIPsepaExecLP()	分離器によるカット生成
SCIPconshdlrSeparateLP()	制約ハンドラによるカット生成
SCIPprimalHeuristics()	ヒューリスティクス実行
enforceConstraints()	制約の強制

カットが追加された場合はLPを再び解き、変化がなくなるまでこのループを繰り返す。

衝突解析 (Conflict Analysis)

伝播やLP解決でカットオフ（矛盾）が検出された場合、衝突解析が呼び出される。

参照: src/scip/conflict_graphanalysis.c

基本的な考え方：

ノードが実行不可能になった原因を分析
その原因となる変数固定の組み合わせを特定
衝突制約 (conflict constraint) を生成
制約が生成されることにより、以後、同じ組み合わせを避ける

これにより、同じ失敗を繰り返すことなく効率的に探索を進められる。

実装上の工夫

コアデータ構造

分枝限定法のノード操作のたびにいちいち全ての変数を再定義してしまうと、計算コストが非常に高くなってしまう。SCIPでは分枝限定木 (SCIP_TREE) としてノードを管理し、ノードごとにどの変数が変更されているかの差分情報のみを保存することで効率化している。
SCIPの中心となるデータ構造は src/scip/struct_scip.h で定義されている。

具体的なデータ構造として以下のような情報を持っている。

struct Scip {
    SCIP_MEM*             mem;          // メモリ管理
    SCIP_SET*             set;          // 設定とプラグイン
    SCIP_STAT*            stat;         // 統計情報
    SCIP_PROB*            origprob;     // 元問題
    SCIP_PROB*            transprob;    // 変換後の問題
    SCIP_PRIMAL*          primal;       // 主問題データ（実行可能解）
    SCIP_TREE*            tree;         // 分枝限定木
    SCIP_LP*              lp;           // LP緩和
    SCIP_CONFLICT*        conflict;     // 衝突解析
    // ...
};

プラグインシステム

SCIPの求解フロー上ではヒューリスティックス、分枝規則、ノード選択、制約ハンドラなどが存在するが、これらは全てプラグインとして実装されている。ユーザは独自のアルゴリズムをプラグインとして追加できるため、非常に高い拡張性を持つ。
SCIPはこれらのプラグインを適切なタイミングで自動で呼び出す仕組みを備えている。

プラグインの配置

全てのプラグインは src/scip/ ディレクトリ内に、プレフィックスで種類が分かる命名規則で配置されている：

具体例としては以下のような構成になっている。

src/scip/
├── branch_*.c    分枝規則
│   ├── branch_relpscost.c    相対擬似コスト分枝（デフォルト）
│   ├── branch_fullstrong.c   完全強分枝
│   ├── branch_pscost.c       擬似コスト分枝
│   └── ...
│
├── nodesel_*.c   ノード選択
│   ├── nodesel_estimate.c    推定値ベース選択（デフォルト）
│   ├── nodesel_bfs.c         最良優先探索
│   ├── nodesel_dfs.c         深さ優先探索
│   └── ...
│
├── heur_*.c      ヒューリスティクス
│   ├── heur_rounding.c       丸めヒューリスティクス
│   ├── heur_feaspump.c       実行可能ポンプ
│   ├── heur_rins.c           RINS
│   ├── heur_alns.c           適応大近傍探索
│   └── ...
│
├── sepa_*.c      分離器（カット生成）
│   ├── sepa_gomory.c         Gomoryカット
│   ├── sepa_clique.c         クリークカット
│   ├── sepa_knapsackcover.c  ナップサックカバーカット
│   └── ...
│
├── cons_*.c      制約ハンドラ
│   ├── cons_linear.c         線形制約
│   ├── cons_knapsack.c       ナップサック制約
│   ├── cons_setppc.c         集合パッキング/カバー/分割
│   ├── cons_indicator.c      指示変数制約
│   └── ...
│
├── prop_*.c      伝播器
│   ├── prop_obbt.c           最適化ベース境界強化
│   ├── prop_probing.c        プロービング
│   └── ...
│
└── presol_*.c    前処理器
    ├── presol_trivial.c      単純な前処理
    ├── presol_implics.c      含意による前処理
    └── ...

プラグイン一覧

種類	プレフィックス	役割
分枝規則	`branch_`	分枝変数の選択方法
ノード選択	`nodesel_`	次に処理するノードの選択
ヒューリスティクス	`heur_`	実行可能解の探索
分離器	`sepa_`	カット（有効不等式）の生成
制約ハンドラ	`cons_`	制約タイプごとの処理
伝播器	`prop_`	変数境界の縮小
前処理器	`presol_`	前処理による問題簡略化

各プラグインの詳細をかいつまんで紹介したものは以下となる。

分枝規則の具体例

プラグイン	説明
branch_relpscost.c	相対擬似コスト分枝（デフォルト）。過去の分枝履歴から各変数の「分枝効果」を学習し、最も効果的な変数を選択する
branch_fullstrong.c	完全強分枝。全候補変数で実際にLPを解いて最良を選択（高精度だが計算コスト大）
branch_pscost.c	擬似コスト分枝。過去の分枝による目的関数変化を記録し、変数選択に利用

ノード選択の具体例

プラグイン	説明
nodesel_estimate.c	推定値ベース選択（デフォルト）。各ノードの最適解推定値に基づいて選択
nodesel_bfs.c	最良優先探索 (Best-First Search)。下界が最も小さいノードを優先
nodesel_dfs.c	深さ優先探索 (Depth-First Search)。メモリ効率が良く、早期に実行可能解を発見しやすい

選択基準の例: 未探索ノードが3つあり、それぞれの下界が $L_1 = 10.5$ 、 $L_2 = 12.3$ 、 $L_3 = 11.0$ のとき、BFSでは $L_1$ が最小のノード1を選択する。一方、推定値ベースでは各ノードの最適解推定値 $E_i = L_i + \text{(擬似コストによる補正)}$ を計算し、最小の $E_i$ を持つノードを選択する。

ヒューリスティクスの具体例

プラグイン
説明

heur_rounding.c
LP解を制約を満たすように丸めて実行可能解を生成

heur_feaspump.c

実行可能ポンプ。LP解と整数解の間を反復的に移動して実行可能解を探索

heur_rins.c

RINS (Relaxation Induced Neighborhood Search)。LP解と現在の最良解で一致する変数を固定し、部分問題を解く

heur_alns.c

適応大近傍探索。複数の破壊・修復オペレータを適応的に選択

Roundingの例: LP解が (x_1, x_2, x_3) = (1.3, 0.7, 2.1) のとき、制約 x_1 + x_2 \leq 2 を考慮しながら丸める。単純に四捨五入すると (1, 1, 2) だが、これは 1+1=2 \leq 2 を満たすので実行可能解となる。
Feasibility Pumpの例: LP解 \tilde{x} = (1.3, 2.7) を丸めた整数点 \bar{x} = (1, 3) が実行不可能なら、\min \|x - \bar{x}\| を目的関数として新たなLPを解き、その解をまた丸める。これを実行可能解が見つかるまで反復する。

プラグイン	説明
heur_rounding.c	LP解を制約を満たすように丸めて実行可能解を生成
heur_feaspump.c	実行可能ポンプ。LP解と整数解の間を反復的に移動して実行可能解を探索
heur_rins.c	RINS (Relaxation Induced Neighborhood Search)。LP解と現在の最良解で一致する変数を固定し、部分問題を解く
heur_alns.c	適応大近傍探索。複数の破壊・修復オペレータを適応的に選択

分離器の具体例

プラグイン
説明

sepa_gomory.c

Gomoryカット。LP最適解のシンプレックス表から導出される混合整数カット

sepa_clique.c

クリークカット。同時に1になれない変数の集合からカットを生成

sepa_knapsackcover.c

ナップサックカバーカット。ナップサック制約から導出されるカット

sepa_zerohalf.c

{0, 1/2}カット。係数が0か1/2の線形結合から整数カットを導出

Gomoryカットの例: シンプレックス表の行が x_1 + 0.4x_3 + 0.6x_4 = 2.7 のとき、小数部分を取り出して 0.4x_3 + 0.6x_4 \geq 0.7 というカットを生成する。これは x_1 が整数という条件から導かれる有効不等式である。
カバーカットの例: ナップサック制約 3x_1 + 4x_2 + 5x_3 \leq 7（x_i \in \{0,1\}）において、\{x_1, x_2, x_3\} はカバー（全部1だと制約違反）なので、x_1 + x_2 + x_3 \leq 2 というカットを追加できる。

プラグイン	説明
sepa_gomory.c	Gomoryカット。LP最適解のシンプレックス表から導出される混合整数カット
sepa_clique.c	クリークカット。同時に1になれない変数の集合からカットを生成
sepa_knapsackcover.c	ナップサックカバーカット。ナップサック制約から導出されるカット
sepa_zerohalf.c	{0, 1/2}カット。係数が0か1/2の線形結合から整数カットを導出

制約ハンドラの具体例

プラグイン
説明


cons_linear.c

線形制約。一般的な線形不等式・等式を処理

cons_knapsack.c

ナップサック制約。\sum a_i x_i \leq b（x_i \in \{0,1\}, a_i > 0）の特殊処理

cons_setppc.c
集合パッキング/カバー/分割制約

cons_indicator.c

指示変数制約。y=1 \Rightarrow ax \leq b の形式

制約タイプの変換例: 線形制約 2x_1 + 3x_2 + 4x_3 \leq 6（x_i \in \{0,1\}, 係数が正）は、前処理でナップサック制約として認識され、cons_knapsack による特殊な伝播・カット生成が適用される。これにより、一般の線形制約として処理するよりも効率的に解ける。
集合制約の例:
集合パッキング: x_1 + x_2 + x_3 \leq 1（高々1つ選択）
集合カバー: x_1 + x_2 + x_3 \geq 1（少なくとも1つ選択）
集合分割: x_1 + x_2 + x_3 = 1（ちょうど1つ選択）

プラグイン	説明
cons_linear.c	線形制約。一般的な線形不等式・等式を処理
cons_knapsack.c	ナップサック制約。 $\sum a_i x_i \leq b$ （ $x_i \in \{0,1\}$ , $a_i > 0$ ）の特殊処理
cons_setppc.c	集合パッキング/カバー/分割制約
cons_indicator.c	指示変数制約。 $y=1 \Rightarrow ax \leq b$ の形式

伝播器の具体例

プラグイン
説明

prop_obbt.c

最適化ベース境界強化 (OBBT)。LPを解いて変数の上下界を強化

prop_probing.c

プロービング。変数を仮固定して含意を調査

prop_redcost.c

被約費用伝播。LP双対情報から変数固定を導出

OBBTの例: 変数 x_1 の上界を強化するため、現在の制約下で \max x_1 を解く。結果が x_1^* = 3.2 なら、x_1 が整数の場合 x_1 \leq 3 に上界を強化できる。
被約費用伝播の例: 最小化問題でLP最適解における変数 x_j の被約費用（reduced cost）が r_j = 5 のとき、現在の上界と下界のギャップが \Delta = 4 なら、x_j を下界に固定しても最適性は失われないことが分かる。

プラグイン	説明
prop_obbt.c	最適化ベース境界強化 (OBBT)。LPを解いて変数の上下界を強化
prop_probing.c	プロービング。変数を仮固定して含意を調査
prop_redcost.c	被約費用伝播。LP双対情報から変数固定を導出

前処理器の具体例

プラグイン
説明

presol_trivial.c

単純な前処理。明らかに固定できる変数の検出

presol_implics.c

含意による前処理。変数間の含意関係を利用

presol_domcol.c

支配列検出。他の列に支配される変数を削除

単純な前処理の例: 制約 x_1 \geq 5 と x_1 \leq 5 があれば x_1 = 5 に固定できる。また、x_1 \in \{0,1\} で目的関数の係数が正（最小化）なら x_1 = 0 に固定できる可能性がある。
含意の例: 制約 x_1 + x_2 \leq 1（x_i \in \{0,1\}）から、x_1 = 1 \Rightarrow x_2 = 0 という含意が導かれる。これを保存しておき、x_1 = 1 に固定された時点で自動的に x_2 = 0 と伝播する。
支配列の例: 変数 x_1 と x_2 があり、すべての制約で x_1 の係数 \leq x_2 の係数、かつ目的関数で c_1 \leq c_2（最小化）なら、x_2 は x_1 に支配されるので削除できる。

プラグイン	説明
presol_trivial.c	単純な前処理。明らかに固定できる変数の検出
presol_implics.c	含意による前処理。変数間の含意関係を利用
presol_domcol.c	支配列検出。他の列に支配される変数を削除

これらのプラグインは自作してSCIPに組み込むことも可能であり、ユーザ固有のアルゴリズムを容易に追加できる。

実際にデバッグログとともに見てみる

ここまでの解説を、実際のデバッグログで確認する。小さなMIP問題を使って、3章で説明した各フェーズがどのように実行されるかを見ていく。

環境構築

本記事で使用するリポジトリは、SCIP公式リポジトリ（scipopt/scip）のtag v10.0.0 をフォークし、デバッグログ出力を追加したものである。オリジナルとの差分は、求解処理の各フェーズで [DEBUG] プレフィックス付きのログを出力する printf 文を追加した点のみである。

# 作業ディレクトリの作成
mkdir -p ~/scip_work && cd ~/scip_work

# SoPlexのビルド（SCIPが依存するLPソルバー）
git clone -b release-700 https://github.com/scipopt/soplex
cd soplex
mkdir build && cd build
cmake ..
make -j4
cd ../..

# SCIPのクローン（v10.0.0-debugブランチを指定）
git clone -b v10.0.0-debug https://github.com/j-i-k-o/scip_for_debug
cd scip_for_debug

# SCIPのビルド（SoPlexのパスを指定）
mkdir build && cd build
cmake .. -DAUTOBUILD=ON -DSOPLEX_DIR=~/scip_work/soplex/build
make -j4
cd ..

# 実行確認
./build/bin/scip --version

デモ用の問題ファイルとバッチファイルは demo/ ディレクトリに配置されている：

demo/
├── test_problem.lp      # 小規模MIP問題（0-1ナップサック風）
└── batch.txt            # test_problem.lp 用バッチファイル

テスト問題

test_problem.lp は10個の0-1変数、6つの制約を持つ小さな問題である。^[2]

Maximize
 obj: 10 x1 + 9 x2 + 8 x3 + 7 x4 + 6 x5 + 5 x6 + 4 x7 + 3 x8 + 2 x9 + x10

Subject To
 c1: 7 x1 + 6 x2 + 5 x3 + 4 x4 + 3 x5 + 2 x6 + x7 + x8 + x9 + x10 <= 15
 c2: x1 + 2 x2 + 3 x3 + 4 x4 + 5 x5 + 6 x6 + 7 x7 + 6 x8 + 5 x9 + 4 x10 <= 18
 c3: 2 x1 + x2 + 2 x3 + x4 + 2 x5 + x6 + 2 x7 + x8 + 2 x9 + x10 <= 8
 c4: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 <= 6
 c5: 3 x1 + 2 x3 + x5 + 3 x7 + 2 x9 <= 6
 c6: 2 x2 + 3 x4 + 4 x6 + 2 x8 + x10 <= 7

Generals
 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
End

実行コマンド:

./build/bin/scip -b demo/batch.txt

念の為、実行した際の標準出力ログ全文をこちらに添付する

実行ログ全文

SCIP version 10.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 9.0.0] [GitHash: 5c1227b4cf-dirty]
Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline EditLine w  GNU library for command line editing (gnu.org/s/readline)
  SoPlex 9.0.0         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 1fb93591]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.12          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  TinyCThread 1.2      small portable implementation of the C11 threads API (tinycthread.github.io)
  GMP 6.3.0            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  AMPL/MP 4.0.3        AMPL .nl file reader library (github.com/ampl/mp)
  Nauty 2.8.8          Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)
  sassy 2.0            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)
  Ipopt 3.14.19        Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

user parameter file <scip.set> not found - using default parameters


read problem <demo/test_problem.lp>
============

original problem has 10 variables (0 bin, 10 int, 0 cont) and 6 constraints


========================================
[DEBUG] SCIPsolve() 開始 - メイン求解エントリーポイント
========================================
[DEBUG] Phase 2: SCIPpresolve() 開始 - 前処理フェーズ
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=BEFOREPRESOL, nheurs=61)
[DEBUG] heur <trivial> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=-1, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <trivial> が解を発見! (obj=-0.0000)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG]       SCIPprimalHeuristics() 新しい最良解発見!
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
[DEBUG] presol <trivial> 実行開始 (round=0, timing=4)
[DEBUG] presol <trivial> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <inttobinary> 実行開始 (round=0, timing=4)
[DEBUG] presol <inttobinary> 完了: result=DIDNOTRUN, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] conshdlr <linear> presol開始 (conss=6, round=0, timing=4)
[DEBUG] conshdlr <linear> presol完了: result=DIDNOTFIND, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] presol <implics> 実行開始 (round=0, timing=8)
[DEBUG] presol <implics> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] presol <gateextraction> 実行開始 (round=0, timing=16)
[DEBUG] presol <gateextraction> 完了: result=DIDNOTRUN, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] conshdlr <linear> presol開始 (conss=6, round=0, timing=16)
[DEBUG] conshdlr <linear> presol完了: result=SUCCESS, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 6 upgd conss, 0 impls, 0 clqs, 0 implints
[DEBUG] presol <trivial> 実行開始 (round=1, timing=4)
[DEBUG] presol <trivial> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <inttobinary> 実行開始 (round=1, timing=4)
[DEBUG] presol <inttobinary> 完了: result=DIDNOTRUN, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] conshdlr <knapsack> presol開始 (conss=6, round=1, timing=4)
[DEBUG] conshdlr <knapsack> presol完了: result=DIDNOTFIND, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] conshdlr <knapsack> presol開始 (conss=6, round=1, timing=8)
[DEBUG] conshdlr <knapsack> presol完了: result=DIDNOTFIND, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <implics> 実行開始 (round=1, timing=8)
[DEBUG] presol <implics> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] presol <gateextraction> 実行開始 (round=1, timing=16)
[DEBUG] presol <gateextraction> 完了: result=DIDNOTRUN, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] conshdlr <knapsack> presol開始 (conss=6, round=1, timing=16)
[DEBUG] conshdlr <knapsack> presol完了: result=DIDNOTFIND, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <dualcomp> 実行開始 (round=1, timing=16)
[DEBUG] presol <dualcomp> 完了: result=DIDNOTRUN, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <domcol> 実行開始 (round=1, timing=16)
[DEBUG] presol <domcol> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG] presol <sparsify> 実行開始 (round=1, timing=16)
[DEBUG] presol <sparsify> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=1, maxrounds=2147483647)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
   (0.0s) probing cycle finished: starting next cycle
[DEBUG] presol <dualsparsify> 実行開始 (round=1, timing=16)
[DEBUG] presol <dualsparsify> 完了: result=DIDNOTFIND, 累計固定=0, 累計集約=0, 累計界変更=0, 累計削除=0
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present (symcode time: 0.00)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] conshdlr <components> presol開始 (conss=0, round=1, timing=32)
[DEBUG] conshdlr <components> presol完了: result=DIDNOTFIND, 累計固定=0, 累計界変更=0, 累計削除=0
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGPRESOLLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques, 0 implied integral variables (0 bin, 0 int, 0 cont)
presolved problem has 10 variables (10 bin, 0 int, 0 cont) and 6 constraints
      6 constraints of type <knapsack>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
[DEBUG] Phase 2: SCIPpresolve() 完了
[DEBUG] Phase 3: initSolve() 開始 - 求解初期化・分枝限定木作成
transformed 1/1 original solutions to the transformed problem space
[DEBUG] Phase 3: initSolve() 完了 - ルートノード作成済み


[DEBUG] Phase 4: SCIPsolveCIP() 開始 - 分枝限定法メインループ
========================================
[DEBUG] SCIPnodeselSelect() ノード選択中... (nodesel=<estimate>)
[DEBUG] SCIPnodeselSelect() 選択完了: node #1 (depth=0)
[DEBUG] SCIPnodeFocus() ノード活性化 (lowerbound=-100000000000000000000.0000)

[DEBUG] ノード 1 処理開始 (depth=0, 残りノード=0)
[DEBUG]   -> solveNode() 開始
[DEBUG]     propAndSolve() 開始 (伝播・LP・分離ループ)
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <dualfix> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=BEFORENODE, nheurs=61)
[DEBUG] heur <trivial> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG] LP解決: status=OPTIMAL, obj=-6.000000, rows=6, cols=10, iter=0
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     0 |     - |   locks|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 6.000000e+00 | 816.67%| unknown
[DEBUG] heur <locks> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=0, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <locks> が解を発見! (obj=-6.0000)
i 0.0s|     1 |     0 |     0 |     - |  oneopt|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 1.600000e+01 | 243.75%| unknown
[DEBUG] heur <oneopt> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=0, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <oneopt> が解を発見! (obj=-16.0000)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG]       SCIPprimalHeuristics() 新しい最良解発見!
[DEBUG]     propAndSolve() 完了 (lpsolved=0, cutoff=0)
[DEBUG]     propAndSolve() 開始 (伝播・LP・分離ループ)
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <dualfix> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=AFTERPROPLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG]       solveNodeRelax() 開始 (beforelp=1, nrelaxs=1)
[DEBUG]       solveNodeRelax() 完了 (cutoff=0)
[DEBUG]       solveNodeLP() 開始 (LP緩和を解く)
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=6, cols=10, iter=5
[DEBUG]     priceAndCutLoop() 呼び出し (fullseparation=1)
  0.0s|     1 |     0 |     5 |     - |  1397k |   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 1.600000e+01 |  71.09%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
r 0.0s|     1 |     0 |     5 |     - |simplero|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.100000e+01 |  30.36%| unknown
[DEBUG] heur <simplerounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=0, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <simplerounding> が解を発見! (obj=-21.0000)
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=6, cols=10, iter=5
[DEBUG] heur <randrounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=1
r 0.0s|     1 |     0 |     5 |     - |rounding|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG] heur <rounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=0, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <rounding> が解を発見! (obj=-26.0000)
[DEBUG] heur <shifting> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=1
[DEBUG]         ★ ヒューリスティクス <shifting> が解を発見! (obj=-26.0000)
[DEBUG] heur <oneopt> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG]       SCIPprimalHeuristics() 新しい最良解発見!
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg1_s4>, プール内カット数=1
[DEBUG] cutpool: カット追加 <gom1_s4>, プール内カット数=2
[DEBUG] cutpool: カット追加 <scg1_s2>, プール内カット数=3
[DEBUG] cutpool: カット追加 <gom1_s2>, プール内カット数=4
[DEBUG] cutpool: カット追加 <scg1_x0>, プール内カット数=5
[DEBUG] cutpool: カット追加 <gom1_x0>, プール内カット数=6
[DEBUG] cutpool: カット追加 <scg1_s3>, プール内カット数=7
[DEBUG] cutpool: カット追加 <scg1_s5>, プール内カット数=8
[DEBUG] cutpool: カット追加 <gom1_s5>, プール内カット数=9
[DEBUG] cutpool: カット追加 <scg1_x5>, プール内カット数=10
[DEBUG] sepa_gomory: Gomoryカット 10個生成 (depth=0, 最大効率=0.0779)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=10, depth=0
[DEBUG] cutpool: カット追加 <objlci1_0>, プール内カット数=11
[DEBUG] cutpool: カット追加 <lci1_1>, プール内カット数=12
[DEBUG] cutpool: カット追加 <cmir1_2>, プール内カット数=13
[DEBUG] cutpool: カット追加 <flowcover1_3>, プール内カット数=14
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=4, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <zerohalf1_x0>, プール内カット数=15
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=1, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=5, cutoff=0)
[DEBUG] cutpool分離: 15 カット発見, プール内=15, 効果的=15
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=7, cols=10, iter=6
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=REDUCEDDOM, 境界変更=3, depth=0
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=2, cutoff=0)
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=7, cols=10, iter=6
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=4, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] heur <randrounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG] heur <rounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG] heur <shifting> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=2
[DEBUG]       SCIPprimalHeuristics() 完了
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] cutpool分離: 10 カット発見, プール内=15, 効果的=10
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg2_s5>, プール内カット数=16
[DEBUG] cutpool: カット追加 <scg2_x0>, プール内カット数=17
[DEBUG] cutpool: カット追加 <gom2_x0>, プール内カット数=18
[DEBUG] cutpool: カット追加 <scg2_x6>, プール内カット数=19
[DEBUG] sepa_gomory: Gomoryカット 4個生成 (depth=0, 最大効率=0.1740)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=14, depth=0
[DEBUG] cutpool: カット追加 <objlci2_0>, プール内カット数=20
[DEBUG] cutpool: カット追加 <flowcover2_1>, プール内カット数=21
[DEBUG] cutpool: カット追加 <cmir2_2>, プール内カット数=22
[DEBUG] cutpool: カット追加 <flowcover2_3>, プール内カット数=23
[DEBUG] cutpool: カット追加 <cmir2_4>, プール内カット数=24
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=9, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <zerohalf2_x1>, プール内カット数=25
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=2, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=14, cutoff=0)
[DEBUG] cutpool分離: 10 カット発見, プール内=25, 効果的=10
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=9, cols=10, iter=7
  0.0s|     1 |     0 |     7 |     - |  1488k |   0 |  10 |   6 |   9 |   3 |  2 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=3
[DEBUG]         ★ ヒューリスティクス <simplerounding> が解を発見! (obj=-26.0000)
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=4, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=5, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] heur <randrounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=3
[DEBUG]         ★ ヒューリスティクス <randrounding> が解を発見! (obj=-26.0000)
[DEBUG] heur <rounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=3
[DEBUG] heur <shifting> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=3
[DEBUG]         ★ ヒューリスティクス <shifting> が解を発見! (obj=-26.0000)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] cutpool分離: 18 カット発見, プール内=25, 効果的=18
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg3_x6>, プール内カット数=26
[DEBUG] cutpool: カット追加 <gom3_x6>, プール内カット数=27
[DEBUG] cutpool: カット追加 <scg3_x0>, プール内カット数=28
[DEBUG] cutpool: カット追加 <scg3_x5>, プール内カット数=29
[DEBUG] cutpool: カット追加 <gom3_x5>, プール内カット数=30
[DEBUG] cutpool: カット追加 <scg3_s5>, プール内カット数=31
[DEBUG] cutpool: カット追加 <gom3_s5>, プール内カット数=32
[DEBUG] cutpool: カット追加 <scg3_s2>, プール内カット数=33
[DEBUG] cutpool: カット追加 <gom3_s2>, プール内カット数=34
[DEBUG] cutpool: カット追加 <scg3_s4>, プール内カット数=35
[DEBUG] sepa_gomory: Gomoryカット 10個生成 (depth=0, 最大効率=0.3133)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=24, depth=0
[DEBUG] cutpool: カット追加 <objcmir3_0>, プール内カット数=36
[DEBUG] cutpool: カット追加 <cmir3_1>, プール内カット数=37
[DEBUG] cutpool: カット追加 <cmir3_2>, プール内カット数=38
[DEBUG] cutpool: カット追加 <cmir3_3>, プール内カット数=39
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=13, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <zerohalf> 実行: result=DIDNOTFIND, カット数=2, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=22, cutoff=0)
[DEBUG] cutpool分離: 14 カット発見, プール内=39, 効果的=14
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=10, cols=10, iter=9
  0.0s|     1 |     0 |     9 |     - |  1523k |   0 |  10 |   6 |  10 |   4 |  3 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=4
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=4, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=5, maxrounds=1)
[DEBUG] conshdlr <knapsack> 伝播: result=REDUCEDDOM, 境界変更=2, 制約数=4
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] heur <randrounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=4
[DEBUG] heur <rounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=4
[DEBUG] heur <shifting> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=4
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] cutpool分離: 14 カット発見, プール内=39, 効果的=14
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg4_x0>, プール内カット数=40
[DEBUG] cutpool: カット追加 <gom4_x0>, プール内カット数=41
[DEBUG] cutpool: カット追加 <scg4_x1>, プール内カット数=42
[DEBUG] cutpool: カット追加 <gom4_x1>, プール内カット数=43
[DEBUG] cutpool: カット追加 <scg4_s2>, プール内カット数=44
[DEBUG] cutpool: カット追加 <gom4_s2>, プール内カット数=45
[DEBUG] cutpool: カット追加 <scg4_s5>, プール内カット数=46
[DEBUG] cutpool: カット追加 <gom4_s5>, プール内カット数=47
[DEBUG] cutpool: カット追加 <scg4_x5>, プール内カット数=48
[DEBUG] cutpool: カット追加 <gom4_x5>, プール内カット数=49
[DEBUG] cutpool: カット追加 <scg4_x6>, プール内カット数=50
[DEBUG] cutpool: カット追加 <scg4_x2>, プール内カット数=51
[DEBUG] cutpool: カット追加 <scg4_s6>, プール内カット数=52
[DEBUG] sepa_gomory: Gomoryカット 13個生成 (depth=0, 最大効率=0.2404)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=37, depth=0
[DEBUG] cutpool: カット追加 <objcmir4_0>, プール内カット数=53
[DEBUG] cutpool: カット追加 <cmir4_1>, プール内カット数=54
[DEBUG] cutpool: カット追加 <cmir4_2>, プール内カット数=55
[DEBUG] cutpool: カット追加 <flowcover4_3>, プール内カット数=56
[DEBUG] cutpool: カット追加 <flowcover4_4>, プール内カット数=57
[DEBUG] cutpool: カット追加 <cmir4_5>, プール内カット数=58
[DEBUG] cutpool: カット追加 <flowcover4_6>, プール内カット数=59
[DEBUG] cutpool: カット追加 <cmir4_7>, プール内カット数=60
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=21, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <zerohalf4_x0>, プール内カット数=61
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=3, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=18, cutoff=0)
[DEBUG] cutpool分離: 22 カット発見, プール内=61, 効果的=22
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=11, cols=10, iter=10
  0.0s|     1 |     0 |    10 |     - |  1557k |   0 |  10 |   6 |  11 |   5 |  4 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=5
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=4, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=5, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=6, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] heur <randrounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=5
[DEBUG]         ★ ヒューリスティクス <randrounding> が解を発見! (obj=-26.0000)
[DEBUG] heur <rounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=5
[DEBUG] heur <shifting> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=5
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] cutpool分離: 25 カット発見, プール内=61, 効果的=25
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg5_s4>, プール内カット数=62
[DEBUG] cutpool: カット追加 <gom5_s4>, プール内カット数=63
[DEBUG] cutpool: カット追加 <scg5_s2>, プール内カット数=64
[DEBUG] cutpool: カット追加 <gom5_s2>, プール内カット数=65
[DEBUG] cutpool: カット追加 <scg5_s5>, プール内カット数=66
[DEBUG] cutpool: カット追加 <gom5_s5>, プール内カット数=67
[DEBUG] cutpool: カット追加 <scg5_s6>, プール内カット数=68
[DEBUG] cutpool: カット追加 <gom5_s6>, プール内カット数=69
[DEBUG] cutpool: カット追加 <scg5_x0>, プール内カット数=70
[DEBUG] cutpool: カット追加 <gom5_x0>, プール内カット数=71
[DEBUG] cutpool: カット追加 <scg5_x6>, プール内カット数=72
[DEBUG] sepa_gomory: Gomoryカット 11個生成 (depth=0, 最大効率=0.0835)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=48, depth=0
[DEBUG] cutpool: カット追加 <lci5_0>, プール内カット数=73
[DEBUG] cutpool: カット追加 <cmir5_1>, プール内カット数=74
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=23, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <zerohalf5_x2>, プール内カット数=75
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=4, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=27, cutoff=0)
[DEBUG] cutpool分離: 14 カット発見, プール内=75, 効果的=14
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=12, cols=10, iter=11
  0.0s|     1 |     0 |    11 |     - |  1572k |   0 |  10 |   6 |  12 |   6 |  5 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=6
[DEBUG]         ★ ヒューリスティクス <simplerounding> が解を発見! (obj=-26.0000)
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=4, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=5, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=6, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=7, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG] heur <randrounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=6
[DEBUG]         ★ ヒューリスティクス <randrounding> が解を発見! (obj=-26.0000)
[DEBUG] heur <rounding> 実行: result=DIDNOTFIND, 新解=0, 最良解更新=0, depth=0, 累計呼出=6
[DEBUG] heur <shifting> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=6
[DEBUG]         ★ ヒューリスティクス <shifting> が解を発見! (obj=-26.0000)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG] cutpool分離: 48 カット発見, プール内=75, 効果的=48
[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa <closecuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flower> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <rlt> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <disjunctive> 実行: result=DELAYED, カット数=0, depth=0
[DEBUG] sepa <gauge> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <interminor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <minor> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <convexproj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mixing> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <impliedbounds> 実行: result=DIDNOTFIND, カット数=0, depth=0
[DEBUG] sepa <intobj> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cgmip> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <scg6_x1>, プール内カット数=76
[DEBUG] cutpool: カット追加 <gom6_x1>, プール内カット数=77
[DEBUG] cutpool: カット追加 <scg6_s2>, プール内カット数=78
[DEBUG] cutpool: カット追加 <scg6_x0>, プール内カット数=79
[DEBUG] cutpool: カット追加 <gom6_x0>, プール内カット数=80
[DEBUG] cutpool: カット追加 <scg6_s4>, プール内カット数=81
[DEBUG] cutpool: カット追加 <gom6_s4>, プール内カット数=82
[DEBUG] cutpool: カット追加 <scg6_x4>, プール内カット数=83
[DEBUG] cutpool: カット追加 <scg6_x5>, プール内カット数=84
[DEBUG] cutpool: カット追加 <gom6_x5>, プール内カット数=85
[DEBUG] cutpool: カット追加 <gom6_s6>, プール内カット数=86
[DEBUG] cutpool: カット追加 <scg6_x6>, プール内カット数=87
[DEBUG] cutpool: カット追加 <gom6_x6>, プール内カット数=88
[DEBUG] sepa_gomory: Gomoryカット 13個生成 (depth=0, 最大効率=0.3093)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=61, depth=0
[DEBUG] cutpool: カット追加 <objcmir6_0>, プール内カット数=89
[DEBUG] cutpool: カット追加 <cmir6_1>, プール内カット数=90
[DEBUG] cutpool: カット追加 <cmir6_2>, プール内カット数=91
[DEBUG] cutpool: カット追加 <cmir6_3>, プール内カット数=92
[DEBUG] cutpool: カット追加 <cmir6_4>, プール内カット数=93
[DEBUG] cutpool: カット追加 <cmir6_5>, プール内カット数=94
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=29, depth=0
[DEBUG] sepa <clique> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] cutpool: カット追加 <zerohalf6_x5>, プール内カット数=95
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=5, depth=0
[DEBUG] sepa <lagromory> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <mcf> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <eccuts> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <oddcycle> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <flowcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <cmir> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <knapsackcover> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <strongcg> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <gomorymi> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG] sepa <rapidlearning> 実行: result=DIDNOTRUN, カット数=0, depth=0
[DEBUG]         separationRoundLP() 完了 (カット数=50, cutoff=0)
[DEBUG] cutpool分離: 20 カット発見, プール内=95, 効果的=20
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=13, cols=10, iter=15
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG] prop <redcost> 実行: result=DIDNOTFIND, 境界変更=0, depth=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=0, depth=0, 累計呼出=7
[DEBUG]         ★ ヒューリスティクス <simplerounding> が解を発見! (obj=-26.0000)
[DEBUG]         propagateDomains() 開始 (depth=2, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
[DEBUG]         propagateDomains() 開始 (depth=3, maxrounds=1)
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)
r 0.0s|     1 |     0 |    15 |     - |randroun|   0 |  10 |   6 |  13 |   0 |  6 |   0 |   0 | 2.737500e+01 | 2.700000e+01 |   1.39%| unknown
[DEBUG] heur <randrounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1, depth=0, 累計呼出=7
[DEBUG]         ★ ヒューリスティクス <randrounding> が解を発見! (obj=-27.0000)
[DEBUG]       SCIPprimalHeuristics() 完了
[DEBUG]       SCIPprimalHeuristics() 新しい最良解発見!
[DEBUG]       solveNodeLP() 完了 (LP status=4, obj=100000000000000000000.0000)
[DEBUG]     propAndSolve() 完了 (lpsolved=1, cutoff=1)
[DEBUG]   分枝判定: infeasible=0, cutoff=1, postpone=0, restart=1, unbounded=0
[DEBUG]   分枝判定: solverelaxagain=1, solvelpagain=0, propagateagain=1, branched=0
[DEBUG]   -> solveNode() 完了 (cutoff=1, infeasible=1)
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.700000e+01 | 2.700000e+01 |   0.00%| unknown

========================================
[DEBUG] Phase 4: SCIPsolveCIP() 完了 - メインループ終了

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes      : 1
Primal Bound       : +2.70000000000000e+01 (15 solutions)
Dual Bound         : +2.70000000000000e+01
Gap                : 0.00 %

デバッグログの解説

前処理フェーズ（SCIPpresolve）

[DEBUG] SCIPsolve() 開始 - メイン求解エントリーポイント
[DEBUG] Phase 2: SCIPpresolve() 開始 - 前処理フェーズ
[DEBUG]       SCIPprimalHeuristics() 開始 (timing=BEFOREPRESOL, nheurs=61)
[DEBUG] heur <trivial> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <trivial> が解を発見! (obj=-0.0000)

3.2節で説明した前処理フェーズが開始される。まず BEFOREPRESOL (前処理フェーズの前) タイミングでヒューリスティクスが実行され、trivial ヒューリスティクスが初期解（目的関数値0）を発見している。

[DEBUG] presol <trivial> 実行開始 (round=0, timing=4)
[DEBUG] presol <trivial> 完了: result=DIDNOTFIND
[DEBUG] conshdlr <linear> presol開始 (conss=6, round=0, timing=4)
[DEBUG] conshdlr <linear> presol完了: result=DIDNOTFIND

続いて前処理器（presolver）と制約ハンドラの前処理が実行される。linear 制約ハンドラが6つの制約を処理し、round 1で knapsack 制約にアップグレードされている。

presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds
presolved problem has 10 variables (10 bin, 0 int, 0 cont) and 6 constraints
      6 constraints of type <knapsack>

前処理の結果、変数は10個のまま（すべて0-1変数に変換）、制約は6個のまま維持され、すべて knapsack 制約としてアップグレードされた。

初期化（initSolve）

[DEBUG] Phase 2: SCIPpresolve() 完了
[DEBUG] Phase 3: initSolve() 開始 - 求解初期化・分枝限定木作成
transformed 1/1 original solutions to the transformed problem space
[DEBUG] Phase 3: initSolve() 完了 - ルートノード作成済み

前処理が完了すると、分枝限定木のルートノードが作成される。

メインループ（SCIPsolveCIP）

[DEBUG] Phase 4: SCIPsolveCIP() 開始 - 分枝限定法メインループ
[DEBUG] SCIPnodeselSelect() ノード選択中... (nodesel=<estimate>)
[DEBUG] SCIPnodeselSelect() 選択完了: node #1 (depth=0)
[DEBUG] SCIPnodeFocus() ノード活性化 (lowerbound=-100000000000000000000.0000)

3.2節で説明した SCIPsolveCIP() が実行される。ノード選択器 estimate によりノード#1（ルートノード、depth=0）が選択され、SCIPnodeFocus() でアクティベートされる。

ノード処理（solveNode）

[DEBUG] ノード 1 処理開始 (depth=0, 残りノード=0)
[DEBUG]   -> solveNode() 開始

ルートノードの処理が開始される。

propAndSolve()ループ：伝播→LP→カット生成

[DEBUG]     propAndSolve() 開始 (伝播・LP・分離ループ)
[DEBUG]         propagateDomains() 開始 (depth=0, maxrounds=1000)
[DEBUG] prop <dualfix> 実行: result=DIDNOTFIND, 境界変更=0
[DEBUG] prop <pseudoobj> 実行: result=DIDNOTFIND, 境界変更=0
[DEBUG]         propagateDomains() 完了 (rounds=1, cutoff=0)

3.2節の propAndSolve() ループが開始される。まず propagateDomains() で領域伝播が実行される。dualfix と pseudoobj 伝播器が実行されるが、この時点では境界変更は発生していない。

ノード前ヒューリスティクス（BEFORENODE）

[DEBUG]       SCIPprimalHeuristics() 開始 (timing=BEFORENODE, nheurs=61)
[DEBUG] heur <locks> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <locks> が解を発見! (obj=-6.0000)
[DEBUG] heur <oneopt> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <oneopt> が解を発見! (obj=-16.0000)

LP解決前に BEFORENODE タイミングのヒューリスティクスが実行される。locks ヒューリスティクスが目的関数値-6の解を、続いて oneopt が-16の解を発見し、上界（primal bound）が順次改善される。

LP解決

[DEBUG]       solveNodeLP() 開始 (LP緩和を解く)
[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=6, cols=10, iter=5
[DEBUG]     priceAndCutLoop() 呼び出し (fullseparation=1)

solveNodeLP() でLP緩和が解かれる。LP最適値は27.375（これが下界=dual bound）。6行10列のLPを5回のシンプレックス反復で解いている。

LPループ中のヒューリスティクス（DURINGLPLOOP）

[DEBUG]       SCIPprimalHeuristics() 開始 (timing=DURINGLPLOOP, nheurs=61)
[DEBUG] heur <simplerounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <simplerounding> が解を発見! (obj=-21.0000)
[DEBUG] heur <rounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <rounding> が解を発見! (obj=-26.0000)

LP解決後、DURINGLPLOOP タイミングでヒューリスティクスが実行される。simplerounding が-21、rounding が-26の解を発見し、上界が大幅に改善される。

カット生成（separationRoundLP）

[DEBUG]         separationRoundLP() 開始 (カット生成)
[DEBUG] sepa_gomory: Gomoryカット 10個生成 (depth=0, 最大効率=0.0779)
[DEBUG] sepa <gomory> 実行: result=SEPARATED, カット数=10
[DEBUG] sepa <aggregation> 実行: result=SEPARATED, カット数=4
[DEBUG] sepa <zerohalf> 実行: result=SEPARATED, カット数=1
[DEBUG]         separationRoundLP() 完了 (カット数=5, cutoff=0)

separationRoundLP() でカット生成が行われる。Gomoryカット、aggregationカット、zerohalfカットなど複数の分離器がカットを生成している。

伝播→LP→カット生成のループ継続

[DEBUG] LP解決: status=OPTIMAL, obj=-27.375000, rows=7, cols=10, iter=6
[DEBUG] prop <redcost> 実行: result=REDUCEDDOM, 境界変更=3

カット追加後にLPを再度解く。redcost 伝播器により3つの変数境界が縮小されている。このループは変化がなくなるまで繰り返される。

  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown

この時点で下界（dual bound）=-27.375、上界（primal bound）=-26、ギャップ=5.29%。

最適解発見とカットオフ

[DEBUG] heur <randrounding> 実行: result=FOUNDSOL, 新解=1, 最良解更新=1
[DEBUG]         ★ ヒューリスティクス <randrounding> が解を発見! (obj=-27.0000)
[DEBUG]     propAndSolve() 完了 (lpsolved=1, cutoff=1)

randrounding ヒューリスティクスが目的関数値-27の解を発見。これにより上界が-27となり、下界-27.375との差が整数目的関数では閉じられない（-27より良い整数解は存在しない）ため、カットオフが発生。

[DEBUG]   分枝判定: infeasible=0, cutoff=1, postpone=0, restart=1, unbounded=0
[DEBUG]   -> solveNode() 完了 (cutoff=1, infeasible=1)

カットオフにより、このノードでは分枝せずに処理が完了。

終了

[DEBUG] Phase 4: SCIPsolveCIP() 完了 - メインループ終了

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes      : 1
Primal Bound       : +2.70000000000000e+01 (15 solutions)
Dual Bound         : +2.70000000000000e+01
Gap                : 0.00 %

以上により最適値27の最適解が発見された。
ちなみにこの問題におけるSCIPのログは以下の通りとなり、実は冒頭で紹介したログと同一のものである。

original problem has 10 variables (0 bin, 10 int, 0 cont) and 6 constraints

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 6 upgd conss, 0 impls, 0 clqs, 0 implints
   (0.0s) probing cycle finished: starting next cycle
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present (symcode time: 0.00)
presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques, 0 implied integral variables (0 bin, 0 int, 0 cont)
presolved problem has 10 variables (10 bin, 0 int, 0 cont) and 6 constraints
      6 constraints of type <knapsack>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     0 |     - |   locks|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 6.000000e+00 | 816.67%| unknown
i 0.0s|     1 |     0 |     0 |     - |  oneopt|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 5.500000e+01 | 1.600000e+01 | 243.75%| unknown
  0.0s|     1 |     0 |     5 |     - |  1397k |   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 1.600000e+01 |  71.09%| unknown
r 0.0s|     1 |     0 |     5 |     - |simplero|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.100000e+01 |  30.36%| unknown
r 0.0s|     1 |     0 |     5 |     - |rounding|   0 |  10 |   6 |   6 |   0 |  0 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     6 |     - |  1473k |   0 |  10 |   6 |   7 |   1 |  1 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     7 |     - |  1488k |   0 |  10 |   6 |   9 |   3 |  2 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |     9 |     - |  1523k |   0 |  10 |   6 |  10 |   4 |  3 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    10 |     - |  1557k |   0 |  10 |   6 |  11 |   5 |  4 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    11 |     - |  1572k |   0 |  10 |   6 |  12 |   6 |  5 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.737500e+01 | 2.600000e+01 |   5.29%| unknown
r 0.0s|     1 |     0 |    15 |     - |randroun|   0 |  10 |   6 |  13 |   0 |  6 |   0 |   0 | 2.737500e+01 | 2.700000e+01 |   1.39%| unknown
  0.0s|     1 |     0 |    15 |     - |  1624k |   0 |  10 |   6 |  13 |   7 |  6 |   0 |   0 | 2.700000e+01 | 2.700000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes      : 1
Primal Bound       : +2.70000000000000e+01 (15 solutions)
Dual Bound         : +2.70000000000000e+01
Gap                : 0.00 %

さらに、この問題では分枝限定法の分枝は一度も発生しておらず、ヒューリスティクスとカット生成のみで1つのノードのみで最適解が見つかっている。 これはSCIPの持つヒューリスティクスや制約伝播が強力であるために探索する空間を大幅に削減できたためである。

まとめ

本記事では、SCIPのソースコードを追いながら、MIPソルバーの内部構造を解説した。
実際にデバッグログを確認することで、各フェーズがどのように動作しているかを具体的に理解できたと思う。

今後数理最適化ソルバーを利用・開発する際に、本記事の内容が役立てば幸いである。

宣伝

Jijでは各ポジションを積極的に採用しています！
現在の募集職種は、以下リンクよりご覧いただけます。
特に今回の記事でソルバーの内部に興味をお持ちいただいた方も大歓迎です！
カジュアル面談からのスタートも大歓迎ですので、お気軽にご連絡ください。

脚注

厳密には、全変数が整数の場合は整数線形計画問題であり、一部のみ整数の場合が混合整数線形計画問題と呼ばれるが、本記事では両者を総称してMIPと表記する。 ↩︎
この問題は最大化問題であるため、今までの最小化問題を前提とした説明が整合しない可能性があるため、以下のログの解説では目的関数にマイナス符号を付けて最小化問題として説明している。 ↩︎

JIJ Tech BlogPublication

はじめに

分枝限定法の説明

混合整数計画問題とLP緩和

分枝限定法の基本アルゴリズム

アルゴリズムの詳細

SCIPのアルゴリズム全体像

求解処理フロー全体像

ナイーブな分枝限定法との違い

各ステップの詳細

前処理フェーズ (SCIPpresolve())

メインループ (SCIPsolveCIP())

ノード処理 (solveNode())

衝突解析 (Conflict Analysis)

実装上の工夫

コアデータ構造

プラグインシステム

プラグインの配置

プラグイン一覧

実際にデバッグログとともに見てみる

環境構築

テスト問題

デバッグログの解説

前処理フェーズ（SCIPpresolve）

初期化（initSolve）

メインループ（SCIPsolveCIP）

ノード処理（solveNode）

propAndSolve()ループ：伝播→LP→カット生成

ノード前ヒューリスティクス（BEFORENODE）

LP解決

LPループ中のヒューリスティクス（DURINGLPLOOP）

カット生成（separationRoundLP）

伝播→LP→カット生成のループ継続

最適解発見とカットオフ

終了

まとめ

宣伝

Discussion