Because of their nested structure, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel problem, we present heuristic methods that are based on the solution of a linear number of problems of the nominal type. Moreover, quality guarantees for heuristically obtained solutions as well as sufficient ex-post conditions for global optimality of the outcomes are provided. In an extensive computational study on 2,240 instances, we assess the performance of our heuristics and compare them with alternative methods—both heuristic and exact—from the literature. We observe that the optimality gap is closed for a significant portion of the considered instances and that our methods often practically outperform alternative approaches in terms of the solution quality. Moreover, for the special case of Γ-robust interdiction problems, we report considerable speed-up factors when compared with recently published problem-tailored and exact solution approaches while also solving more instances to global optimality. 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.2023.0239 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0239 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

ABSTRACT This paper introduces a novel combinatorial optimization problem with ordering constraints, termed the Ordered Median Traveling Salesman Problem (OMTSP). The OMTSP integrates key elements from both the classic Traveling Salesman Problem (TSP) and the Ordered Median Location Problem. Specifically, the objective is to identify a tour that minimizes a weighted sum of the sorted arc lengths within the tour. This flexible framework enables the modeling of a wide range of combinatorial optimization problems related to the traditional TSP, like the bottleneck TSP, the balanced TSP, or other TSP variants in which fairness measures are applied to the arcs of the tour. In this work, we present new mathematical formulations for the OMTSP across different variable spaces, which are solved using a branch‐and‐cut approach. Leveraging several newly derived structural properties, we enhance these formulations through advanced preprocessing strategies, variable bounding and variable fixing techniques, as well as through the introduction of new valid inequalities. A comprehensive computational study is conducted to evaluate the effectiveness of the proposed formulations and their associated improvements.

A frequently studied problem in the context of digital marketing for online social networks is the influence maximization problem that seeks for an initial seed set of influencers to trigger an information propagation cascade (in terms of active message forwarders) of expected maximum impact. Previously studied problems typically neglect that the probability that individuals passively view content without forwarding it is much higher than the probability that they forward content. Considering passive viewing enables us to maximize more natural (social media) marketing metrics, including (a) the expected organic reach, (b) the expected number of total impressions, or (c) the expected patronage, all of which are investigated in this paper for the first time in the context of influence maximization. We propose mathematical models to maximize these objectives, whereby the model for variant (c) includes individual’s resistances and uses a multinomial logit model to model customer behavior. We also show that these models can be easily adapted to a competitive setting in which the seed set of a competitor is known. In a computational study based on network graphs from Twitter (now X) and from the literature, we show that one can increase the expected patronage, organic reach, and number of total impressions by 36% on average (and up to 13 times in particular cases) compared with seed sets obtained from the classical maximization of message-forwarding users. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Federal Ministry of Education, Science and Research of Austria and by the Austrian Agency for International Mobility and Cooperation in Education, Science and Research [Reference ICM-2019-13384]. 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.2023.0047 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0047 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract In this article, we develop novel mathematical models to optimize utilization of community energy storage (CES) by clustering prosumers and consumers into energy sharing communities/microgrids in the context of a smart city. Three different microgrid configurations are modeled using a unifying mixed‐integer linear programming formulation. These configurations represent three different business models, namely: the island model, the interconnected model, and the Energy Service Companies model. The proposed mathematical formulations determine the optimal households' aggregation as well as the location and sizing of CES. To overcome the computational challenges of treating operational decisions within a multi‐period decision making framework, we also propose a decomposition approach to accelerate the computational time needed to solve larger instances. We conduct a case study based on real power consumption, power generation, and location network data from Cambridge, MA. Our mathematical models and the underlying algorithmic framework can be used in operational and strategic planning studies on smart grids to incentivize the communitarian distributed renewable energy generation and to improve the self‐consumption and self‐sufficiency of the energy sharing community. The models are also targeted to policymakers of smart cities, utility companies, and Energy Service Companies as the proposed models support decision making on renewable energy related projects investments.

Abstract Given a bi‐directed graph modeling a telecommunication network, and a set of origin‐destination pairs representing traffic requests (commodities) along with their associated Service Function Chains (SFCs), the Virtual Network Function Placement and Routing Problem (VNFPRP) aims to find, for each commodity, one latency‐constrained routing path that visits the required Virtual Network Functions in a specific order. The function installation costs together with the node activation costs have to be minimized. In this paper, we present two extended Mixed Integer Programming (MIP) formulations to model the VNFPRP. For each formulation we define the master problem, the pricing problem, the associated Lagrangian bound and a specific branching scheme, in order to derive an efficient Branch‐and‐Price algorithm. We also provide several families of valid inequalities to strengthen the LP‐relaxation bounds. Computational results are reported comparing the performance of the two Branch‐and‐Price algorithms with a compact MIP formulation and its Branch‐and‐Benders‐cut implementation on a set of SNDlib instances representing telecommunication networks.

We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.

Abstract The Steiner tree problem (STP) in graphs is one of the most studied problems in combinatorial optimization. Since its inception in 1970, numerous articles published in the journal Networks have stimulated new theoretical and computational studies on Steiner trees: from approximation algorithms, heuristics, metaheuristics, all the way to exact algorithms based on (mixed) integer linear programming, fixed parameter tractability, or combinatorial branch‐and‐bounds. The pervasive applicability and relevance of Steiner trees have been reinforced by the recent 11th DIMACS Implementation Challenge in 2014 and the PACE 2018 Challenge. This article provides an overview of the rich developments from the last three decades for the STP in graphs and highlights the most recent computational studies for some of its closely related variants.

Two-person interdiction games represent an important modeling concept for applications in marketing, defending critical infrastructure, stopping nuclear weapons projects, or preventing drug smuggling. We present an exact branch-and-cut algorithm for interdiction games under the assumption that feasible solutions of the follower problem satisfy a certain monotonicity property. Prominent examples from the literature that fall into this category are knapsack interdiction, matching interdiction, and packing interdiction problems. We also show how practically relevant interdiction variants of facility location and prize-collecting problems can be modeled in our setting. Our branch-and-cut algorithm uses a solution scheme akin to Benders decomposition based on a family of so-called interdiction cuts. We present modified and lifted versions of these cuts along with exact and heuristic procedures for the separation of interdiction cuts and heuristic separation procedures for the other versions. In addition, we derive further valid inequalities and present a new heuristic procedure. We computationally evaluate the proposed algorithm on a benchmark of 360 knapsack interdiction instances from literature, including 27 instances for which the optimal solution was not known. Our approach is able to solve each of them to optimality within about one minute of computing time on a standard PC (in most cases, within just seconds), and it is up to some orders of magnitude faster than any previous approach from the literature. To further assess the effectiveness of our branch-and-cut algorithm, an additional computational study is performed on 144 randomly generated instances based on 0/1 multidimensional knapsack problems.

In this article we consider the network design problem with relays (NDPR), which gives answers to some important strategic design questions in telecommunication network design. Given a family of origin-destination pairs and a set of existing links these questions are as follows: (1) What are the optimal locations for signal regeneration devices (relays) and how many of them are needed? (2) Could the available infrastructure be enhanced by installing additional links in order to reduce the travel distance and therefore reduce the number of necessary relays? In contrast to previous work on the NDPR, which mainly focused on heuristic approaches, we discuss exact methods based on different mixed-integer linear programming formulations for the problem. We develop branch-and-price and branch-price-and-cut algorithms that build upon models with an exponential number of variables (and constraints). In an extensive computational study, we analyze the performance of these approaches for instances that reflect different real-world settings. Finally, we also point out the relevance of the NDPR in the context of electric mobility.

We present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS), and node-weighted Steiner tree problem (NWSTP). The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong’s dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful bound-based reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. Extensive computational results on benchmark instances for the PCSTP, MWCS, and NWSTP indicate the framework’s effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner trees. Moreover, results on new asymmetric instances for the APCSTP are reported. Since the addressed network design problems are frequently used for modeling various real-world applications (e.g., in bioinformatics), the implementation of the presented B&B framework has been made publicly available.

In this article, we consider the Node‐Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node‐induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node‐cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition‐based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well‐known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 33–51 2017

We consider a network design application that is modeled as the two-level network design problem under uncertainty. In this problem, one of the two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. The decision maker is confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated with the possible realizations of primary customers is available. The network is built in two stages. In the first stage the network topology must be determined. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded, if necessary to primary technology, but at higher recovery cost. The overall goal then is to build a “recoverable robust” spanning tree in the first stage that serves all customers by at least the lower level technology, and that minimizes the first-stage installation cost plus the worst-case cost needed to upgrade the edges of the selected tree, so that the primary customers of each scenario can be served using the primary technology. We discuss the complexity of the problem, provide mixed-integer programming models, and develop a branch-and-cut algorithm to solve it. Our extensive computational experiments demonstrate the efficacy of our approach.

In an optical network a signal can only travel a maximum distance dmaxbefore its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S = T = N, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances.

We introduce the bi-objective prize-collecting Steiner tree problem, whose goal is to find a subtree considering the conflicting objectives of minimizing the edge costs for building that tree, and maximizing the collected node revenues. We consider five iterative mixed-integer programming (MIP) frameworks that identify the complete Pareto front, i.e., one efficient solution for every point on the Pareto front. More precisely, the following methods are studied: an ε-constraint method, a two-phase method, a binary search in the objective space, a weighted Chebyshev norm method, and a method of Sylva and Crema. We also investigate how to exploit and recycle information gained during these iterative MIP procedures to accelerate the solution process. We consider (i) additional strengthening valid inequalities, (ii) procedures for initializing feasible solutions (using a solution pool), (iii) procedures for recycling violated cuts (using a cut pool), and (iv) guiding the branching process by previously detected Pareto optimal solutions. This work is a first study on exact approaches for solving the bi-objective prize-collecting Steiner tree problem. Standard benchmark instances from the literature are used to assess the efficacy of the proposed methods.

Given a set of customers, a set of potential facility locations, and some interconnection nodes, the goal of the connected facility location problem (ConFL) is to find the minimum-cost way of assigning each customer to exactly one open facility and connecting the open facilities via a Steiner tree. The sum of costs needed for building the Steiner tree, facility opening costs, and the assignment costs needs to be minimized. If the number of edges between a prespecified node (the so-called root) and each open facility is limited, we speak of the hop constrained facility location problem (HC ConFL). This problem is of importance in the design of data-management and telecommunication networks. In this article we provide the first theoretical and computational study for this new problem that has not been studied in the literature so far. We propose two disaggregation techniques that enable the modeling of HC ConFL: (i) as a directed (asymmetric) ConFL on layered graphs, or (ii) as the Steiner arborescence problem (SA) on layered graphs. This allows for usage of best-known mixed integer programming models for ConFL or SA to solve the corresponding hop constrained problem to optimality. In our polyhedral study, we compare the obtained models with respect to the quality of their linear programming lower bounds. These models are finally computationally compared in an extensive computational study on a set of publicly available benchmark instances. Optimal values are reported for instances with up to 1,300 nodes and 115,000 edges.

Abstract This article considers the network design problem that searches for a minimum‐cost way of installing capacities on the edges of a network to simultaneously route a flow from a given access point to a subset of nodes representing customers with positive demands. We first consider compact and exponential‐sized Mixed Integer Programming (MIP) formulations of the problem and provide their theoretical and computational comparison. We also consider a stronger disaggregated flow formulation. To solve the problem in practice, we project out the flow variables and generate Benders cuts within a branch‐and‐cut framework. To the best of our knowledge, the combination of Benders approach and this specific disaggregation has not been considered so far. In an extensive computational study, we compare the performance of compact MIP models against a textbook implementation and several normalization variants of Benders decomposition. We introduce a set of 32 real‐world instances and use these, together with 64 other instances from the literature, to test our approaches. The results show that our branch‐and‐cut approach outperforms the best performing compact formulation leading to the best exact algorithm today for solving the considered dataset. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract In this article, we introduce the regenerator location problem (RLP), which deals with a constraint on the geographical extent of transmission in optical networks. Specifically, an optical signal can only travel a maximum distance of dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. We show that the RLP is NP‐Complete. We then devise three heuristics for the RLP. We show how to represent the RLP as a max leaf spanning tree problem (MLSTP) on a transformed graph. Using this fact, we model the RLP as a Steiner arborescence problem (SAP) with a unit degree constraint on the root node. We also devise a branch‐and‐cut procedure to the directed cut formulation for the SAP problem. In our computational results over 740 test instances, the heuristic procedures obtained the optimal solution in 454 instances, whereas the branch‐and‐cut procedure obtained the optimal solution in 536 instances. These results indicate the quality of the heuristic solutions are quite good, and the branch‐and‐cut approach is viable for the optimal solution of problems with up to 100 nodes. Our approaches are also directly applicable to the MLSTP indicating that both the heuristics and branch‐and‐cut approach are viable options for the MLSTP. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract In this article, the first approach for solving the vertex‐biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge‐weighted graph, we search for the cheapest subset of edges to augment this subgraph to make it vertex‐biconnected. The problem is reduced to augmentation of the corresponding block‐cut tree [Khuller and Thummella, J Algorithms 14 (1993), 214–225], and its connectivity properties are exploited to develop two minimum‐cut‐based ILP formulations: a directed and an undirected one. In contrast to the recently obtained result for the more general vertex‐biconnected Steiner network problem [Chimani et al., Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 5165, Springer, 2008, pp. 190–200.], our theoretical comparison shows that orienting the undirected graph does not help in improving the quality of lower bounds. Hence, starting from the undirected cut formulation, we develop a branch‐and‐cut‐and‐price (BCP) algorithm which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of BCP: complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than state‐of‐the‐art metaheuristics and approximation algorithms, for graphs up to 200 vertices. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Given an undirected graph G = (V, E) with edge weights and a positive integer number k, the k-Cardinality Tree problem consists of finding a subtree T of G with exactly k edges and the minimum possible weight. Many algorithms have been proposed to solve this NP-hard problem, resulting in mainly heuristic and metaheuristic approaches. In this paper we present an exact ILP-based algorithm using directed cuts. We mathematically compare the strength of our formulation to the previously known ILP formulations of this problem, and give an extensive study on the algorithm's practical performance compared to the state-of-the-art metaheuristics. In contrast to the widespread assumption that such a problem cannot be efficiently tackled by exact algorithms for medium and large graphs (between 200 and 5000 nodes), our results show that our algorithm not only has the advantage of proving the optimality of the computed solution, but also often outperforms the metaheuristic approaches in terms of running time.

In this paper we present a genetic algorithm (GA) for the NP-hard biconnectivity problem for graphs. Suppose a 2-connected, undirected weighted graph G(V,E) and a spanning subset of edges E/sub 0//spl sub/E are given. The goal is to augment set E/sub 0/ with a set AUG/spl sub/E-E/sub 0/ of minimal weight, such that graph G(V,E/sub 0//spl cup/AUG) is biconnected. To our knowledge, this is the first time a GA is applied to this problem. First, a straight-forward "pure" GA improved with caching is introduced, which is then hybridized with a greedy, problem dependent heuristic. The proposed approaches are problem instances with up to 1160 feasible edges. While the pure GA performs well, significantly better solutions can be obtained by the hybrid strategy.