puzitu — COIN-OR Branch-and-Cut ソルバー（puzitu）

Library
puzitu — COIN-OR Branch-and-Cut ソルバー（puzitu）

puzitu — COIN-OR Branch-and-Cut ソルバー（puzitu）

COIN-OR の Branch-and-Cut 法に基づく混合整数線形計画（MILP）ソルバーの C++ 実装リポジトリ。COIN-OR 財団のエコシステムに属し、LP 緩和の解法、分枝（branching）、カット生成（cutting planes）、プリソルブやヒューリスティクスといった MIP 解法の主要要素を含む。オープンソースで拡張性を持ち、最適化問題の研究・実務両面で利用・改良が可能な構成になっている。

https://github.com/shykrase/puzitu

概要

puzitu は COIN-OR にルーツを持つ Branch-and-Cut ベースの混合整数線形計画（MILP）ソルバーのリポジトリです。C++ で書かれており、LP 緩和の解法、分枝戦略、カット生成、プリソルブ、各種ヒューリスティクスなど、MIP を解くための標準的かつ発展的な機能群を備えています。COIN-OR の他コンポーネント（例：OSI、CLP など）と連携する設計が想定されており、研究目的のアルゴリズム改良や実務での最適化モデル適用に向いています。オープンソースとして管理され、ボランティアによるメンテナンスや寄付を通じて発展しているプロジェクトです。

GitHub

リポジトリの統計情報

  • スター数: 36
  • フォーク数: 0
  • ウォッチャー数: 36
  • コミット数: 30
  • ファイル数: 29
  • メインの言語: C++

主な特徴

  • Branch-and-Cut による混合整数最適化の実装（分枝・刈り込みとカット生成の統合）
  • COIN-OR エコシステムとの親和性（他ライブラリと連携する構造）
  • C++ による高性能実装で、研究用の拡張やチューニングがしやすい設計
  • オープンソース運用で貢献・拡張が可能

技術的なポイント

puzitu の技術的な中核は、Branch-and-Cut アルゴリズムを中心に据えた MIP ソルバーの構成です。Branch-and-Cut はノード探索（分枝）とカット生成（線形不等式の追加）を組み合わせることで、探索空間を効率的に狭めつつ最適解を探索します。本リポジトリはその典型的な要素 — LP 緩和の解法、プリプロセス（プリソルブ）による問題縮小、ノード選択・変数選択の分枝規則、さらにカット生成モジュールやヒューリスティクス — を C++ で実装している点がポイントです。

設計面では COIN-OR 財団の他プロジェクトとの相互運用性を重視しており、Solver Interface（OSI）や CLP などの LP ソルバーを利用するかたちで、線形緩和問題の高速な解法が活かせるようになっています。これにより、LP ソルバーの差し替えや、特定問題向けのプリソルブ戦略・カット生成ルーチンの追加といった拡張が容易です。

アルゴリズム実装においては、計算効率と柔軟性のバランスが重要です。プリソルブでは冗長不等式の除去、固定変数の検出、係数縮退の処理などで問題サイズを削減し、各分枝ノードでの LP 解法の負荷を低減します。カット生成は一般的なカット（例：ゴモリーカット、カバー/ナップサックカット、分割平面など）を想定しており、問題構造に応じたカットの組合せによって探索を加速します。ヒューリスティクスは初期の実行可能解や良好な上界（プライマル解）を得るために重要で、ラウンド手法や局所探索、簡易整数化戦略が役立ちます。

拡張性の観点では、モジュール化されたコードベースにより新しい分枝規則やカット発見アルゴリズム、評価関数の追加が比較的容易です。研究用途では新しい分枝基準の試験、カットの品質評価、問題クラス別のチューニングといった実験が行いやすい設計になっています。また、ビルドや CI の設定（.github ディレクトリなど）の存在は、継続的インテグレーションや外部寄稿を受け入れる体制づくりにも貢献します。

プロジェクトの構成

主要なファイルとディレクトリ：

  • .clang-format: file
  • .coin-or: dir
  • .gitattributes: file
  • .github: dir
  • .gitignore: file

…他 24 ファイル

まとめ

COIN-OR の設計思想を受け継ぐ C++ ベースの Branch-and-Cut ソルバーで、研究・実務双方の最適化ニーズに応える拡張性と実装基盤を備えています。

リポジトリ情報：

READMEの抜粋：

Cbc

A COIN-OR Project

Projects such as this one are maintained by a small group of volunteers under the auspices of the non-profit COIN-OR Foundation and we need your help! Please consider sponsoring our activities or volunteering to help!

[![Latest Release](https://img.shields.io/github/v/release/coin-or/Cbc?sort=semver…