ストロング#

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

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

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

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