Search for: All records

Abstract The analysis of social and biological networks often involves modeling clusters of interest ascliquesor 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 across‐graph‐clubmodel, 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. 

Abstract In this study, we address the mate selection problem in the hybridization stage of a breeding pipeline, which constitutes the multi-objective breeding goal key to the performance of a variety development program. The solution framework we formulate seeks to ensure that individuals with the most desirable genomic characteristics are selected to cross in order to maximize the likelihood of the inheritance of desirable genetic materials to the progeny. Unlike approaches that use phenotypic values for parental selection and evaluate individuals separately, we use a criterion that relies on the genetic architecture of traits and evaluates combinations of genomic information of the pairs of individuals. We introduce theexpected cross value(ECV) criterion that measures the expected number of desirable alleles for gametes produced by pairs of individuals sampled from a population of potential parents. We use the ECV criterion to develop an integer linear programming formulation for the parental selection problem. The formulation is capable of controlling the inbreeding level between selected mates. We evaluate the approach or two applications: (i) improving multiple target traits simultaneously, and (ii) finding a multi-parental solution to design crossing blocks. We evaluate the performance of the ECV criterion using a simulation study. Finally, we discuss how the ECV criterion and the proposed integer linear programming techniques can be applied to improve breeding efficiency while maintaining genetic diversity in a breeding program. 

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/ . 

We introduce the Influence Coverage Optimization Problem (ICOP), which is an influence maximization problem where the activation of nodes also depends on their location on the plane. Specifically, the ICOP assumes that there is a network where nodes become active (i.e., influenced) either by the influence they receive from interactions with active in-neighbors or by entering the coverage area of a physical ad or a Geo-fence. The objective is to locate a fixed number of ads or Geo-fences and modify the network influence rates to minimize the network activation time. Assuming a Markovian influence model, we prove that the ICOP is 𝑁𝑃-hard, and then we present mixed-integer programming formulations for three different types of coverage modes. A reformulation of the non-linear “big-M” constraints, two types of valid cuts, and a fast heuristic based on the k-means algorithm are used as enhancements that facilitate solving the ICOP via an Iterative Decomposition Branch-and-Cut (IDBC) algorithm. In addition, we present an alternative discrete formulation of the ICOP using critical intersection points. Several experiments under various parameter configurations across instances with more than a hundred nodes and thousand arcs are conducted, showing the IDBC’s capability to provide optimal solutions within seconds or minutes for most instances. Moreover, the experiments reveal that the ICOP can significantly outperform a Geo-fence coverage model that does not consider network interactions to make location decisions. 

We introduce a new variant of the network interdiction problem with a Markovian evader that randomly chooses a neighboring vertex in each step to build their path from designated source(s) to terminal(s). The interdictor's goal is to maximize the evader's minimum expected first passage time. We establish sufficient conditions for the interdiction to not be counter-productive, prove that the problem is NP-hard, and demonstrate the model's usefulness by solving a mixed-integer programming formulation on a test bed of social networks. 

The analysis of social and biological networks often involves model- ing clusters of interest as cliques or their graph-theoretic generaliza- tions. 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/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 paper, we consider the canonical optimization problem of finding a cross-graph 𝑘-club of maximum cardinality. We introduce algorithmic ideas to solve this problem and evaluate their performance on some benchmark instances. Published in: Proceedings of The International Network Optimization Conference (INOC) 2022, Aachen, Germany