We propose a novel exact algorithm for the transportation problem, one of the paradigmatic network optimization problems. The algorithm, called Iterated Inside Out, requires as input a basic feasible solution and is composed of two main phases that are iteratively repeated until an optimal basic feasible solution is computed. In the first “inside” phase, the algorithm progressively improves upon a given basic solution by increasing the value of several nonbasic variables with negative reduced cost. This phase typically outputs a nonbasic feasible solution interior to the constraint set polytope. The second “out” phase moves in the opposite direction by iteratively setting to zero several variables until a new improved basic feasible solution is reached. Extensive computational tests show that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in the commercial solvers CPLEX and Gurobi and other exact algorithms available in the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. 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.0642 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0642 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Designing efficient algorithms to compute Nash equilibria poses considerable challenges in algorithmic game theory and optimization. In this work, we employ integer programming techniques to compute Nash equilibria in integer programming games, a class of simultaneous and noncooperative games in which each player solves a parameterized integer program. We introduce zero regrets, a general and efficient cutting-plane algorithm to compute, enumerate, and select Nash equilibria. Our framework leverages the concept of equilibrium inequality, an inequality valid for any Nash equilibrium, and the associated equilibrium separation oracle. We evaluate our algorithmic framework on a wide range of practical and methodological problems from the literature, providing a solid benchmark against the existing approaches. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0282 .

Abstract We tackle a stochastic version of the critical node problem (CNP) where the goal is to minimize the pairwise connectivity of a graph by attacking a subset of its nodes. In the stochastic setting considered, the outcome of attacks on nodes is uncertain. In our work, we focus on trees and demonstrate that over trees the stochastic CNP actually generalizes to the stochastic critical element detection problem where the outcome of attacks on edges is also uncertain. We prove the NP‐completeness of the decision version of the problem when connection costs are one, while its deterministic counterpart was proved to be polynomial. We then derive a nonlinear model for the considered CNP version over trees and provide a corresponding linearization based on the concept of probability chains. Moreover, given the features of the derived linear model, we devise an exact Benders decomposition (BD) approach where we solve the slave subproblems analytically. A strength of our approach is that it does not rely on any statistical approximation such as the sample average approximation, which is commonly employed in stochastic optimization. We also introduce an approximation algorithm for the problem variant with unit connection costs and unit attack costs, and a specific integer linear model for the case where all the survival probabilities of the nodes in case of an attack are equal. Our methods are capable of solving relevant instances of the problem with hundreds of nodes within 1 hour of computational time. With this work, we aim to foster research on stochastic versions of the CNP, a problem tackled mainly in deterministic contexts so far. Interestingly, we also show a successful application of the concept of probability chains for problem linearizations significantly improved by decomposition methods such as the BD.

We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of nodes. The two metaheuristics are based on the Iterated Local Search and Variable Neighborhood Search frameworks. Their main characteristic is to exploit two smart and computationally efficient neighborhoods which we show can be implemented far more efficiently than the classical neighborhood based on the exchange of any two nodes in the graph, and which we prove is equivalent to the classical neighborhood in the sense that it yields the same set of neighbors. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated. The results of the proposed metaheuristics outperform those currently available in literature. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 209–221 2016