In this study, we consider the robust knapsack problem introduced by Bertsimas and Sim [Operations Research 52(1) pp.35-53, 2004]. Robust cover inequalities are well-known valid inequalities for the robust knapsack problem. These inequalities can be strengthened using lifting methods that improve each coefficient of inequality by utilizing the optimal objective values of lifting problems. Since obtaining an optimal solution for every lifting problem can be time-consuming, we propose an efficient alternative lifting method using the upper bounds of the lifting problems. Through computational tests, we demonstrate that our lifting method outperforms existing methods in terms of computational efficiency, while the effectiveness of the resulting lifted robust cover inequalities remains competitive compared to those generated by existing lifting methods.

Benders Decomposition (BD) has been used to solve a variety of optimization problems. The performance of BD is strongly influenced by the choice of the cuts to be added during the course of the algorithm.

Several algorithmic approaches to make this choice are known. The so-called Magnanti-Wong method aims for Pareto-optimal Benders cuts. Cuts based on minimal infeasible subsystems of a modified version of the Benders subproblem have proven to provide strong cuts. Recently, methods using facets of the subproblem's value function's epigraph as Benders cuts have been developed.

We contribute to the field of cut selection strategies for BD by developing a new notion of Pareto-optimality, that incorporates, in contrast to the Magnanti-Wong notion of Pareto-optimality, the behavior of the cuts on the whole feasible domain of the Benders masterproblem.
We prove that cuts that are non-dominated according to our notion are non-dominated in the sense of Magnanti-Wong as well.
We provide an approach to calculate non-dominated cuts according to our notion, that solves a single linear program that has one variable and one constraint more than the standard dual Benders subproblem.

We benchmark our cut selection strategy against the other known strategies on various instances.
Some instances are taken from the MIPLib, others are multi-commodity flow network design problems, and others are randomly generated MIPs.
The computational results show, that a hybrid selection strategy consisting of minimal infeasible system cuts and our cut selection strategy is the most efficient in terms of running time. Further, the results show, that our cut selection strategy is the most efficient measured in the number of Benders cuts that are needed to solve a problem.

We consider classical graph problems in a bulk optimization setting. In a nutshell, the idea is as follows: we want solve a graph problem (e.g., perfect matching or spanning tree), but there is uncertainty on the actual edges that will be available in different scenarios. Therefore, we identify a minimum cost subset of edges such that the resulting graph contains the structure we are interested in (i.e, a perfect matching or a spanning tree), under each scenario. Although the paradigm was studied for what concerns its theoretical properties, and some approximation algorithms were proposed, we are not aware of any computational approach. Therefore, we propose a unified approach based on Benders decomposition. In this approach, the master problem encapsulates variables determining which edges to activate, while the subproblems verify the admissibility of the master solution in each scenario. The transformation of the subproblems into efficiently solvable flow problems enhances computational tractability.

The detection of targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets, each of which has unique search capabilities, in the decision theatre over the planning horizon. We develop a two-stage integer stochastic programming model designed to maximize the expected number of targets detected, considering both the stochastic nature of target movements and the probabilistic detection capabilities of the assets. Leveraging the problem structure, we develop a closed-form solution for the second stage of the stochastic program, which allows for large-scale instances of the model to be solved efficiently via Benders decomposition. We conduct computational experiments to demonstrate the efficacy of the approach.