We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between two players: the leader and the follower. There is a market that is partitioned into two parts: the part of the leader and the part of the leader’s competitors. The leader controls one part of the market and can freely set the prices for products. By contrast, the prices of the competitors' products are fixed and known in advance. The follower, then, needs to solve a combinatorial optimization problem in order to satisfy their own demands, while comparing the leader’s offers to the offers of the competitors. Therefore, the leader has to hit the intricate balance of making an attractive offer to the follower, while at the same time ensuring that their own profit is maximized. Pferschy, Nicosia, Pacifici, and Schauer considered the Stackelberg pricing game where the follower solves a knapsack problem. They raised the question whether this problem is complete for the second level of the polynomial hierarchy, i.e., Σ^p₂-complete. The same conjecture was also made by Böhnlein, Schaudt, and Schauer. In this paper, we positively settle this conjecture. Moreover, we show that this result holds actually in a much broader context: The Stackelberg pricing game is Σ^p₂-complete for over 50 underlying problems whose decision versions are NP-complete, including most classics such as TSP, vertex cover, clique, subset sum, etc. This result falls in line of recent meta-theorems about higher complexity in the polynomial hierarchy by Grüne and Wulf.

We consider the general problem of blocking all solutions of some given combinatorial problem with only few elements. For example, the problem of destroying all Hamiltonian cycles of a given graph by forbidding only few edges; or the problem of destroying all maximum cliques of a given graph by forbidding only few vertices. Problems of this kind are so fundamental that they have been studied under many different names in many different disjoint research communities already since the 90s. Depending on the context, they have been called the interdiction, most vital vertex, most vital edge, blocker, or vertex deletion problem. Despite their apparent popularity, surprisingly little is known about the computational complexity of interdiction problems in the case where the original problem is already NP-complete. In this paper, we fill that gap of knowledge by showing that a large amount of interdiction problems are even harder than NP-hard. Namely, they are complete for the second stage of Stockmeyer’s polynomial hierarchy, the complexity class Σ 2 p . Such complexity insights are important because they imply that all these problems cannot be modelled by a compact integer program (unless the unlikely conjecture NP = Σ 2 p holds). Concretely, we prove Σ 2 p -completeness of the following interdiction problems: satisfiability, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, p -center, p -median, independent set, clique, subset sum, knapsack, Hamiltonian path/cycle (directed/undirected), TSP, k -directed vertex disjoint path ( k ≥ 2), Steiner tree. We show that all of these problems share an abstract property which implies that their interdiction counterpart is Σ 2 p -complete. Thus, all of these problems are Σ 2 p -complete “for the same reason”. Our result extends a recent framework by Grüne and Wulf.

Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become Σ^p₃-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP = Σ^p₃ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, p-center, p-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, k-directed disjoint path (k ≥ 2), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes Σ^p₃-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is Σ^p₃-complete. This reveals the insight that all the above problems are Σ^p₃-complete "for the same reason". Our result extends a recent framework by Grüne and Wulf.

Rural rail transportation can contribute significantly to achieving climate goals and encountering mobility challenges, especially by reactivating currently disused railway lines.Rural areas are mainly characterised by their dispersed demands.Thus, small highly automated rail vehicles could be operated on-demand and thus service-oriented.The operation of those networks is complex and the economic efficiency must be correspondingly high.Therefore, optimised resource planning is necessary.The paper focuses on the planning of a-priori known transport requests.The paper presents a formulation for the underlying Integer Programming mathematical model that optimises travel times and number of vehicles used under consideration of railway specific constraints such as headway times and deadlock prevention.The modelling goes beyond existing Dial-a-Ride approaches and adds the necessary routing constraints for rail systems as well as energy management constraints for potential refuelling or recharging.The potential for application of the approach is evaluated in a computational study.A validation scenario shows in an exemplary manner on the one hand how the constraints affect routing on a single track railway line and on the other hand how solving the model with a black-box solver such as Gurobi is handled for this scenario.On a real-world railway line, it can be shown that the Integer Programming solver is able to induce meaningful results for limited input sizes.Further potential improvements are discussed as well.