Multiple objectives decomposition–coordination methods for hierarchical organizations

In this paper, the integration of goal programming models and hierarchical programming models is analyzed. The systems under study are assumed to consist of interconnected subsystems with multiple goals in each. Three possible cases regarding the number of decision makers will be considered: (1) one decision maker for the overall goals and one decision maker for each subsystem, (2) conflicting decision makers who are interested in their subsystems, and (3) just one decision maker for the overall system. Next, conditions are stated under which the problem of obtaining satisfying solutions for problems (1) and (3) can be reduced to the problem of obtaining satisfying solutions for the case (2). In order to determine such solutions, hierarchical techniques which exploit the structure of a decomposable system are analyzed. The empirical implementation of the two algorithms proposed shows their efficiency in terms of processing time.     

基于决策者选择偏好的网络DEA模型——以我国若干家商业银行为例

本文从决策者选择偏好的角度构建了一类两阶段链形系统的关联网络DEA模型,用于测算系统以及各阶段的纯技术效率.并从理论上证明了系统DEA有效的充分必要条件是链上的每个子过程都是DEA有效的.结合我国商业银行的特点,将银行运营过程分为存款过程和投资过程,根据建立的三种选择偏好模型,测算了我国13家商业银行2007年的系统效率及其两个运营过程的纯技术效率,分析出了各商业银行运营无效率的内在原因.     

Measuring teaching efficiency in higher education: An application of data envelopment analysis to economics graduates from UK Universities 1993

Data envelopment analysis (DEA) is applied to 2547 Economics graduates from UK Universities in 1993 in order to assess teaching efficiency. Following a methodology developed by [Education Economics 10(2) (2002) 183–207], each individual’s efficiency is decomposed into two components: one attributable to the university at which the student studied, and the other attributable to the student himself. From the former component, a measure of each institution’s teaching efficiency is derived and compared to efficiency scores derived from a conventional DEA applied using each Economics department as a decision making unit (DMU). The results suggest that efficiencies derived from DEAs performed at an aggregate level include both institution and individual components, and are therefore misleading. Thus the unit of analysis in a DEA is highly important. Moreover, an analysis at the individual level can give institutions insight into whether it is the students’ own efforts or the institution’s efficiency which are a constraint on increased efficiency. This has implications for the choice of strategy for improving efficiency.     

Efficiency decomposition for parallel production systems

For production systems composed of parallel processes, the system efficiency will more properly represent the aggregate performance of the component processes if the operation of each process is taken into consideration. Several approaches have been proposed for measuring the efficiency of parallel production systems. By requiring the same factor to have the same virtual multiplier, the proposed method is able to calculate the system and process efficiencies at the same time. Moreover, the former can be decomposed into a weighted average of the latter. A system is efficient only if all of its component processes are efficient. Chemistry departments in the UK are used as an example, where teaching and research are two major functions of the department. The relationship between the system and process efficiencies which holds for the case of constant returns to scale can be extended to the case of variable returns to scale.

     

Three-stage recursive least squares parameter estimation for controlled autoregressive autoregressive systems

A three-stage recursive least squares parameter estimation algorithm is derived for controlled autoregressive autoregressive (CARAR) systems. The basic idea is to decompose a CARAR system into three subsystems, one of which contains one parameter vector, and to identify the parameters of each subsystem one by one. Compared with the recursive generalized least squares algorithm, the dimensions of the involved covariance matrices in each subsystem become small and thus the proposed algorithm has a high computational efficiency. Finally, we verify the proposed algorithm with a simulation example.     

The number of feasible designs in a compatibility matrix

Many design and planning problems consist of a number of distinct subsystems. Generally, there are several possible alternatives for design of a subsystem. However, an alternative for one subsystem may be incompatible with an alternative for another subsystem. Thus, a feasible design is one that incorporates one alternative for each subsystem such that no pairwise incompatibilities exist. Several such design and planning problems have been formulated as compatibility matrices. The feasible designs can be identified by using an efficient algorithm. This paper shows that, in general, the exact number of feasible designs decreases exponentially with the increase in the number of incompatible pairs. This finding should motivate more potential users to employ the compatibility matrix approach.     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

Pareto efficiency in locally convex spaces II: Stability results

In this second part of our work on Pareto efficiency we study the stability of the set of efficient points under perturbations of the data. For that purpose we use a general notion of convergence of sets which is known as the Kuratowski-Mosco convergence. We also determine the properties of Eff_K(S) as a function of the set S and of the dominance cone K. Finally our work is extended to stochastic Pareto efficiency and we derive several stability results, we determine the measurability of the efficiency multifunction and we obtain a new characterization of the efficient points of the aggregate set.     

有向网络下多个体系统的整体行为

研究非时变有向通讯网络背景下一阶线性多个体动力学系统的整体行为.根据通讯网络的结构,系统可以区分为独立基本子系统和非独立基本子系统.当系统的控制规则为一类平凡的线性类型时,系统的独立基本子系统将趋于自身的一致状态,也即子系统中的每个个体趋于子系统的带权中心.独立基本子系统带权中心由子系统的系数矩阵的零特征根归一化左特征向量确定.非独立子系统中个体将趋于独立基本子系统带权中心的凸集内.当且仅当系统的独立基本子系统唯一时,系统实现一致性行为.     

A non-radial measure of different systems for Taiwanese tourist hotels’ efficiency assessment

The literature assumes that Taiwan’s international tourist hotels have identical frontier technology to evaluate non-radial efficiencies, even if they characterize different operating types. This study develops a non-radial systems model, for which the different operating types are evaluated based on different frontier technologies in order to calculate efficiencies. Compared to the radial systems model, the new model is able to practice two verifications. First, efficient units can be separated into strong and weak efficient sets. The second finds the benchmark among the different types for each input and output. The empirical results show that most efficient units reflect strong efficiency while only one hotel reflects weak efficiency. Inefficient hotels should refer to the chain type in order to improve excess utilizations in employees, rooms, catering space, and revenue deficits. For improving excess operating expenses and occupancy rate deficits, inefficient hotels should refer to the independent type.     

Adaptive partitioning techniques for ordinary differential equations

Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05     

Evaluation of the local error of fractional-rational multistep methods with variable integration step

To ensure the proper qualitative characteristic of approximate numerical solution of the Cauchy problem for a system of ordinary differential equations, it is necessary to formulate certain conditions that have to be satisfied by numerical methods. The efficiency of a numerical method is determined by constructing the algorithm of integration step changing and the choice of the order of the method. The construction of such a method requires one to determine preliminarily the admissible error of the method in each integration step. A theorem on the evaluation of the local error of multistep numerical p th-order methods with variable integration step without taking into account the round-off error is formulated. This theorem enables one to construct an efficient algorithm for the step change and the choice of the corresponding order of the method.     

The Waveform Relaxation method for systems of differential/algebraic equations

This paper reports efforts towards establishing a parallel numerical algorithm known as Waveform Relaxation (WR) for simulating large systems of differential/algebraic equations. The WR algorithm was established as a relaxation based iterative method for the numerical integration of systems of ODEs over a finite time interval. In the WR approach, the system is broken into subsystems which are solved independently, with each subsystem using the previous iterate waveform as “guesses” about the behavior of the state variables in other subsystems. Waveforms are then exchanged between subsystems, and the subsystems are then resolved repeatedly with this improved information about the other subsystems until convergence is achieved.

In this paper, a WR algorithm is introduced for the simulation of generalized high-index DAE systems. As with ODEs, DAE systems often exhibit a multirate behavior in which the states vary as differing speeds. This can be exploited by partitioning the system into subsystems as in the WR for ODEs. One additional benefit of partitioning the DAE system into subsystems is that some of the resulting subsystems may be of lower index and, therefore, do not suffer from the numerical complications that high-index systems do. These lower index subsystems may therefore be solved by less specialized simulations. This increases the efficiency of the simulation since only a portion of the problem must be solved with specially tailored code. In addition, this paper established solvability requirements and convergence theorems for varying index DAE systems for WR simulation.     

Analysis of multistation production systems with limited buffer capacity part 2: The decomposition method

We seek efficient techniques to evaluate the performance of multistation production systems with limited interstation buffers and station breakdown. Our ultimate objective is to develop a practical computer implementation that can be used for analysis and design. A flexible decomposition framework is developed. This approach allows the analysis of multistation production systems with various structures including series arrangements, network topologies, and rework (feedback) systems. The efficient solution techniques for the subsystems developed in Part 1 are used at each iteration of the decomposition method. It is the generality and efficiency of the subsystem model as well as the flexibility and robustness of the decomposition approach that distinguish our study from earlier work.     

Equity portfolio construction and selection using multiobjective mathematical programming

A multi-objective mixed integer programming model for equity portfolio construction and selection is developed in this study, in order to generate the Pareto optimal portfolios, using a novel version of the well known ε-constraint method. Subsequently, an interactive filtering process is also proposed to assist the decision maker in making his/her final choice among the Pareto solutions. The proposed methodology is tested through an application in the Athens Stock Exchange.     

Optimal control of impulsive switched systems with minimum subsystem durations

This paper presents a new computational approach for solving optimal control problems governed by impulsive switched systems. Such systems consist of multiple subsystems operating in succession, with possible instantaneous state jumps occurring when the system switches from one subsystem to another. The control variables are the subsystem durations and a set of system parameters influencing the state jumps. In contrast with most other papers on the control of impulsive switched systems, we do not require every potential subsystem to be active during the time horizon (it may be optimal to delete certain subsystems, especially when the optimal number of switches is unknown). However, any active subsystem must be active for a minimum non-negligible duration of time. This restriction leads to a disjoint feasible region for the subsystem durations. The problem of choosing the subsystem durations and the system parameters to minimize a given cost function is a non-standard optimal control problem that cannot be solved using conventional techniques. By combining a time-scaling transformation and an exact penalty method, we develop a computational algorithm for solving this problem. We then demonstrate the effectiveness of this algorithm by considering a numerical example on the optimization of shrimp harvesting operations.     

Group technology in production management: The short horizon planning level

We consider a set of parts divided into subsets called part types, determined in such a way that the parts belonging to the same part type are manufactured using the same sequence of tasks (i.e. the same working process). We are looking for a partition of the set of part types into subsets called part families, and for a partition of the set of tasks into subsets called production subsystems defined as follows: (1) the number of part families and the number of production subsystems are equal, (2) one (one only one) production subsystem corresponds to each part family, (3) one (and only one) part family corresponds to each production subsystem, (4) the previous partitions minimize the number of tasks performed in a production subsystem different from that which corresponds to the part family containing the part involved. We give a fast algorithm which leads to a good solution depending on the initial set of part families. We also propose an algorithm to find a ‘good’ initial set of part families.     

A numerical algorithm for some singularly perturbed boundary value problems

A numerical algorithm is proposed to solve singularly perturbed linear two-point value problems. The method starts with a partial decoupling of the system to obtain two independent subsystems, fast and slow components. Each subsystem is then solved separately. A second-order finite difference scheme is used for this purpose. Numerical examples will be presented to show the efficiency of the method.     

Interval DEA模型中决策单元的投影问题

在传统的DEA模型中,最优相对效率模型是在不大于1的范围内研究决策单元的效率的,最差相对效率模型是在不小于1的范围内研究决策单元的效率,这两种模型在研究投影问题时,是在不同的范围内进行的,有一定的片面性.将在interval DEA模型中,研究决策单元的投影问题,该模型是在相同的约束域内研究最优和最差相对效率模型,得出的结论将更加全面,通过两个定理给出了非DEA有效的决策单元在DEA有效面上的投影表达式和非DEA无效的决策单元在DEA无效面上的投影表达式.同时,通过一个实例对决策单元在interval DEA模型中的投影结果与在传统的DEA模型的投影结果进行了比较,发现投影结果比传统模型得到的投影结果对实际的生产有更强的指导意义.     

On the maximum feasible subsystem problem,IISs and IIS-hypergraphs

 We consider the Max FS problem: For a given infeasible linear system A x≤b, determine a feasible subsystem containing as many inequalities as possible. This problem, which is NP-hard and also difficult to approximate, has a number of interesting applications in a wide range of fields. In this paper we examine structural and algorithmic properties of Max FS and of Irreducible Infeasible Subsystems (IISs), which are intrinsically related since one must delete at least one constraint from each IIS to attain feasibility. First we provide a new simplex decomposition characterization of IISs and prove that finding a smallest cardinality IIS is very difficult to approximate. Then we discuss structural properties of IIS-hypergraphs, i.e., hypergraphs in which each edge corresponds to an IIS, and show that recognizing IIS-hypergraphs subsumes the Steinitz problem for polytopes and hence is NP-hard. Finally we investigate rank facets of the Feasible Subsystem polytope whose vertices are incidence vectors of feasible subsystems of a given infeasible system. In particular, using the IIS-hypergraph structural result, we show that only two very specific types of rank inequalities induced by generalized antiwebs (which generalize cliques, odd holes and antiholes to general independence systems) can arise as facets. Received: December 2000 / Accepted: November 2002 Published online: February 14, 2003 RID="⋆" ID="⋆" Part of this work was done while the first two authors were with the School of OR&IE, Cornell University, USA. A preliminary version appeared in the Proceedings of the 10th IPCO conference [7], held in Graz, Austria, June 1999. This work was supported by NSF grant DMS-9527124. Key words. infeasible linear systems – feasible subsystems – Irreducible Infeasible Subsystem (IIS) – IIS-hypergraphs – independence systems – feasible subsystem polytope – rank facets