【数理最適化】python scipy.linprogを用いた数理最適化問題の演算結果のずれを修正したい

Question

前提・実現したいこと

以下の数理最適化問題をscipy.linprogを使って解いた結果が手計算と一致しない理由と解決策を知りたい

ここに質問の内容を詳しく書いてください。
①
Minimize -3x-4y
Subject to x + 4y ≦ 1700
2x + 3y ≦ 1400
2x + y ≦ 1000
x ≧ 0
y ≧ 0

②
import numpy as np
from scipy import optimize

c = np.array([-3, -4], dtype=np.float64)
G = np.array([[1, 4], [2, 3], [2, 1]], dtype=np.float64)
h = np.array([1700, 1400, 1000], np.float64)
sol = optimize.linprog(c, A_ub=G, b_ub=h, bounds=(0, None))

print(sol.x)
print(sol.fun)

③
[399.99988463 199.99996114]
-1999.9994984688583

発生している問題・エラーメッセージ

①の数理最適化問題を解くために②のコードを実行したところ結果が③となりました。
手計算で行うとx=400,y=200のとき最小値-2000となるのですが
なぜ手計算とコードの演算結果がずれるのかがわかりません。

試したこと

「linprog 少数　ずれ」　など検索は試しました。

補足情報（FW/ツールのバージョンなど）

jupyter notebook使用、python3以降です。

よろしくお願い申し上げます。

Answer 1

解決済みですが、少し気になって調べたので結果を共有しておきます。

昔のscipyではscipy.optimize.linprogは基本的にsimplexというmethodで動いていました（というかそれしかありませんでした）。割と最近（1.3.0ですから一年弱前ですね）、デフォルトのmethodがinterior-pointに変わりました。

SciPy 1.3.0 Release Notes — SciPy v1.4.1 Reference Guide

method="simplex"というオプションを指定すれば[400. 200.],-2000.0が結果として得られます。どうしてこうなるのかは詳しくないので解説できません。微妙な実装の相違の問題かもしれません。ただ、参考書の著者が1.3より古いバージョンで実行していたのであれば、本の結果がこちらになっていることは自然です。

Comments

[togo_mentor]

コメントいただきありがとうございます。

メソッドの違いが原因として考えられそうということですね。
そもそも関数がどのようなメソッドで動いているのかという視点さえありませんでした。
参考にした本の初版が2018年9月なのでもしかすると古いメソッドで動かした時のままの演算結果が記載されていたのかもしれません。

大変参考になりました。ありがとうございます。

Answer 2

なぜ手計算とコードの演算結果がずれるのかがわかりません。

linprog() の中身がどのようなアルゴリズムなのか確認する必要がありますが、反復法のアルゴリズムを使っているのだとしたら、近似解になるので、厳密解に近い値になっても完全に一致することはないでしょう。
また、そうでなくとも、浮動小数点演算では丸め誤差は必ず発生するので、多少のずれは生じます。

丸め誤差は防ぎようがない話なので、厳密に x=400,y=200、-2000 を出力するというのは数値計算を行う以上、無理です。

Comments

[togo_mentor]

回答いただきありがとうございます。

浮動小数点数の誤差なんですね。
参考書のコードそのままなのですが、参考書では正しく整数で回答が出ておりましたので
疑問に感じておりました。

技術書の回答が数値計算の誤差を正しく反映していないということは十分ありうると考えてよいでしょうか？

[tiitoi]

整数に丸めた結果が書かれていたのではないでしょうか。
sol をそのまま出力してその値になるというはありえないと思います。

print(sol.x.round())
print(sol.fun.round())
# [400. 200.]
# -2000.0

[togo_mentor]

返信ありがとうございます。
コードが書かれていてその下に
「実行結果」として整数の計算結果が書かれておりました。

実行結果
[400. 200.]
-2000.0

[tiitoi]

自分の環境で実行しても質問欄に記載の値とまったく同じものが出てきました。
[399.99988463 199.99996114]
-1999.9994984688583

書籍の作者がどのような環境で実行したのかわからないですが、「丸めた結果を書いたけどそのことについて注釈がない」もしくは「表示する際に自動的に丸められた」などの要因が考えられますが、それは作者にしかわかりません。
少なくとも質問者さんが実行した結果、以下のように出てきたというのは何も間違っておらず、こうなるのが自然です。
[399.99988463 199.99996114]
-1999.9994984688583

[tiitoi]

なので、この件は気にせずに先に進んで大丈夫だと思いますよ

[togo_mentor]

実行いただきありがとうございます。

なるほど、そうなんですね。ありがとうございます。
今後浮動小数点数の誤差で不安があればround()を使用するなどして
対処いたします。

この度はありがとうございました！