STOCHASTIC OFFLINE PROGRAMMING
We propose a framework which we call stochastic off-line programming (SOP). The idea is to embed the development of combinatorial algorithms in an off-line learning environment which helps the developer choose heuristic advisors that guide the search for satisfying or optimal solutions. In particular,we consider the case where the developer has several heuristic advisors available. Rather than selecting a single heuristic,we propose that one of the heuristics is chosen randomly whenever the heuristic guidance is sought. The task of the SOP is to learn favorable instance-specific distributions of the heuristic advisors in order to boost the average-case performance of the resulting combinatorial algorithm. Applying this methodology to a typical optimization problem,we show that substantial improvements can infact be achieved when we perform learning in an instances specific manner.
off-line learning pameter tuning combinatorialoptimization