Estimating the hardness of optimisation
Sylvie Thiébaux, John Slaney, Philip Kilby · 2000
. Estimating computational cost is a fundamental issue in time-bounded computation. We present a method for estimating the hardness of optimisation problems (find a minimal cost solution to instance I) by observing that of the corresponding decision problems (has I a solution of cost less than threshold T ). Provided T is not too close to the optimal, decision is typically much easier than optimisation, yet knowing the hardness of the former is useful for predicting the latter. The present paper reports an experimental investigation of this idea, with encouraging results. An investment of a few percent of the work required for optimisation suffices for estimation within a small factor, even using a very simple implementation of the method. 1 INTRODUCTION Many combinatorial problems found in scheduling, network design, planning and the like have both an optimisation form (find a minimal cost solution) and a corresponding decision form (is there a solution of cost less than threshold T ...