サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

最適化

Benders DecompositionのGurobipy実装例

Benders Decomposition(ベンダー分解)は問題を二つのmain, sub問題に分割することで問題を解きやすくするテクニックです。次のような性質がある問題に有効です。Kohji Nishimuraさんの「双対変数を直感的に理解したい」から引用しています。 決定変数にyが一…

GUROBIのログについて

Gurobiのログに出てくる項目について。 Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time Nodes: 解探索の過程で考慮されたノード数。これは分枝限定法で生成される。 Expl: 既に探索…

SCIP version 8.0.3 コンパイル + おまけでpulpから実行

SCIP: https://www.scipopt.org/は言わずと知れたLP、MIPソルバ。 このプロジェクトにはfscip: https://ug.zib.de/も同封されています。これはSCIPのスレッド並列版ソルバです。 Environment Ubuntu 18.04.2 LTS Build unzip scipoptsuite-8.0.3.zip cd scip…

サーベイ: Topoopt: Co-optimizing network topology and parallelization strategy for distributed training jobs (2022)

Wang, Weiyang, et al. "Topoopt: Co-optimizing network topology and parallelization strategy for distributed training jobs." arXiv preprint arXiv:2202.00433 (2022). [paper] 概要 どんなもの? Metaにおける分散DNNトレーニングジョブの解析 それを…

flopt 仕様 v0.5.5: Solverサイド

本稿ではfloptのSolverサイドであるソルバの話をします。 floptでは内部で実装されたアルゴリズムと外部ライブラリのソルバを用いて最適化を実行することができます。 Solver実装のキホン 解の登録 コールバック関数の実行 時間制限の確認 終了ステータス 問…

flopt 仕様 v0.5.5: Systemサイド -- 問題解析とソルバ選択

本稿ではfloptのSystemサイドである問題(Problem)の解析やソルバ選択について記載します。 問題解析とは? 本稿では問題解析をユーザーが定義した問題がどのタイプの最適化問題に属するのかを機械的に判断すること、とします。floptでは柔軟なモデリングによ…

flopt 仕様 v0.5.5: Userサイド -- モデリング

本稿ではfloptにおける柔軟で強力なモデリングを支える基盤である変数と式の設計を紹介します。 変数 (Variable) 式 (Expression) Expression 式の文字列表現とその恩恵 単項式と多項式クラス CustomExpression Sum, Prod 演算のオーバーライド まとめ 関連…

flopt 仕様 v0.5.5: 全体構成

これから数回にわたってfloptという私が開発している最適化モデリングツールの構成について紹介したいと思います。具体的な使い方というよりは、その仕様について記録を残すのがメインです。 具体的な使用方法やチュートリアルはこちら。 本稿ではfloptの構…

最適化モデリングツール flopt を試してみる

Qiitaに記事を投稿しました。 Dev Community Medium 本稿では、最適化モデリングツールfloptの基本的な使い方やいくつかの機能の具体例を紹介します。(私も開発者の一人です) 最適化モデリングツールとは、ユーザーが解きたい問題を表現、具現化する作業をサ…