Rolling mill reheating furnaces are widely used in large-scale iron and steel plants, the efficient operation of which has been hampered by the complexity of the combustion mechanism. In this paper, a soft-sensing method is developed for modeling and predicting combustion efficiency since it cannot be measured directly. Statistical methods are utilized to ascertain the significance of the proposed derived variables for the combustion efficiency modeling. By employing the nonnegative garrote variable selection procedure, an adaptive scheme for combustion efficiency modeling and adjustment is proposed and virtually implemented on a rolling mill reheating furnace. The results show that significant energy saving can be achieved when the furnace is operated with the proposed model-based optimization strategy.