トップ > 数理計画用語集 > ストロング

数理計画用語集

ストロング

読み:すとろんぐ
英名:Strongness

整数計画問題における整数変数の整数条件を緩和(例えば 0-1 変数に[0,1] という上下限を与える)した場合に,得られる最適解が整数解とかけはなれておらず,目的関数の値もそれほど変化しない( integrarity gap が小さい ) ことを言う.

同一のモデルでも変数の取り方によって strongness は変化する.strong な問題として,整数条件を緩めても,解が全く変化しないという total unimodularity という性質を持つものが知られており,例えばヒッチコック輸送問題が知られている.これは単体法でこの問題解くときの基底行列の行列式の絶対値が 1 になることで示すことができる.しかし,total unimodularity は制約の追加に対して失われやすいことも知られており,例えば,ヒッチコック輸送問題は,送り手と受け手を結ぶ辺に容量の制約を付けると失われてしまう.

よく現れる問題のタイプが strong かどうかは実務家には経験的に知られている.例えば一般化割当て問題は比較的 strong な部類に属する.