Resource Management and Online Optimization
(Topic B.4)

– Right now, I have to make a decision about my resources. I try to optimize conflicting objectives. And to cap it all, I don't know about the situation tomorrow. –

The current research in the area of combinatorial optimization takes a great interest in the consideration of uncertainties in optimization problems. Especially, problems in the area of renewable resources require decisions made without full knowledge of all relevant data. The research area of online optimization is concerned with problems with uncertain input data and the development of online algorithms which make decisions without full knowledge of all data. Furthermore, these algorithms are analyzed with respect to their quality compared to the optimal solution based on the full knowledge of all data.

In the course of this dissertation, a certain class of online problems which are applicable to resource allocation problems is investigated. Consider for example a timber dealer facing the problem to allocate his current timber stock to potential buyers in order to maximize his profit. The trouble is that the timber dealer has no knowledge about future demands, and, additionally, changes in the timber stock due to new deliveries have to be taken into account. What are possible decision strategies for the timber dealer? How good are these strategies? The quality of an algorithm is measured by the concept of competitive analysis, which compares the solution of an algorithm to the optimal solution in case all future information is known in advance. The solution of an algorithm for the problem of the timber dealer is thus compared to the optimal solution in case the timber dealer would be aware of all future demand and all future deliveries. Within the concept of competitive analysis, this relation is computed for all possible sequences. Therefore, this is a worst-case analysis.

The interdisciplinary collaboration and exchange with the areas of economic sciences, forest science, and agricultural science serve as a profound basis for the motivation of structural assumptions for the uncertain data and foster the application of theoretical results to real world cases.

Furthermore, if the timber dealer does not only want to maximize his profit but also wants to sell his resources to demanders that act in a sustainable way, for example with respect to cascade utilization of the resource, the timber dealer faces a multi-objective problem. Therefore, the concept of classic single-objective online optimization is extended to multi-objective online optimization and a general framework for these types of problems is proposed.