We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which components to probe subject to a probing budget in a first decision stage. Then, the uncertainty realizes, and the planner observes the disruption status of the probed components, after which the planner solves the combinatorial problem in the second stage. In contrast to standard two-stage stochastic optimization, the planner does not have access to the full uncertainty realization in the second stage. Consequently, the planner cannot directly optimize the second-stage objective function, which is given by the actual cost after disruptions, and the decisions have to be made based on an estimate of the cost. By assuming that the estimate is given by the conditional expected cost given the information revealed by probing, we reformulate the probing optimization problem as a bilevel problem with multiple followers and propose an exact algorithm based on a value function reformulation and three heuristic algorithms. We derive theoretical results that bound the value of information and the price of not having full information and a bound on the required probing budget that attains the same performance as full information. Our extensive computational experiments suggest that probing a fraction of the components is sufficient to yield large improvements in the optimal value, that our exact algorithm is competitive for small- to medium-scale instances, and that the proposed heuristics find high-quality solutions in large-scale instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0236] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI 2145553]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0629 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0629 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract The analysis of social and biological networks often involves modeling clusters of interest as cliques or their graph‐theoretic generalizations. The ‐club model, which relaxes the requirement of pairwise adjacency in a clique to length‐bounded paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules or complexes in biological networks. However, if the graphs are time‐varying, or if they change under different conditions, we may be interested in clusters that preserve their property over time or under changes in conditions. To model such clusters that are conserved in a collection of graphs, we consider a cross‐graph ‐club model, a subset of nodes that forms a ‐club in every graph in the collection. In this article, we consider the canonical optimization problem of finding a cross‐graph ‐club of maximum cardinality in a graph collection. We develop integer programming approaches to solve this problem. Specifically, we introduce strengthened formulations, valid inequalities, and branch‐and‐cut algorithms based on delayed constraint generation. The results of our computational study indicate the significant benefits of using the approaches we introduce.

We study a class of adversarial minimum-cost flow problems where the arcs are subject to multiple ripple effect disruptions that increase their usage cost. The locations of the disruptions’ epicenters are uncertain, and the decision maker seeks a flow that minimizes cost assuming the worst-case realization of the disruptions. We evaluate the damage to each arc using a linear model, where the damage is the cumulative damage of all disruptions affecting the arc; and a maximum model, where the damage is given by the most destructive disruption affecting the arc. For both models, the arcs’ costs after disruptions are represented with a mixed-integer feasible region, resulting in a robust optimization problem with a mixed-integer uncertainty set. The main challenge to solve the problem comes from a subproblem that evaluates the worst-case cost for a given flow plan. We show that for the linear model the uncertainty set can be decomposed into a series of single disruption problems, which leads to a polynomial time algorithm for the subproblem. The uncertainty set of the maximum model, however, cannot be decomposed, and we show that the subproblem under this model is NP-hard. For this case, we further present a big-M free binary reformulation of the uncertainty set based on conflict constraints that results in a significantly smaller formulation with tighter linear programming relaxations. We extend the models by considering a less conservative approach where only a subset of the disruptions can occur and show that the properties of the linear and maximum models also hold in this case. We test our proposed approaches over real road networks and synthetics instances and show that our methods achieve orders of magnitude improvements over a standard approach from the literature. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0236] and the Office of Naval Research [Grant N00014-19-1-2329]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1243 .

We study a class of sequential defender-attacker optimization problems where the defender’s objective is uncertain and depends on the operations of the attacker, which are represented by a mixed-integer uncertainty set. The defender seeks to hedge against the worst possible data realization, resulting in a robust optimization problem with a mixed-integer uncertainty set, which requires the solution of a challenging mixed-integer problem, which can be seen as a saddle-point problem over a nonconvex domain. We study two exact solution algorithms and present two feature applications for which the uncertainty is naturally modeled as a mixed-integer set. Our computational experiments show that the considered algorithms greatly outperform standard algorithms both in terms of computational time and solution quality. Moreover, our results show that modeling uncertainty with mixed-integer sets, instead of approximating the data using convex sets, results in less conservative solutions, which translates to a lower cost for the defender to protect from uncertainty. Summary of Contribution: We consider a class of defender-attacker problems where the defender has to make operational decisions that depend on uncertain actions from an adversarial attacker. Due to the type of information available to the defender, neither probabilistic modeling, nor robust optimization methods with convex uncertainty sets, are well suited to address the defender’s decision-making problem. Consequently, we frame the defender’s problem as a class of robust optimization problems with a mixed-integer uncertainty sets, and devise two exact algorithms that solve this class of problems. A comprehensive computational study shows that for the considered applications, our algorithms improves the performance of existing robust optimization approaches that can be adapted to solve this class of problems. Moreover, we show how mixed-integer uncertainty sets can reduce the level of over-conservatism that is a known issue of robust optimization approaches.