floating-point - 線形計画精度

Question

最小化する線形問題に取り組んでいます。これは明確に定義されており、ほとんどの場合 [0;1] の範囲の数値を使用します。Excel の線形ソルバーと Mathematica の LinearProgramming は解決策を見つけますが、私の制約の 1 つにひどく違反しています。

私のソリューションが有効であるためには、制約は正確に 0 に等しい必要がありますが、両方のソルバーはそこに数値 ~10E-17 を配置し、それを満足として扱います。私は正確に操作しようとしましたが、10E-17 を下回ると、問題は線形ではないと述べられていますが、これは誤りです。自動スケーリングも役に立ちません。

コンピューターで使用される浮動小数点数の限られた精度を扱っていることは知っています。私はここで運命づけられているのか、それともこの問題を克服するためのトリックがあるのか​​ を確認したいと思います.

Answer 1

線形計画法ソルバーは、ほぼ確実に IEEE 754 64 ビット 2 進浮動小数点を使用しています。53 有効ビットに相当する値を格納します。これは、10 進数で約 15.9 桁に相当します。その表現では、正確さは不可能であり、10e-17 前後の解を見つけることは、あなたが得ようとしているのと同じくらい良いです.

最初に行うことは、通常のソルバーで得られる近似解が実際の問題に対して十分であるかどうかを確認することです。入力として使用される測定された物理量は、精度がはるかに低いことがわかっていることに注意してください。

@harold はコメントで、「一部のソルバーには、任意の有理数を使用する正確なモードがありますが、非常に遅いです。」と指摘しました。本当に正確さが必要な場合は、有理数表現のソルバーを探すことが唯一の解決策です。