In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision maker (referred to as a leader) and the lower-level decision maker (referred to as a follower) are induced by two distinct partition matroids with a common weighted ground set. Unlike classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent capacity constraints and engage in a zero-sum game. Although the problem of finding a maximum weight independent set in a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is NP-hard even when the weights of ground elements are all binary. On a positive note, it is revealed that, if the number of capacity constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial-time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a greedy algorithm for the leader. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

We consider the max-min eigenvalue augmentation problem: given $n \times n$ symmetric positive semidefinite matrices $M,A_1,\ldots, A_m$ and a positive integer $k < m$, the goal is to choose a subset $I \subset \{1,\ldots,m\}$ of cardinality at most $k$ that maximizes the minimum eigenvalue of the matrix $M + \sum_{i \in I} A_i$. The problem captures both the Bayesian E-optimal design and maximum algebraic connectivity augmentation problems. In contrast to the existing work, we do not assume that the augmentation matrices are rank-one matrices, and we focus on the setting in which $k < n$. We show that a simple randomized rounding method provides a constant-factor approximation if the optimal increase is sufficiently large, specifically, if $\mathrm{OPT} - \lambda_{\mathrm{min}}(M) = \Omega(R \ln k)$, where $\mathrm{OPT}$ is the optimal value, and $R$ is the maximum trace of an augmentation matrix. To establish the guarantee, we derive a matrix concentration inequality that is of independent interest. The inequality can be interpreted as an intrinsic dimension analog of the matrix Chernoff inequality for the minimum eigenvalue of a sum of independent random positive semidefinite matrices; such an inequality has already been established for the maximum eigenvalue, but not for the minimum eigenvalue.

Given a vertex-weighted undirected graph with blocking costs of its vertices and edges, we seek a minimum cost subset of vertices and edges to block such that the weight of any γ-quasi-clique in the interdicted graph is at most some predefined threshold parameter. The value of [Formula: see text] specifies the edge density of cohesive vertex groups of interest in the network. The considered weighted γ-quasi-clique interdiction problem can be viewed as a natural generalization of several variations of the clique blocker problem previously studied in the literature. From the application perspective, this setting is primarily motivated by the problem of disrupting adversarial (“dark”) networks (e.g., social or communication networks), where γ-quasi-cliques represent “tightly knit” groups of adversaries that we aim to dismantle. We first address the theoretical computational complexity of the problem. We then exploit some basic characterization of its feasible solutions to derive a linear integer programming (IP) formulation. This linear IP model can be solved using a lazy-fashioned branch-and-cut scheme. We also propose a combinatorial branch-and-bound algorithm for solving this problem. The computational performance of the developed exact solution schemes is studied using a test bed of randomly generated and real-life networks. Finally, some interesting insights and observations are also provided using a well-known example of a terrorist network. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: The work of S. Butenko was partially supported by the Air Force Office of Scientific Research under Award FA9550-23-1-0300. The work of O. A. Prokopyev was partially supported by the Office of Naval Research under Award ONR N00014-22-1-2678. 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.0027 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0027 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . The online appendix is available at https://doi.org/10.1287/ijoc.2023.0027 .

ABSTRACT This article proposes an implicit enumeration approach to solve the maximum ratio ‐plex and the maximum ratio ‐defective clique problems. The approach is inspired by the classical Bron‐Kerbosch algorithm for enumerating all maximal cliques in a graph, which is extended to enumerating structures that are hereditary on induced subgraphs. Such structures include ‐plexes and ‐defective cliques, among many others. The performance of the proposed approach is compared with that of the methods based on mixed integer linear programming (MILP), binary search, and Newton's iteration through numerical experiments on randomly generated and real‐life network instances.

Failures of safety-critical mission-based systems, such as aircraft and submarines, could result in significant losses and damage. To enhance the survivability of such systems, their missions may be aborted if the failure risk becomes too high. We investigate such mission abort policies under a completely observed two-stage degradation process that progresses stochastically from “normal” to “defective” to “failure.” Mission abort decisions are considered as a function of the duration of the defective stage. This mission abort problem is formulated as a discrete-time optimal stopping problem with the goal of minimizing the expected total cost of mission failure and system failure. In addition to deriving some structural properties, we also numerically evaluate several intuitive heuristic policies. Finally, a joint optimization problem is formulated to simultaneously identify the optimal mission abort policy and the optimal investment to delay system deterioration.

Abstract This article introduces and studies two clique relaxation models with fractional objectives: the maximum ratio ‐plex problem and the maximum ratio ‐defective clique problem. The decision version of each problem is shown to be strongly ‐complete; we also discuss some related computational complexity issues. The base optimization models are single‐ratio fractional 0‐1 problems. We describe two general types of solution methods: the first one is based on mixed‐integer linear programs (MILPs) obtained by linearizing the original nonlinear 0‐1 models; the other one exploits parametric methods (namely, a binary search and Newton's method) that solve MILPs in an iterative manner. For the proposed MILPs, we derive valid inequalities that are shown to substantially improve the performance of an off‐the‐shelf MILP solver. Finally, the considered solution approaches are compared via extensive numerical experiments using a set of artificially generated and real‐life network instances.

Network cascades represent a number of real-life applications: social influence, electrical grid failures, viral spread, and so on. The commonality between these phenomena is that they begin from a set of seed nodes and spread to other regions of the network. We consider a variant of a critical node detection problem dubbed the robust critical node fortification problem, wherein the decision maker wishes to fortify nodes (within a budget) to limit the spread of cascading behavior under uncertain conditions. In particular, the arc weights—how much influence one node has on another in the cascade process—are uncertain but are known to lie in some range bounded by a worst-case budget uncertainty. This problem is shown to be [Formula: see text]-hard even in the deterministic case. We formulate a mixed-integer program (MIP) to solve the deterministic problem and improve its continuous relaxation via nonlinear constraints and convexification. The robust problem is computationally more difficult, and we present an MIP-based expand-and-cut exact solution algorithm, in which the expansion is enhanced by cutting planes, which are themselves tied to the expansion process. Insights from these exact solutions motivate two novel (interrelated) centrality measures, and a centrality-based heuristic that obtains high-quality solutions within a few seconds. Finally, extensive computational results are given to validate our theoretical developments as well as provide insights into structural properties of the robust problem and its solution.

We consider the best subset selection problem in linear regression—that is, finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We are primarily concerned with alternatives to cross-validation methods that do not require data partitioning and involve a range of information criteria extensively studied in the statistical literature. We show that the problem of interest can be modeled using fractional mixed-integer optimization, which can be tackled by leveraging recent advances in modern optimization solvers. The proposed algorithms involve solving a sequence of mixed-integer quadratic optimization problems (or their convexifications) and can be implemented with off-the-shelf solvers. We report encouraging results in our computational experiments, with respect to both the optimization and statistical performance. Summary of Contribution: This paper considers feature selection problems with information criteria. We show that by adopting a fractional optimization perspective (a well-known field in nonlinear optimization and operations research), it is possible to leverage recent advances in mixed-integer quadratic optimization technology to tackle traditional statistical problems long considered intractable. We present extensive computational experiments, with both synthetic and real data, illustrating that the new fractional optimization approach is orders of magnitude faster than existing approaches in the literature.

In many maintenance settings, it is assumed that the preventive maintenance policy prescribed by the maintenance planner is implemented without error. However, in practice, the party who implements the policy often deviates from the intended maintenance times. We study an age-replacement setting in which the maintenance worker may be unpunctual. That is, the actual preventive replacement times may deviate from the prescribed replacement times in a probabilistic manner. Previous work on this problem assumes that the degree of unpunctuality is not influenced by the length of time between scheduled replacements. We relax this assumption and let the degree of deviation depend on the prescribed replacement time. In this article, we formulate a long-run cost-rate minimization model and present analytical and numerical results that compare its optimal solution and performance to those when the unpunctual behavior is assumed to be either absent or independent of the prescribed replacement time. We also provide insights that can help maintenance planners adjust their policies in anticipation of nonstationary, unpunctual implementation.

Abstract We introduce the two‐stage stochastic minimum s − t cut problem. Based on a classical linear 0‐1 programming model for the deterministic minimum s − t cut problem, we provide a mathematical programming formulation for the proposed stochastic extension. We show that its constraint matrix loses the total unimodularity property, however, preserves it if the considered graph is a tree. This fact turns out to be not surprising as we prove that the considered problem is ‐hard in general, but admits a linear time solution algorithm when the graph is a tree. We exploit the special structure of the problem and propose a tailored Benders decomposition algorithm. We evaluate the computational efficiency of this algorithm by solving the Benders dual subproblems as max‐flow problems. For many tested instances, we outperform a standard Benders decomposition by two orders of magnitude with the Benders decomposition exploiting the max‐flow structure of the subproblems.

Closeness centrality is a class of distance-based measures in the network analysis literature to quantify reachability of a given vertex (or a group of vertices) by other network agents. In this paper, we consider a new class of critical edge detection problems, in which given a group of vertices that represent an important subset of network elements of interest (e.g., servers that provide an essential service to the network), the decision maker is interested in identifying a subset of critical edges whose removal maximally degrades the closeness centrality of those vertices. We develop a general optimization framework, in which the closeness centrality measure can be based on any nonincreasing function of distances between vertices, which, in turn, can be interpreted as communication efficiency between them. Our approach includes three well-known closeness centrality measures as special cases: harmonic centrality, decay centrality, and [Formula: see text]-step reach centrality. Furthermore, for quantifying the centrality of a group of vertices we consider three different approaches for measuring the reachability of the group from any vertex in the network: minimum distance to a vertex in the group, maximum distance to a vertex in the group, and the average centrality of vertices in the group. We study the theoretical computational complexity of the proposed models and describe the corresponding mixed integer programming formulations. For solving medium- and large-scale instances of the problem, we first develop an exact algorithm that exploits the fact that real-life networks often have rather small diameters. Then we propose two conceptually different heuristic algorithms. Finally, we conduct computational experiments with real-world and synthetic network instances under various settings, which reveal interesting insights and demonstrate the advantages and limitations of the proposed models and algorithms. The online appendices are available at https://doi.org/10.1287/ijoc.2018.0829 .

Abstract We study a class of bilevel spanning tree (BST) problems that involve two independent decision‐makers (DMs), the leader and the follower with different objectives, who jointly construct a spanning tree in a graph. The leader, who acts first, selects an initial subset of edges that do not contain a cycle, from the set under her control. The follower then selects the remaining edges to complete the construction of a spanning tree, but optimizes his own objective function. If there exist multiple optimal solutions for the follower that result in different objective function values for the leader, then the follower may choose either the one that is the most (optimistic version) or least (pessimistic version) favorable to the leader. We study BST problems with the sum‐ and bottleneck‐type objective functions for the DMs under both the optimistic and pessimistic settings. The polynomial‐time algorithms are then proposed in both optimistic and pessimistic settings for BST problems in which at least one of the DMs has the bottleneck‐type objective function. For BST problem with the sum‐type objective functions for both the leader and the follower, we provide an equivalent single‐level linear mixed‐integer programming formulation. A computational study is then presented to explore the efficacy of our reformulation.

The influence class of network problems models the propagation of influence (an abstraction of cascading beliefs, behaviors, or physical phenomena) in a network. Such problems have applications in social networks, electrical networks, computer networks, viral spreading, and so on. These types of networks have also been studied through the lens of critical arcs detection; that is, which arcs (edges) are the most important for maintaining some property of the network (e.g., connectivity). We introduce a new class of problems at the intersection of these two models. Specifically, given a set of seed nodes and the linear threshold influence propagation model, our work proposes to determine which arcs (e.g., relationships in a social network or communication pathways in a telecommunication network) are most critical to the influence propagation process. We prove NP‐hardness of the problem. Time‐dependent and time‐independent mixed‐integer programming (MIP) models are introduced. Insights gleaned from MIP solutions leads to the development of an improved MIP‐based exact algorithm rooted in the idea of diffusion expansion. A heuristic based upon a new centrality measure is also proposed, and computational results are presented. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 412–431 2018

We consider the problem of finding a degree‐based ‐quasi‐clique of maximum cardinality in a given graph for some fixed . A degree‐based ‐quasi‐clique (often referred to as simply a quasi‐clique) is a subgraph, where the degree of each vertex is at least times the maximum possible degree of a vertex in the subgraph. A degree‐based ‐quasi‐clique is a relative clique relaxation model, where the case of corresponds to the well‐known concept of a clique. In this article, we first prove that the problem is ‐hard for any fixed , which addresses one of the open questions in the literature. More importantly, we also develop new exact solution methods for solving the problem and demonstrate their advantages and limitations in extensive computational experiments with both random and real‐world networks. Finally, we outline promising directions of future research including possible functional generalizations of the considered clique relaxation model. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 136–152 2018

Many patients face difficulties when accessing medical facilities, particularly in rural areas. To alleviate these concerns, medical centers may offer transportation to eligible patients. However, the operation of such services is typically not tightly coordinated with the scheduling of medical appointments. Motivated by our collaborations with the U.S. Veterans Health Administration, we propose an integrated approach that simultaneously considers patient routing and operating room scheduling decisions. We model this problem as a mixed-integer program. Unfortunately, realistically sized instances of this problem are intractable, so we focus on a special case of the problem that captures the needs of low-volume (e.g., rural) hospitals. We establish structural properties that are exploited to develop a branch-and-price algorithm, which greatly outperforms a commercial solver on the original formulation. We discuss several algorithmic strategies to improve the overall solution efficiency. We evaluate the performance of the proposed approach through an extensive computational study calibrated with clinical data. Our results demonstrate that there exist opportunities for healthcare providers to significantly improve the quality of their services by integrating scheduling and routing decisions.

In this article, a heuristic is said to be provably best if, assuming , no other heuristic always finds a better solution (when one exists). This extends the usual notion of “best possible” approximation algorithms to include a larger class of heuristics. We illustrate the idea on several problems that are somewhat stylized versions of real‐life network optimization problems, including the maximum clique, maximum k‐club, minimum (connected) dominating set, and minimum vertex coloring problems. The corresponding provably best construction heuristics resemble those commonly used within popular metaheuristics. Along the way, we show that it is hard to recognize whether the clique number and the k‐club number of a graph are equal, yet a polynomial‐time computable function is “sandwiched” between them. This is similar to the celebrated Lovász function wherein an efficiently computable function lies between two graph invariants that are ‐hard to compute. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 238–245 2016

This study considers a class of critical node detection problems that involves minimization of a distance‐based connectivity measure of a given unweighted graph via the removal of a subset of nodes (referred to as critical nodes) subject to a budgetary constraint. The distance‐based connectivity measure of a graph is assumed to be a function of the actual pairwise distances between nodes in the remaining graph (e.g., graph efficiency, Harary index, characteristic path length, residual closeness) rather than simply whether nodes are connected or not, a typical assumption in the literature. We derive linear integer programming (IP) formulations, along with additional enhancements, aimed at improving the performance of standard solvers. For handling larger instances, we develop an effective exact algorithm that iteratively solves a series of simpler IPs to obtain an optimal solution for the original problem. The edge‐weighted generalization is also considered, which results in some interesting implications for distance‐based clique relaxations, namely, ‐clubs. Finally, we conduct extensive computational experiments with real‐world and randomly generated network instances under various settings that reveal interesting insights and demonstrate the advantages and limitations of the proposed approach. In particular, one important conclusion of our work is that vulnerability of real‐world networks to targeted attacks can be significantly more pronounced than what can be estimated by centrality‐based heuristic methods commonly used in the literature. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 170–195 2015

This paper considers a system with periodic inspections and periodic preventive maintenance (PM) to detect and correct hidden failures that generate a penalty cost per unit time undetected. Imperfect periodic inspections (IPIs) occur at a chosen interval$t$, and detect hidden failures with probability$p\in (0,1)$. Both reactive maintenance (RM), performed when a hidden failure is detected by an IPI, and PM, performed at a chosen time$(n+1)t$, renew the system. The objective is to determine the optimal frequency$t$and quantity$n$of imperfect inspections between PM such that the expected cost (which includes the costs of undetected failures, IPIs, PM, and RM) per unit time is minimized over an infinite horizon. We analytically establish conditions for the existence of a finite optimal$t$for a given value of$n$, and discuss the asymptotic behavior of the objective function for large$n$and$t$. These results are further exploited to describe convergence properties of a proposed approach for finding a globally optimal solution. Also, for the special case of a Weibull time-to-failure distribution, we derive conditions that guarantee the uniqueness of a locally optimal solution for a given value of$n$.

Implantable cardioverter defibrillators (ICDs) include small, battery-powered generators, the longevity of which depends on a patient's rate of consumption. Generator replacement, however, involves risks, including death. Hence, a trade-off exists between prematurely exposing the patient to these risks and allowing for the possibility that the device is unable to deliver therapy when needed. Currently, replacements are performed using a one-size-fits-all approach. Here, we develop a Markov decision process model to determine patient-specific optimal replacement policies as a function of patient age and the remaining battery capacity. We analytically establish that the optimal policy is of threshold-type in the remaining capacity, but not necessarily in patient age. Based on clinical data, we conduct a large computational study that suggests that under the optimal policy, patients undergoing initial implantation at age 30–40, 41–60, and 61–80 see an approximate decrease in the total expected number of replacements of 8%–14%, 8%–15% and 8%–19%, respectively, while achieving the same or greater expected lifetime.

We consider the problem of maximizing the lifetime of a query-based wireless sensor network in which all of the sensor nodes are both producers and consumers of network resources. Of particular concern is the problem of selecting a common transmission range for all of the sensor nodes, the resource replication level (or time-to-live counter), and the active/sleep schedule of nodes while satisfying connectivity and quality-of-service constraints. To this end, we first formulate a general, mixed-integer programming model that selects the optimal operating parameters in each period of a finite planning horizon. Subsequently, we examine in detail specific connectivity and quality-of-service constraints that can be considered within this framework. Due to the complexity of the model, we formulate an alternative linearized version that can be solved more efficiently. Additionally, we devise a simple algorithm to solve a special case of the problem when alive nodes are always active. Computational results indicate that the maximum attainable lifetime can be significantly improved by adjusting the key operating parameters as sensor nodes fail over time due to energy depletion.

We discuss two possible parallel strategies for randomized restart algorithms. Given a set of available algorithms, one can either choose the best performing algorithm and run its multiple copies in parallel (single algorithm portfolio) or choose some subset of algorithms to run in parallel (mixed algorithm portfolio). It has been previously shown that the latter approach may provide better results computationally. In this paper, we provide theoretical investigation of the extent of such improvement generalizing some of the known results from the literature. In particular, we estimate the computational value of mixing randomized restart algorithms with different properties. Under some mild assumptions, we prove that in the best case the mixed algorithm portfolio may perform approximately up to 1.58 times faster than the best single algorithm portfolio. We also show that the obtained upper bound is sharp. Furthermore, the constructive proof of the main result allows us to characterize algorithms that are likely to form an effective mixed algorithm portfolio.

Scheduling elective procedures in an operating suite is a formidable task because of competing performance metrics and uncertain surgery durations. In this paper, we present an optimization framework for batch scheduling within a block booking system that maximizes the expected utilization of operating room resources subject to a set of probabilistic capacity constraints. The algorithm iteratively solves a series of mixed-integer programs that are based on a normal approximation of cumulative surgery durations. This approximation is suitable for high-volume medical specialities but might not be acceptable for the specialties that perform few procedures per block. We test our approach using the data from the ophthalmology department of the Veterans Affairs Pittsburgh Healthcare System. The performance of the schedules obtained by our approach is significantly better than schedules produced by simple heuristic scheduling rules.

MOTIVATION: A major limitation in modeling protein interactions is the difficulty of assessing the over-fitting of the training set. Recently, an experimentally based approach that integrates crystallographic information of C2H2 zinc finger-DNA complexes with binding data from 11 mutants, 7 from EGR finger I, was used to define an improved interaction code (no optimization). Here, we present a novel mixed integer programming (MIP)-based method that transforms this type of data into an optimized code, demonstrating both the advantages of the mathematical formulation to minimize over- and under-fitting and the robustness of the underlying physical parameters mapped by the code. RESULTS: Based on the structural models of feasible interaction networks for 35 mutants of EGR-DNA complexes, the MIP method minimizes the cumulative binding energy over all complexes for a general set of fundamental protein-DNA interactions. To guard against over-fitting, we use the scalability of the method to probe against the elimination of related interactions. From an initial set of 12 parameters (six hydrogen bonds, five desolvation penalties and a water factor), we proceed to eliminate five of them with only a marginal reduction of the correlation coefficient to 0.9983. Further reduction of parameters negatively impacts the performance of the code (under-fitting). Besides accurately predicting the change in binding affinity of validation sets, the code identifies possible context-dependent effects in the definition of the interaction networks. Yet, the approach of constraining predictions to within a pre-selected set of interactions limits the impact of these potential errors to related low-affinity complexes. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this paper we consider the order-preserving submatrix (OPSM) problem. This problem is known to be NP-hard. Although in recent years some heuristic methods have been presented to find OPSMs, they lack the guarantee of optimality. We present exact solution approaches based on linear mixed 0–1 programming formulations and develop algorithmic enhancements to aid in solvability. Encouraging computational results are reported both for synthetic and real biological data. In addition, we discuss theoretical computational complexity issues related to finding fixed patterns in matrices.

A cooperative team's performance strongly depends on the view that the team has of the environment in which it operates. In a team with many autonomous vehicles and many sensors, there is a large volume of information available from which to create that view. However, typically communication bandwidth limitations prevent all sensor readings being shared with all other team members. This paper presents three policies for sharing information in a large team that balance the value of information against communication costs. Analytical and empirical evidence of their effectiveness is provided. The results show that using some easily obtainable probabilistic information about the team dramatically improves overall belief sharing performance. Specifically, by collectively estimating the value of a piece of information, the team can make most efficient use of its communication resources.