We present the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem, a new variant of the well-known Vehicle Routing Problem. It is a real-world problem originating from the policies of a Nordic distribution company. The problem includes a single depot, a non-predetermined hierarchy of intermediate facilities, and two different fleets, consisting of homogeneous depot and homogeneous local vehicles, which are pulling swap-bodies. Depot vehicles with attached swap bodies depart from the central depot. They can either visit customers directly if only one swap-body is attached or visit one or two consecutive switch points in order to transfer one or two loaded swap-bodies to a corresponding number of local vehicles, which are subsequently routed to customers while the depot vehicle itself proceeds to serve customers with the remaining loaded swap-body. Two column generation formulations of the problem are proposed and evaluated, both with respect to their respective bounding quality and best found feasible solutions. The main focus is on the excellent lower bounding quality from the column generation models. As a bonus, we find good integer solutions.

Despite their widespread applications, bilevel problems are known to be challenging to solve in practice, as even in the linear case bilevel problems are strongly NP-hard. However, unboundedness in these problems is often overlooked, with research typically assuming boundedness of their feasible sets. This presentation addresses this gap by exploring unboundedness in linear bilevel optimization and its computational complexity. We introduce the notion of direction of unboundedness to linear bilevel programs, and show that determining unboundedness in the case without upper-level constraints is in NP. Additionally, we prove that the decision problem of knowing whether a linear bilevel program with linking upper-level constraints is unbounded is NP-hard.

Bilevel optimization is an important mathematical tool to model phenomena in many domains, such as economic game theory, decision science, and machine learning, to name but a few. Despite its importance, efficient and scalable algorithms for bilevel optimization are mostly developed for the (strong) convexity of the lower-level problem case, which is unrealistic for many practical tasks. In the quest to understand more general bilevel problems, we relax the lower level strong convexity and consider polynomial bilevel optimization, i.e., polynomial objective functions and constraints. We focus on the worst-case analysis of this class of problems, from both geometric and computational viewpoints. Our analysis suggests that even the algebraic rigidity of polynomials does not exclude extreme pathologies induced by the bilevel optimization. More specifically, we demonstrate that any semi-algebraic function can be represented as the objective of a polynomial bilevel problem. This discovery implies that solving polynomial bilevel optimization is equivalent to optimizing general semi-algebraic functions. We obtain other sharp variations of this result by considering relevant properties of the lower problem, such as convexity or feasible set compacity. In addition, we show the $\Sigma_2^p$-hardness of polynomial bilevel optimization, characterizing polynomial bilevel problems as vastly more challenging than NP-complete problems (under reasonable hardness assumptions).