Publishing house / Banach Center Publications / All volumes

Abstract

The problem of existence of a forecast (or planning) horizon has been considered in many special models, more or less precisely. We specify and investigate this problem for families of cheapest paths in networks with weakly ordered nodes. In a discrete network, the standard forward algorithm finds the subnetwork generated by optimal paths. The proposed forward procedure reduces subnetworks such that the forecast horizon remains unchanged. Based on the final subnetwork, we have an answer to the forecast horizon questions. In particular, we show that many questions about rationality of initial decisions become NP-hard. To improve the performance of heuristics, we introduce the notion of potentially rational initial decisions.