A matrix approach to status quo analysis in the graph model for conflict resolution

An algebraic method is developed to carry out status quo analysis within the framework of the graph model for conflict resolution. As a form of post-stability analysis, status quo analysis aims at confirming that possible equilibria, or states stable for all decision-makers, are in fact reachable from the status quo or any other initial state. Although pseudo-codes for status quo analysis have been developed, they have never been implemented within a practical decision support system. The novel matrix approach to status quo analysis designed here is convenient for computer implementation and easy to employ, as is illustrated by an application to a real-world conflict case. Moveover, the proposed explicit matrix approach reveals an inherent link between status quo analysis and the traditional stability analysis and, hence, provides the possibility of establishing an integrated paradigm for stability and status quo analyses.     

A matrix-based approach to searching colored paths in a weighted colored multidigraph

An algebraic approach to finding all edge-weighted-colored paths within a weighted colored multidigraph is developed. Generally, the adjacency matrix represents a simple digraph and determines all paths between any two vertices, and is not readily extendable to colored multidigraphs. To bridge the gap, a conversion function is proposed to transform the original problem of searching edge-colored paths in a colored multidigraph to a standard problem of finding paths in a simple digraph. Moreover, edge weights can be used to represent some preference attribute. Its potentially wide realm of applicability is illustrated by a case study: status quo analysis in the graph model for conflict resolution. The explicit matrix function is more convenient than other graphical representations for computer implementation and for adapting to other applications. Additionally, the algebraic approach reveals the relationship between a colored multidigraph and a simple digraph, thereby providing new insights into algebraic graph theory.     

Status quo analysis in the graph model for conflict resolution

The graph model for conflict resolution, an analysis paradigm for strategic conflicts, has mainly relied on stability analysis for its conclusions. This paper proposes algorithms to apply another analysis technique, status quo analysis, to a graph model. Status quo analysis is dynamic and forward-looking, in contrast to Stability Analysis, which is static and contingent. Status quo analysis is carried out by means of a directed graph that tracks moves and countermoves from a status quo state, and a table that records the reachability status of states from the status quo. Different algorithms are proposed to produce status quo diagrams with and without restrictions on moves; more efficient versions of the algorithm for the case of transitive graphs are also put forward. Properties of diagrams generated by different algorithms are investigated. A case study illustrates how status quo analysis can be applied, and how it interacts with other analysis methodologies.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

An integrated algebraic approach to conflict resolution with three-level preference

An integrated algebraic approach is developed to calculate stabilities in multiple decision maker graph models with three levels of preference. The algebraic approach establishes an integrated paradigm for stability analysis and status quo analysis under different preference structures, such as two-level preference and three-level preference. Difficulties in coding algorithms to analyze stabilities, rooted in their logical representation, led to the development of matrix representations of preference and explicit matrix calculations to determine stabilities. Here, the algebraic approach is used to represent graph models with three levels of preference and to conduct stability analysis for such models. The algebraic approach facilitates the development of new stability concepts and algorithms to calculate them, and reveals an inherent link between status quo analysis and traditional stability analysis. Hence, it will facilitate the design of an integrated decision support system for the graph model for conflict resolution.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.     

Semirings and path spaces

This paper develops a unified algebraic theory for a class of path problems such as that of finding the shortest or, more generally, the k shortest paths in a network; the enumeration of elemementary or simple paths in a graph. It differs from most earlier work in that the algebraic structure appended to a graph or a network of a path problem is not axiomatically given as a starting point of the theory, but is derived from a novel concept called a “path space”. This concept is shown to provide a coherent framework for the analysis of path problems, and hence the development of algebraic methods for solving them.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

解一般TSP问题的并行算法

任何连通的带权图均有ＴＳＰ的解．本文用图的最短路径矩阵代替加权邻接矩阵，使所有带权图，ＨＰ模型都能够接受．由于采用并行算法，可以较快获得问题的最优解．     

基于分段策略评分的冲突主体偏好排序方法及其应用

冲突中各利益主体的偏好信息对冲突局势的演变和纠纷调解具有重要影响。现有的冲突偏好排序方法主要基于决策者对冲突局势或状态、策略权重和声明信息的主观判断和理解,缺乏科学的数据来源支撑。为准确获取冲突主体的偏好信息,本文提出了一种基于调查法的分段策略冲突偏好排序方法。首先,根据决策者类别将冲突策略集合进行分段,并通过问卷、调研等方法获取每个冲突主体对所有分段策略的重要度评分信息。在此基础上,计算决策者对各个冲突状态的综合偏好评分,进而得到状态偏好的排序结果。最后以医患纠纷为例,对比分析了传统策略权重法和分段策略评分法的偏好排序和稳定性分析结果,进一步验证了所提方法的有效性。     

Dijkstra’s algorithm and L-concave function maximization

Dijkstra’s algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra’s algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra’s algorithm.     

Interval fuzzy preferences in the graph model for conflict resolution

A new analysis technique, appropriate to situations of high preference uncertainty, is added to the graph model for conflict resolution methodology. Interval fuzzy stabilities are now formulated, based on decision makers’ (DMs’) interval fuzzy preferences over feasible scenarios or states in a conflict. Interval fuzzy stability notions enhance the applicability of the graph model, and generalize its crisp and fuzzy preference-based stability ideas. A graph model is both a formal representation and an analysis procedure for multiple participant-multiple objective decisions that employs stability concepts representing various forms of human behavior under conflict. Defined based on a type-2 fuzzy logic, an interval fuzzy preference for one state over another is represented by a subinterval of [0, 1] indicating an interval-valued preference degree for the first state over the second. The interval fuzzy stabilities put forward in this research are interval fuzzy Nash stability, interval fuzzy general metarational stability, interval fuzzy symmetric metarational stability, and interval fuzzy sequential stability. A state is interval fuzzy stable for a DM if moving to any other state is not adequately desirable to the DM; where adequacy is measured by the interval fuzzy satisficing threshold of the DM and farsightedness, involving possible moves and countermoves by DMs, is determined by the interval fuzzy stability notion selected. Note that infinitely many degrees in an interval-valued preference are preserved in characterizing the desirability of a move. A state from which no DM can move to any sufficiently desirable scenario is an interval fuzzy equilibrium, and is interpreted as a possible resolution of the strategic conflict under study. The new stability concept is illustrated through its application to an environmental conflict that took place in Elmira, Ontario, Canada. Insightful results are identified and discussed.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

Reliability function of a class of time-dependent systems with standby redundancy

By applying shortest path analysis in stochastic networks, we introduce a new approach to obtain the reliability function of time-dependent systems with standby redundancy. We assume that not all elements of the system are set to function from the beginning. Upon the failure of each element of the active path in the reliability graph, the system switches to the next path. Then, the corresponding elements are activated and consequently the connection between the input and the output is established. It is also assumed each element exhibits a constant hazard rate and its lifetime is a random variable with exponential distribution. To evaluate the system reliability, we construct a directed stochastic network called E-network, in which each path corresponds with a minimal cut of the reliability graph. We also prove that the system failure function is equal to the density function of the shortest path of E-network. The shortest path distribution of this new constructed network is determined analytically using continuous-time Markov processes.     

Fuzzy graphs modelling for HazMat telegeomonitoring

Telegeomonitoring system development combines two heterogeneous technologies: the geographical information systems technology (GIS) and telecommunications technology. In this paper, we give the system components for telegeomonitoring transportation of hazardous materials. The telegeomonitoring system uses GIS to capture civil infrastructure (urban network, land use, industries, etc.) and decision support systems technology to allow risks analysis and evaluate routing strategies that minimize transportation risk. Routing algorithms are to this effect adapted to graphs of the fuzzy risk. A new algebraic structure is proposed to solve a path-finding problem in a fuzzy graph. This algebraic structure is adapted precisely to solve the problem of the K-best fuzzy shortest paths. The approach that we proposed, consists of defining generic structures of operator’s traversal problem in fuzzy graphs. The principal contribution of our approach is to build adequate structures of path algebra to solve the problem of graph traversal in a fuzzy graph without negative circuits. Foundations of the system studied in this work will be able to be transposed to other fields of transportation.     

网络最短的最优解集结构

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.     

突发事件中对嫌疑犯有效封堵的模型与算法

基于CUMCM-2011 B题中关于嫌疑犯的封堵问题的研究.通过建立描述市区交通网络图的权矩阵,采用求最短路的Dijstra算法求出市区任意两节点的最短路径及路长,构作最佳路径阵和距离矩阵,以此为基点建立封堵路口的最优调度方案模型,再在此基础上建立封堵住嫌疑犯的最优模型,并设计了模型求解的算法.将算法应用于CUMCM-2011 B题中关于嫌疑犯的封堵问题,获得最优封堵方案.     

Solving the shortest path tour problem

In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.