An analytics-based decomposition approach to large-scale bilevel optimisation
University College Cork
Bilevel optimisation problems contain several decision makers, each with different objectives and constraints, arranged in a hierarchical structure. One type of bilevel problem is the single-leader, multiple-follower problem, which has been used in applications like toll-setting, resource management, conflict resolution, and many others. This hierarchical structure allows for the reformulation of the forest harvesting problem as a multiple-follower bilevel problem. In the forest harvesting problem of Chapter 4, trees are cut into different log types, some of which are more valuable than others. Due to the fact that harvesting machines are designed to prioritise the production of these higher-value log types, over-production and waste of the high-value logs, as well as unfulfilled demand for the low-value logs is seen. Additionally, the discrepancy between amounts of log types expected pre-harvest and the actual amounts seen post-harvest leads to the inefficient harvesting of the forest. Despite the many approaches for solving multiple-follower problems, they are either not applicable in cases in which the follower problems are not traditional optimisation problems, or do not scale up appropriately. An example of this case occurs with the forest harvesting problem, where the follower problems are dynamic programming problems. Another example is the case where the follower problems are black-box functions. In such cases, replacing the follower problems with reformulations or optimality conditions are not applicable. Evolutionary algorithms can be used, but these are computationally-intensive schemes which do not scale up effectively. For this reason, an analytics-based approach, which is better able to sample the solution space is needed. The thesis defended throughout this dissertation is that an analytics-based decomposition approach can be used to solve largescale multiple-follower bilevel problems more efficiently than the other approaches. Specifically, the contributions of this thesis are: (i) a new class of multiple-follower bilevel problems is proposed; (ii) a novel analytics-based decomposition approach for solving this class of large-scale bilevel multiple-follower problems is given; (iii) the forest harvesting problem is reformulated as a bilevel optimisation problem to take into the account operation of harvester, and (iv) a reactive harvesting approach is developed to mitigate the effects of the uncertainty in the data .
Bilevel optimisation , Forest harvesting , Cutting stock problem , Analytics-based decomposition
Fajemisin, A. 2018. An analytics-based decomposition approach to large-scale bilevel optimisation. PhD Thesis, University College Cork.