Topic B.4: Online algorithms for optimization in the forestry and agricultural sciences

The uncertainties in forestry and agricultural applications often demand practical decisions without all the relevant data (insect infestation, annual weather conditions, market prices, etc.) being available. Online optimization (Albers, 2010) deals with how good a planning can be, given uncertainties and, in particular, without definitive basic data, and searches for optimal algorithms for this field. Algorithms that make decisions without comprehensive knowledge of all the input data, are known as online algorithms. Correspondingly, an algorithm that has all the information at its disposal from the start, is known as an offline algorithm. Competitive analysis (Borodin, El-Yaniv, 1998) established itself as a method to assess the quality of an online algorithm solution and compares the result from an online algorithm with a solution from an optimum offline algorithm.

In this topic, online algorithms are developed for planning problems resulting from information uncertainty across the production and value chains in given corporate networks, and to supply information about the solution’s quality. In addition, reasonable assumptions are made about the unknown data and the quality of the algorithms in relation to these. When formulating the online problems under review and estimating the underlying probability distributions, reference is made to the interim results and finding from the dissertations based on topic group A and, specifically, topic A.1. Topic B.2 can also provide important input. The significance of the robust optimization dealt with in topic B.3 is that, in this case, decisions have to be made in a first phase that will remain acceptable for all conceivable developments in a second phase. An online algorithm, on the other hand, processes a sequence of requests (e.g., offers from a potential client) and makes a decision (to accept or reject). The new approach of recoverable robustness (Cicerone et al., 2008) creates a conceptual interface between the two topic areas. Owing to the thematic relatedness, this topic area can be investigated regarding how far the methods developed for these uncertainty concepts can be transferred to the other topic area within the context of these studies. Conversely, the methods developed in this work can be applied as inputs for topics B.1, B.2, and B.6.

Discrete optimization methods are applied to deal with this complex of themes. First, the corresponding offline problems are formulated and investigated. Deterministic and random online algorithms are then developed, their competitivity estimated, and general conclusions drawn regarding the best possible quality of online algorithms in this environment (e.g., by means of Yao’s principle (Yao, 1977)). In addition, linear optimization methods, integer programming, network optimization, etc. are utilized to develop exact, as well as heuristic, methods and to evaluate their quality. The applicability of the developed methods is tested by means of simulation to achieve an estimation of the algorithms’ average-case behavior.