Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.     

Dynamic interdiction networks with applications in illicit supply chains

We study the interdiction of illegal product distribution in a network with multiple sources (origins) and sinks (destinations). This work contributes to the literature of dynamic maximum flow interdiction problems by addressing multiple commodities in a network of relationships. The related distribution network consists of (1) criminals, who are hierarchically connected, and seeking to maximize the total profit flow from origins to destinations, and (2) enforcement officers aiming to minimize criminals’ long-term success by monitoring and arresting them, using the limited resources at their disposal. Considering several real-world operational details, we first propose a mixed-integer programming model by reformulating a Min–Max bi-level mathematical model. We then propose a new formulation and discuss its efficiency compared with the traditional duality-based reformulation. This new formulation also has a higher compatibility with decomposition solution methods. Utilizing the new formulation, we design a solution method based on the Benders decomposition procedure and apply several accelerating strategies (e.g., Super Valid Inequalities) to solve larger instances for a better representation of reality. Lastly, we create a heuristic method based on real-world evidence, which is usually practiced by law enforcement officers. Our results show that the quality of the heuristic method declines quickly as the network size increases.     

An efficient approach for large scale graph partitioning

In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.     

Computational risk management techniques for fixed charge network flow problems with uncertain arc failures

We consider a formulation for the fixed charge network flow (FCNF) problem subject to multiple uncertain arc failures, which aims to provide a robust optimal flow assignment in the sense of restricting potential losses using Conditional Value-at-Risk (CVaR). We show that a heuristic algorithm referred to as Adaptive Dynamic Cost Updating Procedure (ADCUP) previously developed for the deterministic FCNF problem can be extended to the considered problem under uncertainty and produce high-quality heuristic solutions for large problem instances. The reported computational experiments demonstrate that the described procedure can successfully tackle both the uncertainty considerations and the large size of the networks. High-quality heuristic solutions for problem instances with up to approximately 200,000 arcs have been identified in a reasonable time.     

An exact method for shrinking pivot tables

Pivot tables are one of the most popular tools for data visualization in both business and research applications. Although they are in general easy to use, their comprehensibility becomes progressively lower when the quantity of cells to be visualized increases (i.e., information flooding problem). Pivot tables are largely adopted in OLAP, the main approach to multidimensional data analysis. To cope with the information flooding problem in OLAP, the shrink operation enables users to balance the size of query results with their approximation, exploiting the presence of multidimensional hierarchies. The only implementation of the shrink operator proposed in the literature is based on a greedy heuristic that, in many cases, is far from reaching a desired level of effectiveness.In this paper we propose a model for optimizing the implementation of the shrink operation which considers two possible problem types. The first type minimizes the loss of precision ensuring that the resulting data do not exceed the maximum allowed size. The second one minimizes the size of the resulting data ensuring that the loss of precision does not exceed a given maximum value. We model both problems as set partitioning problems with a side constraint. To solve the models we propose a dual ascent procedure based on a Lagrangian pricing approach, a Lagrangian heuristic, and an exact method. Experimental results show the effectiveness of the proposed approaches, that is compared with both the original greedy heuristic and a commercial general-purpose MIP solver.     

An individual-based model of information diffusion combining friends’ influence

In many real-world scenarios, an individual accepts a new piece of information based on her intrinsic interest as well as friends’ influence. However, in most of the previous works, the factor of individual’s interest does not receive great attention from researchers. Here, we propose a new model which attaches importance to individual’s interest including friends’ influence. We formulate the problem of maximizing the acceptance of information (MAI) as: launch a seed set of acceptors to trigger a cascade such that the number of final acceptors under a time constraint T in a social network is maximized. We then prove that MAI is NP-hard, and for time \(T = 1,2\) , the objective function for information acceptance is sub-modular when the function for friends’ influence is sub-linear in the number of friends who have accepted the information (referred to as active friends). Therefore, an approximation ratio \((1-\frac{1}{e})\) for MAI problem is guaranteed by the greedy algorithm. Moreover, we also prove that when the function for friends’ influence is not sub-linear in the number of active friends, the objective function is not sub-modular.     

Single cycle policies for the one-warehouse N-retailer inventory/distribution system

We address a multi-echelon inventory system with one-warehouse and N  -retailers. The demand at each retailer is assumed to be known and satisfied by the warehouse. Shortages are not allowed and lead times are negligible. Costs at each facility consist of a fixed charge per order and a holding cost. The goal is to determine single-cycle policies which minimize the average cost per unit time, that is, the sum of the average holding and setup costs per unit time at the retailers and at the warehouse. We propose a O(NlogN)$\mathrm{O}(N\log N)$ heuristic procedure to compute efficient single-cycle policies. This heuristic is compared with other approaches proposed by Schwarz, Graves and Schwarz and Muckstadt and Roundy. We carry out a computational study to test the effectiveness of the heuristic and to compare the performance of the different procedures. From the computational results, it is shown that the new heuristic provides, on average, better single-cycle policies than those given by the Muckstadt and Roundy method.     

A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a \(O(k^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.     

α-鲁棒随机截流选址问题的模型和算法

由于选址决策的长期性,相关参数会随着时间而变化,所以选址问题存在很多不确定因素。本文通过不同的情景来处理截流问题中流量的不确定性,并结合随机优化和鲁棒优化,提出α-鲁棒随机截流选址模型。该模型规定了在各情景下的相对后悔值不超过α的条件下,使截得的流量的期望值最大,该条件称为α-鲁棒约束。本文将该模型建立成为一个线性0-1整数规划,并给出了改进型贪婪算法和拉格朗日启发式算法。最后,本文使用这两种算法对不同规模的截流选址问题进行了研究。     

Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.     

Practical implications of the resource-based view

Managers use many decision making tools when developing a firm’s strategic direction. Ideally, such tools yield a good solution for an acceptable amount of application effort. This paper presents the results of an experimental research project that compares the effectiveness of a theory-based strategic decision making tool, theVRIO-framework, with two alternative decision making heuristics for predicting the stock-market performance of different companies. First, we assess how the predictions of theVRIO-framework contrast with decisions based on “gut feeling” using the forecasts derived from a recognition-based decision making tool, theRecognition Heuristic. Secondly, theVRIO-framework’spredictive power is compared to predictions derived fromAnalyst Ratings. Our results suggest that the predictions of theVRIO-framework are superior to those of theRecognition Heuristic and theAnalyst Ratings, supporting the practical usefulness of resource-based theory. We conclude that resource analysis is important to strategic decision making and discuss the implications of our findings for future research and management practice.     

Identifying and Structuring the Objectives of Terrorists

The risk of terrorism is of great concern to many countries and significant resources are spent to counter this threat. A better understanding of the motivation of terrorists and their reasons for selecting certain modes and targets of attack can help improve the decisions to allocate resources in the fight against terrorism. The fundamental question addressed in this article is: “What do terrorists want?” We take the view that terrorists’ preferences for actions are based on their values and beliefs. An important missing piece in our knowledge of terrorists’ preferences is an understanding of their values. This article uses a novel approach to determine these values and state them as objectives, using principles from decision analysis and value‐focused thinking. Instead of interviewing decisionmakers and stakeholders, as would be normal in decision analysis, we extract the values of terrorists by examining their own writings and verbal statements. To illustrate the approach, we extract the values of Al‐Qaeda and structure them in terms of strategic, fundamental, and means objectives. These objectives are interrelated through a means‐ends network. This information is useful for understanding terrorists’ motivations, intent, and likely actions, as well as for developing policies to counter terrorism at its root causes.     

Enabling high-dimensional range queries using <Emphasis Type="Italic">k</Emphasis>NN indexing techniques: approaches and empirical results

Many modern search applications are high-dimensional and depend on efficient orthogonal range queries. These applications span web-based and scientific needs as well as uses for data mining. Although k-nearest neighbor queries are becoming increasingly common due to mobile and geospatial applications, orthogonal range queries in high-dimensional data remain extremely important and relevant. For efficient querying, data is typically stored in an index optimized for either kNN or range queries. This can be problematic when data is optimized for kNN retrieval and a user needs a range query or vice versa. Here, we address the issue of using a kNN-based index for range queries, as well as outline the general computational geometry problem of adapting these systems to range queries. We refer to these methods as space-based decompositions and provide a straightforward heuristic for this problem. Using iDistance as our applied kNN indexing technique, we also develop an optimal (data-based) algorithm designed specifically for its indexing scheme. We compare this method to the suggested naïve approach using real world datasets. The data-based algorithm consistently performs better.     

不对称信息下反恐阻止网络设计

当前，我国面临的恐怖主义威胁日益严峻。为防止境外恐怖分子潜入，政府可设计反恐阻止网络，通过在交通网络中有效地分配例如安检仪器、传感设备等阻断资源，来提前识别和拦截正在潜入的恐怖分子。特别地，考虑信息不对称情形，把阻断资源分为"公开"和"隐蔽"两种类型，并假设恐怖分子观察不到"隐蔽"阻断。主要研究政府应如何同时优化两类阻断方案，才能发挥信息优势，设置"陷阱"并降低袭击分析。首先，将该问题构造为双层规划模型，上层规划是关于政府的阻止网络设计问题，下层规划则是关于恐怖分子的袭击节点选择和入侵路径优化问题。随后，设计一类用改进遗传算法处理上层规划，并结合下层规划直接求解的混合算法。其中，改进体现于杂交算子和变异算子的设计。最后，结合喀什地区进行算例分析，并分析"隐蔽"阻断的作用机理。     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.     

Strategic Learning and the Topology of Social Networks

We consider a group of strategic agents who must each repeatedly take one of two possible actions. They learn which of the two actions is preferable from initial private signals and by observing the actions of their neighbors in a social network. We show that the question of whether or not the agents learn efficiently depends on the topology of the social network. In particular, we identify a geometric “egalitarianism” condition on the social network that guarantees learning in infinite networks, or learning with high probability in large finite networks, in any equilibrium. We also give examples of nonegalitarian networks with equilibria in which learning fails.     

Organizational processes as determinants of information value

Research on the determinants of information value has not explicitly considered whether the type of organizational process participated in by a decisionmaker has an effect on his/her evaluation of information on which the decision is based. Much important managerial activity in organizations is carried on through formal or informal processes such as budgeting and strategic planning. If process differences are significant determinants of the way in which information is valued, the inclusion of this element into the framework for thinking in this area might add considerably to our ability to prescribe appropriate managerial processes as well as to our understanding of differences in the outcomes of decision processes. This empirical study suggests that organizational process type does have a significant effect on the determination of information value in the context of two generic process types (individual, group) that were evaluated in a strategic decisionmaking context.     

Scheduling and the problem of computational complexity

Why is it that the problem of scheduling is so computationally difficult to solve? At last recent developments in modern mathematical complexity theory are providing some insights. The paper describes in essentially non-mathematical terms the computational technique known as the ‘Branch and Bound Method’. This, the best general optimising technique available for scheduling, is also shown to have its limitations. It now appears that efficient computational and optimising algorithms are unlikely ever to be found for all except special cases of the general industrial scheduling problem. It seems that heuristic (rule-of-thumb) methods leading to approximate solutions are likely to offer the only real promise for the future.     

On the online multi-agent O–D <Emphasis Type="Italic">k</Emphasis>-Canadian Traveler Problem

In this article, we present new results on the online multi-agent O–D k-Canadian Traveler Problem, in which there are multiple agents and an input graph with a given source node O and a destination node D together with edge costs such that at most k edges are blocked. The blocked edges are not known a priori and are not recoverable. All of the agents are initially located at O. The objective is to find an online strategy such that at least one of the agents finds a route from the initial location O to a given destination D with minimum total cost. We focus on the case where communication among the agents is limited in the sense that some travelers can both send and receive information while the others can only receive information. We formalize the definition of agents’ intelligence by specifying three levels. We introduce two online strategies which utilize higher levels of agents’ intelligence to provide updated lower bounds to this problem. We show that one of our strategies is optimal in both cases with complete and limited communication in the special case of O–D edge-disjoint graphs and highest level of agents’ intelligence.