VCのLP緩和がHalfIntである証明
https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf
LP緩和の解はシンプレックスの端点であり、シンプレックスの端点は、「異なる2つの実行可能解の合成でかけないこと」と同値。
non-halfintがあったとすると、その解をεだけ上下にずらしたものも解になることを示し、矛盾を導く。
https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf
LP緩和の解はシンプレックスの端点であり、シンプレックスの端点は、「異なる2つの実行可能解の合成でかけないこと」と同値。
non-halfintがあったとすると、その解をεだけ上下にずらしたものも解になることを示し、矛盾を導く。