論文読み：From feasibility to improvement to proof: three phases of solving mixed-integer programs

今回は、Optimization Online とは別に、雑誌に掲載された論文をチェックしてみた。

From feasibility to improvement to proof: three phases of solving mixed-integer programs
http://www.tandfonline.com/doi/full/10.1080/10556788.2017.1392519

整数計画問題を厳密に解く時には分枝限定法が一般に用いられるが、この論文は以下のような良く見られる状況に着目している。
１．最初の実行可能解を得るまでの時間は、最適解を得るまでよりも短い
２．最適解を得るまでの時間は、その解が最適であると保証するまでの時間よりも短い

したがって、分枝限定法を３段階に分けていて、
　１．最初の実行可能解を見つけるまで
　２．最適解を見つけるまで
　３．最適解が最適であると保証できるまで
これらの３段階でどのように推移していくか、というヒューリスティクスを議論している。
数値実験を見る限り、それなりにうまく動いているヒューリスティクスのようだ。

整数計画問題を近似的に解く方法として様々なヒューリスティクスが提案されているが、このような分枝限定法のヒューリスティクスを用いて他のヒューリスティクスを改良したら面白いかもしれない。