最適化モデルを作成するときに、スパースな定式化を意識することにより、モデリングや前処理にかかる時間やメモリ使用量を大幅に改善できる場合がある。これは、例えば、疎グラフにおいては、隣接行列でデータを持つよりも隣接リストなどでデータを持った方…

Gurobi Python APIのコードを見ていると、次のようなコードをよく見かける。 import gurobipy as gp model = gp.Model() # model.addVarで変数を作る処理を書く model.update() # model.addConstrで制約を書く model.optimize() このコード自体は問題なく動…

Gurobiで多目的最適化をする際に、それぞれの目的関数における振る舞いを制御したいときがある。今回は例として、目的関数が3つの多目的最適化について、優先度を設定して順々に最適化することを考える。 import gurobipy as gp model = gp.Model() # モデル…

Pythonでグラフの操作をしたい場合は、たいていnetworkxをインストールして使えば事足りる。(フローや最短路、最小全域木など)ただし、なぜかトポロジカルソートは以下の標準ライブラリとして使用可能である。 from graphlib import TopologicalSorter使い勝…

組合せ最適化問題について、整数計画の定式化をしていると、表現したい条件についての制約が非常に多くなってしまうことがある。このような場合には、必要な制約のみを逐次追加していく切除平面法が用いられることがある。本記事では、それをGurobiのLazy Co…

数理最適化を含むデータ分析するシステムを作る際に、いつも悩むのが入出力データの形式だ。 選択肢としては、次の3つがあるだろう。 Excelファイル CSVファイル(文字コード:UTF-8) CSVファイル(文字コード:CP932) ユーザーが扱うことをだけを考えると、最も…

線形順序付け問題は、行列が与えられたときに、置換について、目的関数 を最大化する問題として表される。もしについて、となるようなが取れる場合は、DAG上のトポロジカルソートになる。線形順序付け問題はNP困難であるため、厳密解を求めたければ、整数計…

求解に時間がかかる整数計画問題を解いているとき、暫定実行可能解を図などで確認したいことがある。 Gurobi Python APIでは、callbackを用いることで実現できるので、その方法を書いていく。 例として、ランダムに設定した0-1ナップザック問題を解いていく…

普段のコーディングや勉強の中で気づいたことなどを蓄積しておきたいと考えたので、ブログを始めることにした。 業務では、数理最適化を用いたシステムの開発を行っている。 書く内容は、数理最適化が中心だが、主に以下のトピックについて書く予定。 Gurobi…