最適解の証明は、出来ませんでした。
が、GAPは、約0.00247% となり、ほぼ最適解を得ることができました。このベンチマークが提出されたのは、十数年前になります。これは、今まで、幾多の研究者がこのベンチマークに挑んだはずですが、ここまで最適解に近接したことはありません。
LB:40438 UB:40439
Machine: Ryzen 9700X 192GB Memory RTX5070TI GPU with COPT 8.03 Barrier Solver
最適解の証明は、出来ませんでした。
が、GAPは、約0.00247% となり、ほぼ最適解を得ることができました。このベンチマークが提出されたのは、十数年前になります。これは、今まで、幾多の研究者がこのベンチマークに挑んだはずですが、ここまで最適解に近接したことはありません。
LB:40438 UB:40439
Machine: Ryzen 9700X 192GB Memory RTX5070TI GPU with COPT 8.03 Barrier Solver
2026SAT competition2026結果をよく見ると、大きく向上していることが分かります。特にUNSATの伸びは、近年では一番と言ってよいのではないでしょうか?この秘密を探りました。
satsumaとは?
CNF式の「対称性」を検出して壊す、独立した前処理ツールです(Markus Anders (RPTU Kaiserslautern-Landau) と Cayden Codel (CMU) 開発、SAT 2024で発表・SAT'26 Best Paper受賞)。
入力/出力: DIMACS CNF → 等充足(equisatisfiable)な、対称性を壊したCNFを出力するだけ。ソルバーには一切依存しない、パイプラインの前段に挟むだけのツールです
仕組み: dejavuというグラフ同型判定ソルバーを使い、CNFを(変数・節の関係を表す)グラフとして扱って自動的にグラフ同型群(=論理式の対称性)を検出。そのうえで対称な解を除外する制約を追加します
2つのモード:
satsuma fix — 検出した対称性を使って変数を直接固定・消去(場合によっては変数自体を消せる)
satsuma lex — 「辞書順で最小の解だけを許す」制約(lex-leader constraint)を追加
大会結果に出てきた satsuma-iter+kissat(優勝)・satsuma-lex+kissat はこの手法の異なる設定と見られます(iterは対称性検出→固定を繰り返し適用する版と推測されますが、READMEには明記が薄く未検証です)
使い方: satsuma fix formula.cnf > output.cnf としてCNFを加工し、その結果を好きなソルバー(例: kissat output.cnf)に渡すだけ。ソルバー本体には一切手を入れません
なぜ効くのか(前回の回答の補足)
多くの実問題(ハードウェア検証、組合せ問題など)のCNFには「変数を入れ替えても論理的に同じ」という対称性が大量に潜んでいます。CDCLソルバーは対称な解候補を何度も別々に探索してしまいがちで、これを事前に1つの代表解だけに絞ることで探索空間そのものを縮小できます。これがkissatのコア(CDCL探索)を一切変えずに +38問(238→276、前回表参照)もの差を生んだ理由です。
解互換性について
いいえ、単純にはそのまま互換ではありません。「SAT/UNSATの判定結果(充足可能かどうか)」は保証されますが、「見つかった解(モデル)」がそのまま使えるかはモード次第です。
SAT/UNSAT判定: 常に保証(equisatisfiable)
satsumaが返すのは常に元のCNFと等充足(equisatisfiable)な式です。つまり「SATかUNSATか」という結果自体は変換前後で完全に一致します。UNSATの場合はさらに証明(fixモードはSR/バイナリSR形式が安定版、VeriPBは実験段階。lexモードはVeriPBのみ)を出力でき、これをkissat自身が出す証明と繋いで大会が要求する完全な証明チェーンを作れます。
モデル(具体的な変数割り当て)の互換性: モードで挙動が違う
satsuma fix(変数を固定・消去するモード): 公式ドキュメントに明記されている通り、「対称性を利用して変数そのものを式から取り除くことがある」ため、縮小後の式で見つかった充足割り当ては、元の式の全変数に対する割り当てにはなっていない場合がある、と明言されています。
デフォルトではモデルの互換性は保証されません。互換性が欲しい場合は --add-reduced-as-unit オプションを付ける必要があります(「これを付ければ縮小後の式のどんな充足割り当ても、元の式の妥当な充足割り当てになる」との記載)
このオプションなしだと、消去された変数の値を復元する「reconstruction/witness」的な後処理が別途必要になりますが、そこを自動でやってくれる仕組みはドキュメント上見当たりませんでした
satsuma lex(辞書順最小解に絞る制約を追加するモード): こちらは新しい制約(節)を追加するだけで、変数自体は消していないと読めます。追加された制約は「元の解集合の部分集合だけを許す」ものなので、見つかった解はそのまま元のCNFの妥当な解になるはずです(ただしREADMEに「新規変数を一切導入しない」と明示的に断言されているわけではなく、そこは断定できません)
kissat-cppへの実装インパクト
SAT/UNSATの判定結果だけ欲しいなら、どちらのモードでも問題なく使えます
solver.value(lit) で実際の変数割り当て(モデル)を取りたいなら、
lex モードを使うか、
fix モードなら --add-reduced-as-unit を付けて使う
のどちらかが安全です。付けずに fix を使うと、kissatxxの units()/value() で返ってくる値が元の変数番号と食い違う(あるいは一部の変数が消えていて値を取れない)可能性があります
Sources: markusa4/satsuma (GitHub), satsuma: Structure-based Symmetry Breaking in SAT (arXiv)
fixとlexでは、どちらが解きやすいと考えられますか?
閲覧済み ウェブ
実際の大会データと理論的な違いの両面から見ると、fix(特にその発展形であるiter)の方が明確に「解きやすい式」を作ります。
大会での実測(前回計算したCSVより)
構成 解けた数/400 PAR-2
satsuma-iter+kissat(優勝、Anders/Codel) 276 3647.02
satsuma-lex+kissat(Oertelチーム) 249 4279.58
kissat単体(前処理なし) 238 4611.54
iterはkissat単体比+38問(+16%)、lexは+11問(+4.6%)。同じkissatバックエンドで、iterはlexの3倍以上の伸びしろを引き出しています。
なぜ差が出るのか(手法上の理由)
fix系(iterもこの系統): 検出した対称性を使って変数そのものを固定・消去します。つまり式を物理的に縮小してからソルバーに渡す。しかもiterの元になっている2026年の新論文 "Simplify, Order, Break, Repeat" によれば、対称性破壊を「単なる探索空間の制限」ではなく「簡約化(simplification)手段」と位置づけ、unit/binary節だけを追加する軽い変換に留めることで、その簡約が新たな対称性を露出させ、さらにもう一段対称性を壊せる——というのを繰り返す(Repeat)設計です。この論文はCaDiCaLの前処理としてPAR-2を2025年大会で22%、Anniversary trackで12%改善したと報告しており、fix系アプローチの優位性は他の実験でも裏付けられています
lex: 変数は一切消さず、「対称性のある解のうち辞書順最小のものだけ許す」という制約(lex-leader constraint)を追加するだけです。式は縮小されず、むしろ制約節が増える分だけ形式的には大きくなります。対称群が大きいとlex-leader制約自体が長大・複雑になりやすいことも知られており、追加した制約の処理コストが枝刈り効果を目減りさせがちです
トレードオフも存在する
ただし前回お伝えした通り、fixは変数を消してしまうぶんモデル(具体的な解の値)をそのまま元の式に使えない場合がある(--add-reduced-as-unitか別途reconstructionが必要)のに対し、lexは変数を消さないのでモデルの互換性は素直に保たれます。
→ 「解けるかどうか・どれだけ速く解けるか」だけを重視するならfix/iterが有利、「モデルをそのまま使いたい/実装をシンプルに保ちたい」ならlexが安全、という住み分けです。kissat-cppに組み込むなら、SAT/UNSAT判定だけでなくsolver.value()で解の中身も使う設計なので、fixを使うなら--add-reduced-as-unit必須、という前回の結論と合わせて検討する必要があります。
Sources: Simplify, Order, Break, Repeat (SAT 2026), satsuma: Structure-based Symmetry Breaking in SAT (arXiv), markusa4/satsuma (GitHub), SAT Competition 2026 raw scores
C#用のSDKが整備されたようなので、MCPの開発をPythonから、C#に変更することにしました。
結論から言うと、「C# GUIのMCPサーバー」を作る目的によって、Pythonを使うのが正解(メリットあり)か、それともC#で統一すべき(不正解に近い)かが明確に分かれます。
stdio や EventSource を使用)であるため、PythonでMCPサーバーを作ること自体は技術的に全く問題ありません。しかし、「C#で構築された既存のGUIアプリ」とどう連携させるかによって、最適な開発言語が変わります。 [1, 2]| パターン | システムの構成の流れ | 評価とアドバイス |
|---|---|---|
| パターンA (C#が主役) | AIアプリ(Cursor等) ⇄ (MCP) ⇄ C# GUIアプリ(内部にMCPサーバーを内蔵) | C#で統一するのが正解です。GUIアプリの内部状態をAIに直接見せたり操作させたりできます。Pythonを挟む必要はありません。 |
| パターンB (Pythonが主役) | C# GUIアプリ(MCPクライアント) ⇄ (MCP) ⇄ Python(MCPサーバー) | Pythonを使うのが正解です。C#で作った独自のAIツールから、背後にあるPythonの高度なAI/データ処理ロジックを呼び出す形になります。 |
stdio)を介したプロセス間通信、またはローカルHTTPサーバー(SSE)を介して行われます。stdio)での接続を基本としています。それぞれの通信メカニズムの詳細は以下の通りです。.exe)」をバックグラウンドで起動し、パイプライン(標準入力と標準出力)を繋いで通信する方式です。[ AIアプリ (Client) ]
│ (1) .exe を起動(プロセス生成)
▼
┌──────────────────────────────────────┐
│ [ C# GUIアプリ (Server) ] │
│ │
│ AIアプリの標準出力 ──> 独自の標準入力 │ ※ JSON-RPC 2.0
│ AIアプリの標準入力 <── 独自の標準出力 │ フォーマットのデータ
└──────────────────────────────────────┘
mcpConfig.json など)に従い、C#アプリの .exe パスを指定して起動します。Console.In(標準入力)へ流し込みます。Console.Out(標準出力)へ書き戻します。localhost)を立ち上げ、Web技術をベースに双方向のやり取りを行う方式です。[ AIアプリ (Client) ] ──(HTTP Post / Request)──> [ C# GUIアプリ (Server) ]
[ AIアプリ (Client) ] <───(SSE / Stream)─────── [ 内部でWebサーバーが起動 ]
localhost:5000 などの一時的なローカルWebサーバーを起動します。SSE (Server-Sent Events) という技術を使ってデータを流し続けます。stdio)方式を採用する場合、C#のGUIアプリ(WPFやWinForms)で1点だけ注意が必要です。Console.WriteLine などの標準入出力が正常に機能しない、あるいはAIアプリ側と正しくパイプが繋がらない原因になります。.csproj)を一時的にコンソールアプリケーション(<OutputType>Exe</OutputType>)として作成し、コード側でGUI(Applicationクラスなど)をスレッド起動する構成にするのが一般的です。modelcontextprotocol/csharp-sdk)をNuGetで導入するだけで、AIアプリとC#アプリが1対1で直接おしゃべりできるようになります。[ AIアプリ ] ──(通信①)──> [ Python MCP ] ──(通信②: ここが地獄)──> [ C# Storeアプリ ]
結果を見ると、AI tuneされたソルバLymphosatが、SAT問題において、異常に高性能であることが目につきます。一体何が起きたの?と思い論文をあたってみましたが、それらしい論文は報告されていませんでした。
ソースをダウンロードして、readmeを見てみると、
LymphoSAT は、126 個の専門特化ソルバーと、未知の問題に対する汎用フォールバックソルバーから構成されるモジュール型 SAT ソルバーである。
すべての特化ソルバーは完全にゼロから構築されており、それぞれが特定の問題族に合わせてデータ構造と解法戦略を最適化している。
フォールバックソルバーは kissat-public(2025 SAT Competition に出場)をベースとしているが、DRAT の代わりに擬似ブール証明を出力するよう改造されており、さらに若干高速に動作するよう調整されている(アルゴリズム自体はほぼ変更されていない)。
となっています。
AI Tuneに関する議論をがなされたようです。今まで人間も生成AIほど精緻でなくとも、似たようなアプローチは行っていたわけで(あるインスタンスには全く効かないが、別分野では、すごく効くヒューリスティック等)、必ずしもAI Tuneを責めるわけには行かない、ということのようです。
昨今のAI Tune結果が人間ソルバを凌駕していたのも、実は、この結果である可能性が高い、ということではないでしょうか?
Autonomous Code Evolution Meets NP-Completeness
NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks
同じインスタンスは使用しない(過去問は使用不可)、等の対策を取らないと競技会自体の存在意義問題になる可能性があると思います。議論中、
ファミリー特化は正当だが、インスタンス特化は不正
がエッセンスになろうか、と思います。
いずれにせよ、我々ユーザにとって、自分の問題は常にUniqueなインスタンスなのですから、自分にとっての最適ソルバが優勝するような仕組みになってほしい、ということでしょう.
LLM で生成されたソルバーは、過去のインスタンスから得た構造的知識を内部に保持する。
これは人間研究者が過去のベンチマークから洞察を蓄積するのと同じで、本質的に問題ではない。
生成AIやデータ駆動型ヒューリスティクスでは自然に起こる挙動。
過去のデータを覚えていること自体よりも、訓練データにない構造へどこまで一般化できるかが重要。
AI生成ソルバーは、特定ファミリーに特化した前処理やヒューリスティクスを自動生成できるため、 → “構造の学習” と “単なる暗記” の境界が曖昧になる。
実際には困難。
SATベンチマークは自然にファミリー化しており、類似構造を排除すると現実性が失われる。
また、正当な専門化(例:暗号系、回路系、計画問題向け前処理)まで制限してしまう。
人間研究者もポートフォリオソルバーもファミリー認識を行っている。
LLM生成ソルバーが同じことをするのは自然な進化。
ファミリー特化は不正ではなく、むしろSATソルバーの歴史的流れに沿っている。
公開データに存在しない「ホールドアウトファミリー」を用意する。
新規生成された構造(合成ベンチマーク)でテストする。
毎年新しい分布を追加し、過学習を検出する。
ML分野のベンチマーク設計に近いアプローチ。
結論は以下の通り:
問題ではない:構造的特徴を学習し、適切な前処理やヒューリスティクスを適用する場合。
問題になる:特定インスタンスの解やバックボーンを“丸暗記”している場合。
避けられない:AI生成ソルバーが主流になるほど、ファミリー特化は標準的手法になる。
むしろ有益:メタ学習・自動アルゴリズム設計・ポートフォリオ最適化が進む。
LLM生成ソルバーがインスタンスファミリーを認識し、特化した前処理を行うのは自然な進化であり、必ずしも不公平ではない。
本質的な課題は「暗記」ではなく「汎化性能の測定」。
汎化を評価するためには、ホールドアウトファミリーや新規生成インスタンスを導入するなど、ベンチマーク設計のアップデートが必要。
ファミリー特化はSAT研究の歴史的流れに沿っており、AI時代には標準的なアプローチになる可能性が高い。
はい、その理解でほぼ正確です。 そして、この点こそ AI生成ソルバー時代のSAT競技で最もセンシティブな論点 になります。
特定インスタンスの解やバックボーンを丸暗記しているだけなのに、 あたかも「強いソルバー」に見えてしまう可能性がある。
これは SAT Competition の「汎化性能を評価する」という理念と衝突します。
ソルバーが特定の DIMACS ファイルを覚えているだけなら、 → 未知のインスタンスでは全く役に立たない
しかし競技では「既知のベンチマーク」が多いため、 → 丸暗記でも高スコアが出てしまう → 実力と評価が乖離する
LLM は訓練データのパターンを内部に保持するため、
特定の構造
特定の変数名
特定の制約の並び などを覚えてしまうことがある。
これは人間の「暗記」と違い、 規模が大きく、検出が困難 という特徴がある。
ここが重要な区別です:
例:このファイルは変数 x123 が True で始まる
例:この CNF の backbone を丸ごと記憶 → これは競技の精神に反する
例:暗号系は XOR が多い
例:回路系はゲート構造が階層的
例:計画問題は制約グラフが疎 → これは人間研究者もやっている正当な専門化
AI生成ソルバーはこの境界が曖昧になりやすいため、 「丸暗記による能力の見せかけ」をどう防ぐかが競技の課題 になります。
丸暗記を検出する方法がない
LLM は構造学習と暗記を同時に行うため境界が曖昧
ファミリー特化は正当だが、インスタンス特化は不正
新しいベンチマーク設計(ホールドアウト)が必要
つまり、
AI生成ソルバーの時代には、従来の「ベンチマークを解かせるだけの評価方法」が限界に近づいている。
はい、特定インスタンスの答えを丸暗記して高性能に見せかける危険性がある。 だからこそ「汎化性能の評価」が今後のSAT競技の最大のテーマになる。
Copt8.03Barrier. Ryzen5950X RTX4060TIGPUです。
マシンを最新CPU/GPUにすれば、1日内も可能と思われます。このインスタンスついては、既にKnownResultが存在し世界記録更新ではない、ので学術的価値はありません。が、菅原システムズ内においては、記録更新なので大きな一歩です。
にしても、一つのインスタンスの記録更新を果たすのに5年もかかってしまいました。
とりあえず、Pro版を導入してみました。
技術内容を相談していますが、ChatGPTのような忖度はなく、クールな印象です。今のところ瑕疵は、発見していません。
現在のC++ソース課題として、
1)Highsソース最新の取り込み
2)Highs IIS機能の実装
3)整数Branchの一般化
4)一般インスタンスへの展開(シフトのみ)
5)MCPインタフェースの実装
があります。そのあとにRefactoring作業が必要になります。C++ソースとして、現在数十万行になっていますが、実験コード等が散在してために整理が必要です。人に見て頂くための作業が必要です。最上位プランを使ったとしても、一気にRefactoringは出来ないと思いますが、つい1年前なら、1年以上かかると思っていた作業が、上記を使えば、そんなにはかからないだろう、という気になってきました。日本語Document生成も可能です。これもいちいちコメントタグを書く必要もなくなりました。