割り当て問題は行列の Total Unimodularity (完全単模性) より、LP緩和を解けば整数解が求まるんだと思ってたけど、 単体法じゃなくてバリアとかで解くと、 そうでない最適解が求まる場合もあるのか。