Performance evaluation of nonlinear optimization methods via pairwise comparison and fuzzy numbers

In this paper we extend the deterministic performance evaluation of nonlinear optimization methods: we carry out a pairwise comparison using fuzzy estimates of the performance ratios to obtain fuzzy final scores of the methods under consideration. The key instrument is the concept of fuzzy numbers with triangular membership functions. The algebraic operations on them are simple extensions of the operations on real numbers; they are exact in the parameters (lower, modal, and upper values), not necessarily exact in the shape of the membership function. We illustrate the fuzzy performance evaluation by the ranking and rating of five methods (geometric programming and four general methods) for solving geometric-programming problems, using the results of recent computational studies. Some general methods appear to be leading, an outcome which is not only due to their performance under subjective criteria like domain of applications and conceptual simplicity of use; they also score higher under more objective criteria like robustness and efficiency.     

A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands

In this paper, the vehicle routing problem with fuzzy demands (VRPFD) is considered, and a fuzzy chance constrained program model is designed, based on fuzzy credibility theory. Then stochastic simulation and differential evolution algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy chance constrained program model. Moreover, the influence of the dispatcher preference index on the final objective of the problem is discussed using stochastic simulation, and the best value of the dispatcher preference index is obtained.     

Conditions for convergence of trust region algorithms for nonsmooth optimization

This paper discusses some properties of trust region algorithms for nonsmooth optimization. The problem is expressed as the minimization of a functionh(f(x), whereh(·) is convex andf is a continuously differentiable mapping from ℝ″ to ℝ‴. Bounds for the second order derivative approximation matrices are discussed. It is shown that Powel’s [7, 8] results hold for nonsmooth optimization.     

A numerical evaluation of some collinear scaling algorithms for unconstrained

Collinear scaling algorithms for unconstrained minimization were first proposed by Davidon (1977,80) so that they may incorporate more information about the problem than is possible with quasi–Newton algorithms. Sorensen (1980,82), and Ariyawansa (1983,90) have derived collinear scaling algorithms as natural extensions of quasi–Newton algorithms. In this paper we describe the results of a comprehensive numerical evaluation of four members in the classes of collinear scaling algorithms derived by Sorensen (1980,82) and Ariyawansa (1983,90), relative to the quasi–Newton algorithms they extend.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Analysis of stochastic problem decomposition algorithms in computational grids

Stochastic programming usually represents uncertainty discretely by means of a scenario tree. This representation leads to an exponential growth of the size of stochastic mathematical problems when better accuracy is needed. Trying to solve the problem as a whole, considering all scenarios together, yields to huge memory requirements that surpass the capabilities of current computers. Thus, decomposition algorithms are employed to divide the problem into several smaller subproblems and to coordinate their solution in order to obtain the global optimum. This paper analyzes several decomposition strategies based on the classical Benders decomposition algorithm, and applies them in the emerging computational grid environments. Most decomposition algorithms are not able to take full advantage of all the computing power available in a grid system because of unavoidable dependencies inherent to the algorithms. However, a special decomposition method presented in this paper aims at reducing dependency among subproblems, to the point where all the subproblems can be sent simultaneously to the grid. All algorithms have been tested in a grid system, measuring execution times required to solve standard optimization problems and a real-size hydrothermal coordination problem. Numerical results are shown to confirm that this new method outperforms the classical ones when used in grid computing environments.     

Worst-case analysis of greedy algorithms for the subset-sum problem

Given a set ofn positive integers and another positive integerW, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding,W. We present a polynomial approximation scheme for this problem and prove that its worst-case performance dominates that of Johnson's well-known scheme. Research supported by Ministero Pubblica Istruzion, Italy.     

应用Sugeno模糊积分的目标识别效果评估

针对目标识别效果评估，提出一种通用化的评估思路，选取了评估指标及测度方法。随后，构筑了基于模糊积分的目标识别效果评估模型。最后，结合实测数据和拟合数据完成了仿真。     

Performance evaluation of distribution strategies for the inventory routing problem

Direct shipping strategy is an easy-to-implement distribution strategy frequently used in industrial distribution systems. In this paper, an analytic method is developed for performance evaluation of the strategy for the infinite horizon inventory routing problem with delivery frequency constraint. With the method, the effectiveness of direct shipping strategy can be represented as a function of some system parameters. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that the effectiveness of the strategy can reach 100% (respectively, 94.86%) whenever the demand rate of each retailer is 100% (respectively, 90%) of the vehicle capacity multiplied by the upper bound of the delivery frequency. This insight can help a firm answer questions such as: under what conditions direct shipping strategy is effective and why, and how effective the strategy is under a specific condition? In case direct shipping strategy is proven ineffective, a more general Fixed Partition Policy (FPP) that combines direct shipping strategy and multiple-stop shipping strategy must be used. An analytic method is also developed for performance evaluation of general FPPs. We demonstrate that the effectiveness of an FPP depends on the total demand rate of the retailers in each partition (each retailer set) and their closeness level. This insight provides a useful guideline to the design of effective FPPs. The analytic methods make the performance improvement of a distribution system possible through adjusting its system parameters.     

第三方物流客户服务绩效的灰色模糊综合评价模型

根据评价第三方物流客户服务绩效的KPI指标体系,考虑到评价过程中信息的不完全性以及评判者思维模糊性的特点,将综合评价中传统的信息集结算子推广到更一般的三角模运算上,以此建立了基于三角模算子的第三方物流客户服务绩效的灰色模糊综合评判模型。作为综合评价中传统信息集结算子的推广,该模型具有更广泛的适用范围。     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

基于Nie-Tan算法的区间二型模糊集质心计算:改变主变量采样个数

计算区间二型模糊集的质心(也称降型)是区间二型模糊逻辑系统中的一个重要模块。Karnik-Mendel(KM)迭代算法通常被认为是计算区间二型模糊集质心的标准算法。尽管如此,KM算法涉及复杂的计算过程,不利于实时应用。在各种改进类算法中,非迭代的Nie-Tan(NT)算法可节省计算消耗。此外,连续版本NT(CNT,continuous version of NT)算法被证明是计算质心的准确算法。本文比较了离散版本NT算法中求和运算和连续版本NT算法中求积分运算,通过四个计算机仿真例子证实了当适度增加区间二型模糊集主变量采样个数时,NT算法的计算结果可以精确地逼近CNT算法。     

Insurability of catastrophic risks: the stochastic optimization model

Catastrophes produce losses highly correlated in space and time, which break the law of large numbers. We derive the insurability of dependent catastrophic risks by calculating conditions that would aid insurers in deliberate selection of their portfolios. This paper outlines the general structure of a basic stochastic optimization model. Connections between the probability of ruin and nonsmooth risk functions, as well as adaptive Monte Carlo optimization procedures and path dependent laws of large numbers, are discussed     

Design of cooperative algorithms for multi-objective optimization: application to the flow-shop scheduling problem

This is a summary of the main results presented in the author’s PhD thesis. This thesis was supervised by El-Ghazali Talbi, and defended on 21 June 2005 at the University of Lille (France). It is written in French and is available at http://www.lifl.fr/~basseur/These.pdf. This work deals with the conception of cooperative methods in order to solve multi-objective combinatorial optimization problems. Many cooperation schemes between exact and/or heuristic methods have been proposed in the literature. We propose a classification of such schemes. We propose a new heuristic called adaptive genetic algorithm (AGA), that is designed for an efficient exploration of the search space. We consider several cooperation schemes between AGA and other methods (exact or heuristic). The performance of these schemes are tested on a bi-objective permutation flow-shop scheduling problem, in order to evaluate the interest of each type of cooperation.     

Performance evaluation of a multi-echelon production,transportation and distribution system: A matrix analytical approach

This study proposes an originative method to evaluate complex supply chains. A tentative multi-echelon production, transportation and distribution system with stochastic factors built-in is employed as a test bed for the proposed method. The supply subsystem formulated in this study is a two-stage production facility with constant probability of feedback and stochastic breakdowns. The transportation subsystem is a service facility with one server. The distribution subsystem under study is a single central warehouse with M retailers. All the participants of the supply chain use base-stock policies and single-server settings. We investigated both the make-to-order (MTO) and make-to-stock (MTS) policies for different base-stock levels, as adopted at different sites. Applying quasi-birth-and-death (QBD) processes as decomposed building blocks and then using the existing matrix analytical computing approach for the performance evaluation of a tandem queue constitutes the main procedure of this study. We also discuss the possibilities of extending the current model to account for other inventory control policies as well as for multi-server case. Numerical study shows our proposed analytical model is robust for practical use.     

Performance evaluation of university extension providers: A frontier approach for ordered response data

A frontier model is used to evaluate the performance of extension service providers in the US land grant university system when providing assistance to organic producers. Performance efficiency indicates the effectiveness of extension agents in achieving the highest evaluations from their clientele conditioned on the farm level characteristics and environmental resources and constraints of the organic farmers. Mean performance efficiency of the extension agents is above 0.69 for entire sample with top performing extension service experts outperforming the average providers by about 44%. Performance efficiency, or advisory outcomes that are below the best that extension could provide, are not significantly reduced when extension agents deal with difficult evaluation situations.     

Optimization of finite element bidimensional models: an approach based on genetic algorithms

This paper deals with the optimization of 2D finite element shapes using the very promising methods based on genetic algorithms. The codification of the design variables is carried out by generating series of strings in binary code. Classical genetic operators such as crossover, mutation and reproduction are used for the optimization process. A more refined operators needed to improve the performance of the process are used as well. Some illustrative examples are presented and discussed     

Application of fuzzy optimization to a supply chain network design: A case study of an edible vegetable oils manufacturer

This study applies fuzzy sets to integrate the supply chain network of an edible vegetable oils manufacturer. The proposed fuzzy multi-objective linear programming model attempts to simultaneously minimize the total transportation costs. The first part of the total transportation costs is between suppliers and silos; and rest one is between manufacturer and warehouses. The approach incorporates all operating realities and actual flow patterns at production/distribution network with reference to demands of warehouses, capacities of tin and pet packaging lines. The model has been formulated as a multi objective linear programming model where data are modeled by triangular fuzzy numbers. Finally, the developed fuzzy model is applied for the case study, compiled the results and discussed.     

A new refinement indicator for adaptive parameterization: Application to the estimation of the diffusion coefficient in an elliptic problem

We propose a new refinement indicator (NRI) for adaptive parameterization to determine the diffusion coefficient in an elliptic equation in two-dimensional space. The diffusion coefficient is assumed to be a piecewise constant space function. The unknowns are both the parameter values and the zonation. Refinement indicators are used to localize parameter discontinuities in order to construct iteratively the zonation (parameterization). The refinement indicator is obtained usually by using the first-order effect on the objective function of removing degrees of freedom for a current set of parameters. In this work, in order to reduce the computation costs, we propose a new refinement indicator based on the second-order effect on the objective function. This new refinement indicator depends on the objective function, and its first and second derivatives with respect to the parameter constraints. Numerical experiments show the high efficiency of the new refinement indicator compared to the standard one.