DETERMINATION OF PERMANENT OPTIMAL DATA POINTS AND AN EFFICIENT ALGORITHM FOR LAD PROBLEM

This paper gives a definition of permanent optimal data point of Least Absolute Deviation(LAD)problem.Some theoretical results on non-degenerate LAD problem are obtained.For computing LAD problem,an efficient,algorithm is given according to the idea of permanent optimal data point.Numerical experience shows that our algorithm is better than many of others,including the famous B R algorithm.     

Ant colony optimization for the examination scheduling problem

Ant colony optimization is an evolutionary search procedure based on the way that ant colonies cooperate in locating shortest routes to food sources. Early implementations focussed on the travelling salesman and other routing problems but it is now being applied to an increasingly diverse range of combinatorial optimization problems. This paper is concerned with its application to the examination scheduling problem. It builds on an existing implementation for the graph colouring problem to produce clash-free timetables and goes on to consider the introduction of a number of additional practical constraints and objectives. A number of enhancements and modifications to the original algorithm are introduced and evaluated. Results based on real-examination scheduling problems including standard benchmark data (the Carter data set) show that the final implementation is able to compete effectively with the best-known solution approaches to the problem.     

A metaheuristic approach to the dominating tree problem

This paper considers a recently introduced NP-hard problem on graphs, called the dominating tree problem. In order to solve this problem, we develop a variable neighborhood search (VNS) based heuristic. Feasible solutions are obtained by using the set of vertex permutations that allow us to implement standard neighborhood structures and the appropriate local search procedure. Computational experiments include two classes of randomly generated test instances and benchmark test instances from the literature. Optimality of VNS solutions on small size instances is verified with CPLEX.     

Density Based Problem Space Search for the Capacitated Clustering p-Median Problem

In the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction–deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency.     

Application of principal component analysis to multi-disk concurrent accessing

This paper is concerned with the allocation of multi-attribute records on several disks so as to achieve high degree of concurrency of disk access when responding to partial match queries.An algorithm to distribute a set of multi-attribute records onto different disks is presented. Since our allocation method will use the principal component analysis, this concept is first introduced. We then use it to generate a set of real numbers which are the projections on the first principal component direction and can be viewed as hashing addresses.Then we propose an algorithm based upon these hashing addresses to allocate multi-attribute records onto different disks. Some experimental results show that our method can indeed be used to solve the multi-disk data allocation problem for concurrent accessing.     

数据挖掘过程中连续属性离散化新方法研究

在知识发现和机器学习领域里,许多数据挖掘方法如基于粗集的数据挖掘工具等需要使用离散的属性值,但实际观测到的大多是连续性属性数据,这对许多新型数据挖掘工具的研究带来了不便.本文针对以上问题,在综合分析目前连续属性离散化方法的基础上,提出了一种基于数据分布特征的连续属性离散化新方法,并用经典算例验证了此算法,实验结果表明该方法具有合理性和可行性.     

A hybrid genetic algorithm for the job shop scheduling problem

This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.     

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ, μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.     

Optimization for simulation: LAD accelerator

The goal of this paper is to address the problem of evaluating the performance of a system running under unknown values for its stochastic parameters. A new approach called LAD for Simulation, based on simulation and classification software, is presented. It uses a number of simulations with very few replications and records the mean value of directly measurable quantities (called observables). These observables are used as input to a classification model that produces a prediction for the performance of the system. Application to an assemble-to-order system from the literature is described and detailed results illustrate the strength of the method.     

Balancing of agricultural census data by using discrete optimization

In the case of large-scale surveys, such as a Census, data may contain errors or missing values. An automatic error correction procedure is therefore needed. We focus on the problem of restoring the consistency of agricultural data concerning cultivation areas and number of livestock, and we propose here an approach to this balancing problem based on optimization. Possible alternative models, either linear, quadratic or mixed integer, are presented. The mixed integer linear one has been preferred and used for the treatment of possibly unbalanced data records. Results on real-world Agricultural Census data show the effectiveness of the proposed approach.     

DEA models for ratio data: Convexity consideration

Data envelopment analysis (DEA) is defined based on observed units and by finding the distance of each unit to the border of estimated production possibility set (PPS). The convexity is one of the underlying assumptions of the PPS. This paper shows some difficulties of using standard DEA models in the presence of input-ratios and/or output-ratios. The paper defines a new convexity assumption when data includes a ratio variable. Then it proposes a series of modified DEA models which are capable to rectify this problem.     

A new approach for data editing and imputation

The editing-and-imputation problem concerns the question of finding errors in a record which does not satisfy a set of consistency rules. Once some potential errors have been localizated, it is also necessary to impute new values to the associated fields. The output dataset should consist of valid records and preserve similar statistical properties as the input dataset. Most of this work is usually done manually by statistical agencies, thus consuming a great deal of human resources. This paper presents a mathematical programming model to optimally solve the problem on surveys with categorical values and particular edits. We also describe a heuristic approach to deal with the more complex surveys. The heuristic procedure follows a combination of the widely-accepted hot-deck donor scheme and the multivariate regression analysis. It has been implemented in a graphical user interface running on standard personal computers, and has been tested on real-world surveys. This paper demonstrates the satisfactory performance of our automatic procedure.     

A filter-and-fan approach to the job shop scheduling problem

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms.     

��Ⱦ�������Իع�ģ�͵���Сһ�˹���

In this paper, linear regression models with contaminated data are considered. Estimation methods for the regression parameters based on least absolute deviations (LAD) are proposed, and properties of consistency and asymptotic normality of the proposed method are proved under some regular conditions. Simulations are done to assess the properties of the method when sample size is small, and simulation results show that the methods works well.     

Modeling and algorithmic development of a staff scheduling problem

The problem of scheduling workers at a hub of a trucking system for the stripping and loading of the trucks and the determination of the optimal number of workers is a difficult problem. The trucks arrive at the facility at different (but known) times and may have their own scheduled departure times. This problem is like a set partitioning problem but with a side constraint pertaining to the dynamic arrival of the trucks. We develop a procedure to solve this problem that is based on the column generation technique, and the solution of a set covering problem to obtain the integer solution. The performance of the procedure is demonstrated by applying it to the real-life data obtained from a trucking company. Its effectiveness is illustrated by comparing it with a lower bound and a well-known heuristic procedure.     

LAD estimation for nonlinear regression models with randomly censored data

The least absolute deviations (LAD) estimation for nonlinear regression models with randomly censored data is studied and the asymptotic properties of LAD estimators such as consistency, boundedness in probability and asymptotic normality are established. Simulation results show that for the problems with censored data, LAD estimation performs much more robustly than the least squares estimation.     

基于区间变量RF算法的青海省电力公司员工离职预测

在电力体制改革全面深化的背景下,我国西部偏远地区的电力企业面临较为严重的人员流失问题。员工离职预测越来越受到电力企业关注,然而传统预测算法无法有效解决电力企业员工离职数据集的不平衡问题。基于此,本文提出一种基于区间变量的随机森林算法,采用青海省电力公司2009~2017年人力资源数据集进行实证分析,并与决策树、支持向量机、随机森林算法的预测效果进行对比。结果表明,该算法更适合解决数据不平衡问题,具有更高的预测精度;同时分析得到员工离职的重要特征,为相关电力企业人力资源管理提供决策依据。     

A general method for determining the set of all efficient solutions to a linear vectormaximum problem

To solve a linear vectormaximum problem means, in general, to determine the set E of all efficient solutions. A multiparametric method based on earlier works of the author is presented. In the procedure efficient vertices and efficient edges are generated via one subprogram, which works as a simple linear programming problem, and just by inspection of these results higher dimensional efficient faces are determined. The procedure does not depend on special properties of the restriction set and/or of the system of given objective functions. Illustrative examples are presented. Two appendixes provide a survey on a multiparametric algorithm and on a solution procedure for the auxiliary problem, both of which are the background for the method.     

Robust Adaptive Fuzzy Identification of Time-Varying Processes with Uncertain Data. Handling Uncertainties in the Physical Fitness Fuzzy Approximation with Real World Medical Data: An Application

This study considers the problem of Robust Fuzzy approximation of a time-varying nonlinear process in the presence of uncertainties in the identification data using a Sugeno Fuzzy System while maintaining the interpretability of the fuzzy model during identification. A recursive procedure for the estimation of fuzzy parameters is proposed based on solving local optimization problem that attempt to minimize the worst-case effect of data uncertainties on approximation performance. To illustrate the approach, several simulation studies on numerical examples are provided. The developed scheme was applied to handle the vagueness, ambiguity and uncertainty inherently present in the general notion of a Medical Expert about Physical Fitness based on a set of various Physiological parameters measurements.