A generalized activity network model

In recent years activity networks for projects with both random and deterministic alternative outcomes in key nodes have been considered. The developed control algorithm chooses an optimal outcome direction at every deterministic alternative node which is reached in the course of the project's realization. At each routine decision-making node, the algorithm singles out all the subnetworks (the so-called joint variants) which correspond to all possible outcomes from that node. Decision-making results in determining the optimal joint variant and following the optimal direction up to the next decision-making node. However, such models cover a limited class of alternative networks, namely, only fully-divisible networks which can be subdivided into nonintersecting fragments. In this paper, a more generalized activity network is considered. The model can be applied to a broader spectrum of R&D projects and can be used for all types of alternative networks, for example, for non-divisible networks comprising nodes with simultaneously ‘must follow’, random ‘exclusive OR’ and deterministic ‘exclusive or’ emitters. The branching activities of the third type refer to decision-making outcomes; choosing the optimal outcome is the sole prerogative of the project's management. Such a model is a more universal activity network; we will call it GAAN—Generalized Alternative Activity Network. The problem is to determine the joint variant optimizing the mean value of the objective function subject to restricted mean values of several other criteria. We will prove that such a problem is a NP-complete one. Thus, in general, the exact solution of the problem may be obtained only by looking through all the joint variants on the basis of their proper enumeration. To enumerate the joint variants we will use the lexicographical method in combination with some techniques of discrete optimization. A numerical example will be presented. Various application areas are considered.     

Selection of a representative value function in robust multiple criteria ranking and choice

We introduce the concept of a representative value function in robust ordinal regression applied to multiple criteria ranking and choice problems. The proposed method can be seen as a new interactive UTA-like procedure, which extends the UTA^GMS and GRIP methods. The preference information supplied by the decision maker (DM) is composed of a partial preorder and intensities of preference on a subset of reference alternatives. Robust ordinal regression builds a set of general additive value functions which are compatible with the preference information, and returns two binary preference relations: necessary and possible. They identify recommendations which are compatible with all or at least one compatible value function, respectively. In this paper, we propose a general framework for selection of a representative value function from among the set of compatibles ones. There are a few targets which build on results of robust ordinal regression, and could be attained by a representative value function. In general, according to the interactively elicited preferences of the DM, the representative value function may emphasize the advantage of some alternatives over the others when all compatible value functions acknowledge this advantage, or reduce the ambiguity in the advantage of some alternatives over the others when some compatible value functions acknowledge an advantage and other ones acknowledge a disadvantage. The basic procedure is refined by few extensions. They enable emphasizing the advantage of alternatives that could be considered as potential best options, accounting for intensities of preference, or obtaining a desired type of the marginal value functions.     

A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic

Adaptive large neighborhood search (ALNS) is a useful framework for solving difficult combinatorial optimisation problems. As a metaheuristic, it consists of some components that must be tailored to the specific optimisation problem that is being solved, while other components are problem independent. The literature is sparse with respect to studies that aim to evaluate the relative merit of different alternatives for specific problem independent components. This paper investigates one such component, the move acceptance criterion in ALNS, and compares a range of alternatives. Through extensive computational testing, the alternative move acceptance criteria are ranked in three groups, depending on the performance of the resulting ALNS implementations. Among the best variants, we find versions of criteria based on simulated annealing, threshold acceptance, and record-to-record travel, with a version of the latter being consistently undominated by the others. Additional analyses focus on the search behavior, and multiple linear regression is used to identify characteristics of search behavior that are associated with good search performance.     

Robust ordinal regression for value functions handling interacting criteria

We present a new method called UTA^GMS–INT for ranking a finite set of alternatives evaluated on multiple criteria. It belongs to the family of Robust Ordinal Regression (ROR) methods which build a set of preference models compatible with preference information elicited by the Decision Maker (DM). The preference model used by UTA^GMS–INT is a general additive value function augmented by two types of components corresponding to “bonus” or “penalty” values for positively or negatively interacting pairs of criteria, respectively. When calculating value of a particular alternative, a bonus is added to the additive component of the value function if a given pair of criteria is in a positive synergy for performances of this alternative on the two criteria. Similarly, a penalty is subtracted from the additive component of the value function if a given pair of criteria is in a negative synergy for performances of the considered alternative on the two criteria. The preference information elicited by the DM is composed of pairwise comparisons of some reference alternatives, as well as of comparisons of some pairs of reference alternatives with respect to intensity of preference, either comprehensively or on a particular criterion. In UTA^GMS–INT, ROR starts with identification of pairs of interacting criteria for given preference information by solving a mixed-integer linear program. Once the interacting pairs are validated by the DM, ROR continues calculations with the whole set of compatible value functions handling the interacting criteria, to get necessary and possible preference relations in the considered set of alternatives. A single representative value function can be calculated to attribute specific scores to alternatives. It also gives values to bonuses and penalties. UTA^GMS–INT handles quite general interactions among criteria and provides an interesting alternative to the Choquet integral.     

Solvability criteria for systems of fuzzy relation equations

By solving systems of fuzzy relation equations, qualitative process models can be obtained. To give more information on the solving procedure and to help constructing models, solvability criteria for-systems of fuzzy relation equations are necessary. In this article such criteria will be developed. Both methods are considered. In addition to some ideas on general , the is evaluated in detail. Criteria of practical use will be developed. These criteria will limit the variety of premise intersections to guarantee solvability. Nevertheless, they will still allow to model the significant behaviour of the processes.     

Verbal ordinal classification with multicriteria decision aiding

Professionals in neuropsychology usually perform diagnoses of patients’ behaviour in a verbal rather than in a numerical form. This fact generates interest in decision support systems that process verbal data. It also motivates us to develop methods for the classification of such data. In this paper, we describe ways of aiding classification of a discrete set of objects, evaluated on set of criteria that may have verbal estimations, into ordered decision classes. In some situations, there is no explicit additional information available, while in others it is possible to order the criteria lexicographically. We consider both of these cases. The proposed Dichotomic Classification (DC) method is based on the principles of Verbal Decision Analysis (VDA). Verbal Decision Analysis methods are especially helpful when verbal data, in criteria values, are to be handled. When compared to the previously developed Verbal Decision Analysis classification methods, Dichotomic Classification method performs better on the same data sets and is able to cope with larger sizes of the object sets to be classified. We present an interactive classification procedure, estimate the effectiveness and computational complexity of the new method and compare it to one of the previously developed Verbal Decision Analysis methods. The developed and studied methods are implemented in the framework of a decision support system, and the results of testing on artificial sets of data are reported.     

Bilinear optimization in the analysis of multicriteria problems using criteria importance theory under inexact information about preferences

Exact efficient numerical methods are proposed for solving bilinear optimization problems that arise when various solution variants are compared based on their preferability using an additive value function in the case of interval estimates of the degrees of superiority of certain criteria over others and in the case of interval restrictions on the growth of preferences along the criteria range.     

Structure of multi-criteria decision-making

Multi-criteria decision-making (MCDM) is presented as an eight-stage process of shaping information that satisfies the following criteria. The information should be accessible, differentiable, abstractable, understandable, verifiable, measurable, refinable and usable. For some stages, the decision-advisor should emphasize doing the stage convincingly by carrying out first its technical aspects, then relating to the context of the problem, and finally by taking into account the particular situation of the decision. For others, the decision-advisor should emphasize evincing information from the decision-maker first by relating to the situation of the decision, then seeing it in its context, and finally in its technical aspects. Methods for supporting the first four stages are shown to be personal construct theory for accessing the information, grounded theory for differentiating clusters of constructs, critical realism for abstracting their real meaning, and Nomology to understand how they fit into the criteria tree. An illustration is given.     

Adaptive methods for piecewise polynomial collocation for ordinary differential equations

Various adaptive methods for the solution of ordinary differential boundary value problems using piecewise polynomial collocation are considered. Five different criteria are compared using both interval subdivision and mesh redistribution. The methods are all based on choosing sub-intervals so that the criterion values have (approximately) equal values in each sub-interval. In addition to the main comparison it is shown by example that at least when accuracy is low then equidistribution may not give a unique solution. The main results that using interval size times maximum residual as criterion gives very much better results than using maximum residual itself. It is also shown that a criterion based on a global error estimate while giving very good results in some cases, is unsatisfactory in other cases. The other criteria considered are that given by De Boor and the last Chebyshev series coefficient. AMS subject classification (2000)  65L10, 65L50, 65L60     

On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands

This paper studies how to set the vehicle capacity for traveling Salesman Problems where some of the customer demands are stochastic. The analyses are done for the one-commodity pickup-and-delivery TSP, as this problem also includes the setting of the initial load. The paper first considers feasibility issues. This includes finding the smallest vehicle capacity and some initial load such that a given tour is feasible for all scenarios. Different variants are considered as a function of the time when information becomes available. The paper then analyzes the case where some penalties are paid for routing a tour unable to handle customer demands. Various types of penalties are considered. The paper studies properties of the minimal expected penalty of a given tour, which are then used to provide approaches to find near-optimal tours. Computational results are presented.     

Linearization conditions for regression models with unknown variance parameter

In the case of the nonlinear regression model, methods and procedures have been developed to obtain estimates of the parameters. These methods are much more complicated than the procedures used if the model considered is linear. Moreover, unlike the linear case, the properties of the resulting estimators are unknown and usually depend on the true values of the estimated parameters. It is sometimes possible to approximate the nonlinear model by a linear one and use the much more developed linear methods, but some procedure is needed to recognize such situations. One attempt to find such a procedure, taking into account the requirements of the user, is given in [4], [5], [3], where the existence of an a priori information on the parameters is assumed. Here some linearization criteria are proposed and the linearization domains, i.e. domains in the parameter space where these criteria are fulfilled, are defined. The aim of the present paper is to use a similar approach to find simple conditions for linearization of the model in the case of a locally quadratic model with unknown variance parameter ². Also a test of intrinsic nonlinearity of the model and an unbiased estimator of this parameter are derived.     

基于模糊层次分析的虚拟企业风险评价

在分析虚拟企业风险评价应该考虑的主要因素的基础上,建立了一套适用于虚拟企业风险评价的指标体系,提出了一种基于模糊集合理论与层次分析法相结合的虚拟企业风险评价方法。在多专家指标权重评价的基础上,运用模糊D elph i法对上层准则形成一系列的权重集合,得到三角模糊数表示的准则“重要性”评价。结合以模糊语言变量表示的备选方案偏好等级的“满意度”和下层指标的模糊权重,通过分层结合,得到虚拟企业风险的模糊评分,最后采用重心法和Chang Jing-rong的双系数法对所有方案的三角模糊数进行排序,得到虚拟企业方案综合选择的优先顺序。实例说明了虚拟企业风险评价的具体过程。     

Stochastic multiobjective acceptability analysis for the Choquet integral preference model and the scale construction problem

The Choquet integral preference model is adopted in Multiple Criteria Decision Aiding (MCDA) to deal with interactions between criteria, while the Stochastic Multiobjective Acceptability Analysis (SMAA) is an MCDA methodology considered to take into account uncertainty or imprecision on the considered data and preference parameters. In this paper, we propose to combine the Choquet integral preference model with the SMAA methodology in order to get robust recommendations taking into account all parameters compatible with the preference information provided by the Decision Maker (DM). In case the criteria are on a common scale, one has to elicit only a set of non-additive weights, technically a capacity, compatible with the DM’s preference information. Instead, if the criteria are on different scales, besides the capacity, one has to elicit also a common scale compatible with the preferences given by the DM. Our approach permits to explore the whole space of capacities and common scales compatible with the DM’s preference information.     

The SIR method: A superiority and inferiority ranking method for multiple criteria decision making

In this paper, a superiority and inferiority ranking (SIR) method is proposed. This new method uses two types of information, the superiority and the inferiority information, to derive two types of flows, the superiority flow and the inferiority flow, by which the set of alternatives are ranked partially or completely. Relationships between the SIR method and some of the classical multiple criteria decision making (MCDM) methods (such as SAW, TOPSIS and PROMETHEE) are explored. It is proved that the SIR method is a significant extension of the well-known PROMETHEE method.     

On the extent analysis method for fuzzy AHP and its applications

In a paper by Chang [D.Y. Chang, Applications of the extent analysis method on fuzzy AHP, European Journal of Operational Research 95 (1996) 649–655], an extent analysis method on fuzzy AHP was proposed to obtain a crisp priority vector from a triangular fuzzy comparison matrix. It is found that the extent analysis method cannot estimate the true weights from a fuzzy comparison matrix and has led to quite a number of misapplications in the literature. In this paper, we show by examples that the priority vectors determined by the extent analysis method do not represent the relative importance of decision criteria or alternatives and that the misapplication of the extent analysis method to fuzzy AHP problems may lead to a wrong decision to be made and some useful decision information such as decision criteria and fuzzy comparison matrices not to be considered. We show these problems to avoid any possible misapplications in the future.     

The stable marriage problem with master preference lists

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.     

On the Existence of Focal Points near Closed Geodesics on Surfaces

We establish some criteria for the existence or nonexistence of focal points near closed geodesics on surfaces. These criteria are in terms of the curvature of the manifold along the closed geodesic and the average values of the partial derivatives of the curvature in the direction perpendicular to the geodesic. Our criteria lead to a new family of examples of surfaces with no focal points. We also show that if S is a compact surface with no focal points and an inequality relating the curvature of the surface to the curvature of the horocycles holds, then the horocycles (considered as curves in S) are uniformly C ^2+Lipschitz.     

On the complexity of some quadratic Euclidean 2-clustering problems

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).     

Optimal control of assignment of jobs to processors under heavy traffic

The paper is concerned with the optimal control of the assignment of jobs from several arriving random streams to one of a bank of processors. Owing to the difficulty of the general problem, a heavy traffic approach is used. The required work depends on the processor to which it is assigned. The information that the assignment can be based on is quite flexible, and several information structures (data on which the control is based) are considered. The assignment can be made on arrival or when the job is to be processed. There can be bursty arrivals (the bursts depending on randomly varying environmental factors), rather general nonlinear cost functions and other complications. It is shown, under reasonably general conditions, that the optimal costs for the physical systems converge to the optimal cost for the heavy traffic limit problem, as the heavy traffic parameter goes to its limit. Numerical data is presented to illustrate some of the potential uses of the limit process for obtaining optimal contros, or controls satisfying optimal tradeoffs among competing criteria. The methods of proof are quite powerful tools for such optimal control problems