Bounded variation in multi-stage optimization
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
This thesis studies the computational complexity of a multi-stage optimization problem with either penalized or bounded variation.
The input of the problem is a sequence of instances (one for each time stage), and the task is to find a sequence of solutions (one for each time stage) that achieves a tradeoff between the quality of the solutions in each time stage and their similarity.
The amount of change in the sequence of solutions is quantified by the so-called variation which will be measured time-wise, component-wise, or in total.
The variation of the solution sequence is either incorporated into the model by a penalty term or by imposing a hard upper bound in the set of constraints.
This gives rise to two related but not equivalent multi-stage problems.
When only one binary decision can be made in each stage, the tractability of the problems with either of the three types of variation will be settled by presenting respective compact extended LP-reformulations.
A thorough polyhedral study of the problem versions will yield complete, and usually exponentially large, descriptions of the convex hull of feasible solutions in the original variable space and also corresponding efficient separation algorithms.
For a higher-dimensional underlying combinatorial problem, the complexity of the problem versions will turn out to depend on the type of variation and also on whether this is penalized or bounded.
Indeed, even for an underlying problem as trivial as a selection problem, one version will be strongly NP-hard, while others will be tractable.
An oracle-based approach will shift the perspective from a complexity-theoretical one to a rather information-related one in order to investigate the relative complexity of the bounded and penalized problem version with respect to the underlying combinatorial problem.
Description
Table of contents
Keywords
Bounded variation, Computational complexity, Combinatorial optimization