子問題に連続変数が現れる問題における列生成法的アプローチ - Insight Edge Tech Blog

子問題に連続変数が現れる問題における列生成法的アプローチ - Insight Edge Tech Blog

$\def\R{{\mathbb R}}$ $\def\N{{\mathbb N}}$ $\def\B{\{0, 1\}}$ Insight Edgeのデータサイエンティス...概要を表示 $\def\R{{\mathbb R}}$ $\def\N{{\mathbb N}}$ $\def\B{\{0, 1\}}$ Insight Edgeのデータサイエンティストのki_ieです。今日は最近勉強した数理最適化関連の技術を紹介します。 はじめに 本記事では、混合整数計画(MIP)問題に対する列生成法の発展的な使い方を紹介します。列生成法は巨大な線形計画(LP)問題を解くための厳密解法です。列生成法の有名な応用先として、多数の子問題と少数の子問題をまたぐ制約とに分解できるMIP問題のヒューリスティック解法があります。本記事では、このヒューリスティック解法を典型的なユースケースから少し拡張して利用する(具体的には、子問題に連続変数が登場するような場合でも利用できるように拡張する)方法を考えます。 本記事の構成は以下の通りです。 列生成法 : 列生成法について簡単に説明します。 列生成