Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

A new multicriteria approach for the analysis of efficiency in the Spanish olive oil sector by modelling decision maker preferences

The efficiency in production is often analysed as technical efficiency using the production frontier function. Efficiency scores are usually based on distance computations to the frontier in an m + s-dimensional space, where m inputs produce s outputs. In addition, efficiency improvements consider the total consumption of each input. However, in many cases, the “consumption” of each input can be divided into input-consumption sections (ICSs), and trade-off among the ICSs is possible. This share framework can be used for computing efficiency. This analysis provides information about both the total optimal consumption of each input, as does data envelopment analysis, and the most efficient allocation of the “consumption” among the ICSs. This paper studies technical efficiency using this approach and applies it to the olive oil sector in Andalusia (Spain). A non-parametrical methodology is presented, and an input-oriented Multi-Criteria Linear Programming model (MLP) is proposed. The analysis is developed at global, input and ICSs levels, defining the extent of satisfaction achieved at all these levels for each company, in accordance with their own preferences. The companies’ preferences are modelled with their utility function and their set of weights. MLP offers more detailed information to assist decision makers than other models previously proposed in the literature. In addition to this application, it is concluded that there is room for improvement in the olive oil sector, particularly in the management of the skilled labour. Additionally, the solutions with two opposite scenarios indicate that the model is suitable for the intended decision making process.     

Separated and Connected Maps

Using on the one hand closure operators in the sense of Dikranjan and Giuli and on the other hand left- and right-constant subcategories in the sense of Herrlich, Preuß, Arhangel'skii and Wiegandt, we apply two categorical concepts of connectedness and separation/disconnectedness to comma categories in order to introduce these notions for morphisms of a category and to study their factorization behaviour. While at the object level in categories with enough points the first approach exceeds the second considerably, as far as generality is concerned, the two approaches become quite distinct at the morphism level. In fact, left- and right-constant subcategories lead to a straight generalization of Collins' concordant and dissonant maps in the category of topological spaces. By contrast, closure operators are neither able to describe these types of maps in , nor the more classical monotone and light maps of Eilenberg and Whyburn, although they give all sorts of interesting and closely related types of maps. As a by-product we obtain a negative solution to the ten-year-old problem whether the Giuli–Huek Diagonal Theorem holds true in every decent category, and exhibit a counter-example in the category of topological spaces over the 1-sphere.     

Regularity of d-measure

The modified lower box dimension can be redefined in terms of the d-measure [4]. In this note we prove a decomposition theorem for this measure and show that strong regularity can be interpreted as this d-measure regularity in Rⁿ. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some Results for Large Closed Queueing Networks with and without Bottleneck: Up- and Down-Crossings Approach

The paper provides the up- and down-crossing method to study the asymptotic behavior of queue-length and waiting time in closed Jackson-type queueing networks. These queueing networks consist of central node (hub) and k single-server satellite stations. The case of infinite server hub with exponentially distributed service times is considered in the first section to demonstrate the up- and down-crossing approach to such kind of problems and help to understand the readers the main idea of the method. The main results of the paper are related to the case of single-server hub with generally distributed service times depending on queue-length. Assuming that the first k–1 satellite nodes operate in light usage regime, we consider three cases concerning the kth satellite node. They are the light usage regime and limiting cases for the moderate usage regime and heavy usage regime. The results related to light usage regime show that, as the number of customers in network increases to infinity, the network is decomposed to independent single-server queueing systems. In the limiting cases of moderate usage regime, the diffusion approximations of queue-length and waiting time processes are obtained. In the case of heavy usage regime it is shown that the joint limiting non-stationary queue-lengths distribution at the first k–1 satellite nodes is represented in the product form and coincides with the product of stationary GI/M/1 queue-length distributions with parameters depending on time.     

Modeling factions for “effects based operations”: part I—leaders and followers

This paper presents a synthetic approach for generating role playing simulation games intended to support analysts (and trainees) interested in testing alternative competing courses of action (operations) and discovering what effects they are likely to precipitate in potential ethno-political conflict situations. Simulated leaders and followers capable of playing these games are implemented in a cognitive modeling framework, called PMFserv, which covers value systems, personality and cultural factors, emotions, relationships, perception, stress/coping style and decision making. Of direct interest, as Sect. 1.1 explains, is mathematical representation and synthesis of best-of-breed behavioral science models within this framework to reduce dimensionality and to improve the realism and internal validity of the agent implementations. Sections 2 and 3 present this for leader profiling instruments and group membership decision-making, respectively. Section 4 serves as an existence proof that the framework has generated several training and analysis tools, and Sect. 5 concludes with lessons learned. Part II turns to the question of assessment of the synthesis and its usage in course of action studies.

Small quasimultiple affine and projective planes: Some improved bounds

We improve the known bounds on r(n): = min {λ| an (n², n, λ)-RBIBD exists} in the case where n + 1 is a prime power. In such a case r(n) is proved to be at most n + 1. If, in addition, n − 1 is the product of twin prime powers, then r(n) ${\ \le \ }{n \over 2}$. We also improve the known bounds on p(n): = min{λ| an (n² + n + 1, n + 1, λ)-BIBD exists} in the case where n² + n + 1 is a prime power. In such a case p(n) is bounded at worst by but better bounds could be obtained exploiting the multiplicative structure of GF(n² + n + 1). Finally, we present an unpublished construction by M. Greig giving a quasidouble affine plane of order n for every positive integer n such that n − 1 and n + 1 are prime powers. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 337–345, 1998     

On a decomposition for infinite transition matrices

Heyman gives an interesting factorization of I-P, where P is the transition probability matrix for an ergodic Markov chain. We show that this factorization is valid if and only if the Markov chain is recurrent. Moreover, we provide a decomposition result which includes all ergodic, null recurrent as well as the transient Markov chains as special cases. Such a decomposition has been shown to be useful in the analysis of queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

The dial-a-ride problem: models and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pickup and delivery requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and a summary of the most important models and algorithms is provided. This is an updated version of a paper that appeared in 4OR 1:89–101, 2003.     

Parallel branch, cut, and price for large-scale discrete optimization

In discrete optimization, most exact solution approaches are based on branch and bound, which is conceptually easy to parallelize in its simplest forms. More sophisticated variants, such as the so-called branch, cut, and price algorithms, are more difficult to parallelize because of the need to share large amounts of knowledge discovered during the search process. In the first part of the paper, we survey the issues involved in parallelizing such algorithms. We then review the implementation of SYMPHONY and COIN/BCP, two existing frameworks for implementing parallel branch, cut, and price. These frameworks have limited scalability, but are effective on small numbers of processors. Finally, we briefly describe our next-generation framework, which improves scalability and further abstracts many of the notions inherent in parallel BCP, making it possible to implement and parallelize more general classes of algorithms. Mathematics Subject Classification (1991):65K05, 68N99, 68W10, 90-04, 90-08, 90C06, 90C09, 90C10, 90C11, 90C57     

D3-Modules

A right R-module M is called a D3-module, if M ₁ and M ₂ are direct summands of M with M = M ₁ + M ₂, then M ₁ ∩ M ₂ is a direct summand of M. Following the work of Bass on projective covers, we introduce the notion of D3-covers and provide new characterizations of several well-known classes of rings in terms of D3-modules and D3-covers.     

On the sum of superoptimal singular values

In this paper, we study the following extremal problem and its relevance to the sum of the so-called superoptimal singular values of a matrix function: Given an m×n matrix function Φ, when is there a matrix function Ψ_∗ in the set such that

     

Instrumenting Mathematical Activity: Reflections on Key Studies of the Educational Use of Computer Algebra Systems

This paper examines the process through which students learn to make functional use of computer algebra systems (CAS), and the interaction between that process and the wider mathematical development of students. The result of ‘instrumentalising‘ a device to become a mathematical tool and correspondingly ‘instrumenting’ mathematical activity through use of that tool is not only to extend students' mathematical technique but to shape their sense of the mathematical entities involved. These ideas have been developed within a French programme of research – as reported by Artigue in this issue of the journal – which has explored the integration of CAS – typically in the form of symbolic calculators – into the everyday practice of mathematics classrooms. The French research –influenced by socio-psychological theorisation of the development of conceptual systems- seeks to take account of the cultural and cognitive facets of these issues, noting how mathematical norms – or their absence – shape the mental schemes which students form as they appropriate CAS as tools. Instrumenting graphic and symbolic reasoning through using CAS influences the range and form of the tasks and techniques experienced by students, and so the resources available for more explicit codification and theorisation of such reasoning. This illuminates an influential North American study– conducted by Heid – which French researchers have seen as taking a contrasting view of the part played by technical activity in developing conceptual understanding. Reconsidered from this perspective, it appears that while teaching approaches which ‘resequence skills and concepts’ indeed defer – and diminish –attention to routinised skills, the tasks introduced in their place depend on another –albeit less strongly codified – system of techniques, supporting more extensive and active theorisation. The French research high lights important challenges which arise in instrumenting classroom mathematical activity and correspondingly instrumentalising CAS. In particular, it reveals fundamental constraints on human-machine interaction which may limit the capacity of the present generation of CAS to scaffold the mathematical thinking and learning of students. This revised version was published online in July 2006 with corrections to the Cover Date.     

Nominal and robust train timetabling problems

In this paper we survey the main studies dealing with the train timetabling problem in its nominal and robust versions. Roughly speaking, the nominal version of the problem amounts of determining “good” timetables for a set of trains (on a railway network or on a single one-way line), satisfying the so-called track capacity constraints, with the aim of optimizing an objective function that can have different meanings according to the requests of the railway company (e.g. one can be asked to schedule the trains according to the timetables preferred by the train operators or to maximize the passenger satisfaction). Two are the main variants of the nominal problem: one is to consider a cyclic (or periodic) schedule of the trains that is repeated every given time period (for example every hour), and the other one is to consider a more congested network where only a non-cyclic schedule can be performed. In the recent years, many works have been dedicated to the robust version of the problem. In this case, the aim is to determine robust timetables for the trains, i.e. to find a schedule that avoids, in case of disruptions in the railway network, delay propagation as much as possible. We present an overview of the main works on train timetabling, underlining the differences between models and methods that have been developed to tackle the nominal and the robust versions of the problem.     

Symmetries on random arrays and set-indexed processes

A processX on the setÑ of all finite subsetsJ ofN is said to be spreadable, if for all subsequencesp=(p ₁,p ₂,...) ofN, wherepJ={p _j ;jJ}. Spreadable processes are characterized in this paper by a representation formula, similar to those obtained by Aldous and Hoover for exchangeable arrays of r.v.'s. Our representation is equivalent to the statement that a process onÑ is spreadable, iff it can be extended to an exchangeable process indexed by all finite sequences of distinct elements fromN. The latter result may be regarded as a multivariate extension of a theorem by Ryll-Nardzewski, stating that, for infinite sequences of r.v.'s, the notions of exchangeability and spreadability are equivalent.     

The Dial-a-Ride Problem (DARP): Variants,modeling issues and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pick-up and drop-off requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and classified and some modeling issues are discussed. A summary of the most important algorithms is provided.AMS classification: 90B06, 90C27, 90C59     

Temperley-Lieb planar algebra modules arising from the ADE planar algebras

A Hilbert module over a planar algebra P is essentially a Hilbert module over a canonically defined algebra spanned by the annular tangles in P. It follows that any planar algebra Q containing P is a module over P, and in particular, any subfactor planar algebra is a module over the Temperley-Lieb planar algebra with the same modulus. We describe a positivity result that allows us to describe irreducible Temperley-Lieb planar algebra modules, and apply the result to decompose the planar algebras determined by the Coxeter graphs A_n (n?3), D_n (n?4), E₆, E₇, and E₈.