A finite element — Capacitance method for elliptic problems on regions partitioned into subregions

Summary A method is given for the solution of linear equations arising in the finite element method applied to a general elliptic problem. This method reduces the original problem to several subproblems (of the same form) considered on subregions, and an auxiliary problem. Very efficient iterative methods with the preconditioning operator and using FFT are developed for the auxiliary problem.     

Numerical solution method for the electric impedance tomography problem in the case of piecewise constant conductivity and several unknown boundaries

We study the electrical impedance tomography problem with piecewise constant electric conductivity coefficient, whose values are assumed to be known. The problem is to find the unknown boundaries of domains with distinct conductivities. The input information for the solution of this problem includes several pairs of Dirichlet and Neumann data on the known external boundary of the domain, i.e., several cases of specification of the potential and its normal derivative. We suggest a numerical solution method for this problem on the basis of the derivation of a nonlinear operator equation for the functions that define the unknown boundaries and an iterative solution method for this equation with the use of the Tikhonov regularization method. The results of numerical experiments are presented.     

A general Hungarian method for the algebraic transportation problem

In this paper the algebraic transportation problem is introduced which covers besides the Hitchcock and the time transportation problem several other types of transportation problems of practical relevance. To solve this algebraic transportation problem admissible transformations are considered and characterized. Thereupon a transformation algorithm is described which is a generalization of the Hungarian method for the classical transportation problem as well as of a threshold method for time transportation problems.     

基于遗传算法的车间作业计划仿真研究

将仿真技术和遗传算法相结合,根据生产车间的资源情况、优化目标等建立了生产调度仿真模型,然后对仿真输出结果进行统计,针对统计结果应用遗传算法对调度决策进行优化.仿真优化结果说明了该集成优化方法是有效性的.     

A generalized Weiszfeld method for the multi-facility location problem

An iterative method is proposed for the K facilities location problem. The problem is relaxed using probabilistic assignments, depending on the distances to the facilities. The probabilities, that decompose the problem into K single-facility location problems, are updated at each iteration together with the facility locations. The proposed method is a natural generalization of the Weiszfeld method to several facilities.     

区间AHP权重计算的目标规划法

本文对区间 AHP的权重计算问题进行了研究 ,给出了几种新的权重计算方法 .每种方法求解一个线性目标规划问题得到各方案的区间权重 .文章最后给出了一个算例 .     

Fuzzy uncertainty modeling for grid based localization of mobile robots

This paper presents a localization method using fuzzy logic to represent the different facets of uncertainty present in sensor data. Our method follows the typical predict-update cycle of recursive state estimators to estimate the robot’s location. The method is implemented on a fuzzy position grid, and several simplifications are introduced to reduce computational complexity. The main advantages of this fuzzy logic method compared to most current ones are: (i) only an approximate sensor model is required, (ii) several facets of location uncertainty can be represented, and (iii) ambiguities in the sensor information are directly represented, thus avoiding having to solve the data association problem separately. Our method has been validated experimentally on two different platforms, a legged robot equipped with vision and a wheeled robot equipped with range sensors. The experiments show that our method can solve both the tracking and the global localization problem. They also show that this method can successfully cope with ambiguous observations, when several features may be associated to the same observation, and with robot kidnapping situations. Additional experiments are presented that compare our approach with a state-of-the-art probabilistic method.     

A Bayesian Model for Root Computation

A univariate polynomial over the real or the complex numbers is given approximately. We present a Bayesian method for the computation of the posterior probabilities of different multiplicity patterns. The method is based on interpreting the root computation problem as an inverse problem which is then treated in the Bayesian framework. The method can be used to select the most probable multiplicity pattern when the coefficients of a univariate polynomial are not known exactly. The method is illustrated by several numerical examples.     

Parallel implementation of Newton’s method for solving large-scale linear programs

Parallel versions of a method based on reducing a linear program (LP) to an unconstrained maximization of a concave differentiable piecewise quadratic function are proposed. The maximization problem is solved using the generalized Newton method. The parallel method is implemented in C using the MPI library for interprocessor data exchange. Computations were performed on the parallel cluster MVC-6000IM. Large-scale LPs with several millions of variables and several hundreds of thousands of constraints were solved. Results of uniprocessor and multiprocessor computations are presented.     

A new formulation and an exact approach for the many-to-many hub location-routing problem

An important problem of the freight industry is the parcel delivery network design, where several facilities are responsible for assembling flows from several origins, re-routing them to other facilities where the flows are disassembled and the packages delivered to their final destinations. In order to provide this service, local tours are established for the vehicles assigned to each of the processing facilities, which are then responsible for the pickup and delivery tasks. This application gives rise to the many-to-many hub location routing problem that is the combination of two well known problems: the vehicle routing problem and the single assignment hub location problem. In this work, a new formulation for this important problem is proposed and solved by a specially tailored Benders decomposition algorithm. The proposed method is robust enough to solve instances up to 100 nodes having 4 million integer variables.     

Using shortest paths in some transshipment problems with concave costs

This paper deals with the problem of solving an uncapacitated transshipment problem with either one source and several sinks or one sink and several sources. The cost function of the problem is concave in the amount shipped on each arc and thus local optima are possible. A characterization of adjacent extreme flows in terms of corresponding arborescences is given for this type of networks.This characterization together with shortest path methods is then used to attack the problems of finding local optima and of ranking extreme points.A real-world problem and computational evidence for the usefulness of the method are produced.     

Multi-Item Scheduling by Benders' Decomposition

Scheduling the production of several items requires the determination of production quantities in different periods in the presence of resource constraints. Several approximate and heuristic algorithms have been proposed to solve this problem. However, no method for finding an optimal solution has as yet been developed. It is shown that the problem may be solved advantageously using Benders' decomposition. The subproblem in Benders' decomposition is shown to be a transportation problem, and some strategies for solving the master problem are indicated. The paper concludes with a sample problem demonstrating the application of the method.     

A method for approximating pairwise comparison matrices by consistent matrices

In several methods of multiattribute decision making, pairwise comparison matrices are applied to derive implicit weights for a given set of decision alternatives. A class of the approaches is based on the approximation of the pairwise comparison matrix by a consistent matrix. In the paper this approximation problem is considered in the least-squares sense. In general, the problem is nonconvex and difficult to solve, since it may have several local optima. In the paper the classic logarithmic transformation is applied and the problem is transcribed into the form of a separable programming problem based on a univariate function with special properties. We give sufficient conditions of the convexity of the objective function over the feasible set. If such a sufficient condition holds, the global optimum of the original problem can be obtained by local search, as well. For the general case, we propose a branch-and-bound method. Computational experiments are also presented.     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

调节熵函数法

１．引言 考虑如下极小极大问题这里ｆｉ（ｘ）是Ｒｎ中连续可微的函数,ｍ≥２是正整数（Ｐ）是一类比较典型的非光滑优化问题,是许多实际问题的数学模型．同时,线性规划的 Ｋａｒｍａｒｋａｒ标准型的对偶也是（Ｐ）的形式,光滑约束优化问题的一类重要罚函数法也是将问题化为类似（Ｐ）的形式．所以,如何有效地求解（Ｐ）,是一个重要问题．近些年发展起来的嫡函数法（或称凝聚函数法）是一种较新颖而实用的方法．它借助信息论中 Ｓｈａｎｎｏｎ熵的概念,推导出一族光滑的极大熵函数Ｆｐ（ｘ）,且Ｆｐ（ｘ）一致逼近要极小化的非光…     

The method of central difference for the inverse time-dependent heat source problem

This paper investigates the inverse problem of determining a heat source in a parabolic equation where data are given at some fixed location. This problem is ill-posed, i.e., the solution (if it exists) does not depend continuously on the data. A central difference regularization method is given and an order optimal stability estimate is obtained. Numerical results for several benchmark test problems indicate that the central difference regularization method is an accurate and flexible method to determine the unknown time-dependent heat source.     

A hybrid metaheuristic algorithm for dynamic rail car fleet sizing problem

The aim of this paper is to present a model and a solution method for rail freight car fleet sizing problem. The mathematical model is dynamic and multi-periodic and car demands and travel times are assumed deterministic, and the proposed solution method is hybridization of genetic algorithms and simulated annealing algorithms. Experimental analysis is conducted using several test problems. The results of the proposed algorithm and CPLEX software are compared. The results show high efficiency and effectiveness of the proposed algorithm. The solution method is applied to solve fleet sizing problem in the Iran Railways as a case study.     

Bifurcation of the self-excited oscillations of a plate with slight damping in a supersonic gas flow

A non-linear boundary-value problem is considered which simulates the oscillations of a plate in a supersonic gas flow. The classical version of the formulation of the problem, proposed by Bolotin, as well as several of its modifications considered by Holmes and Marsden, are taken as a basis. The oscillations of the plate are studied assuming that the damping coefficient is small. This version of the formulation of the problem leads to the need to investigate the bifurcations of the self-excited oscillations in a non-linear boundary-value problem in a case which is close to the critical case of a double pair of pure imaginary values of the stability spectrum. The bifurcation problem is reduced to the investigation of a complex second order non-linear differential equation by the method of normal forms. All the stages in the investigation are carried out without using the Bubnov method.     

Fitting differential equation models to observed economic data—I. quasilinearization

This paper discusses the fitting of differential equation models to economic data. In particular, it treats the problem of describing the growth of capital in terms of a differential equation containing several parameters. The parameters are to be estimated on the basis of data. This estimation problem is formulated as a nonlinear boundary value problem. The rapidly convergent successive approximation method of quasilinearization is described and applied. Representative results of numerical experiments are presented, showing the effectiveness of the approach. Suggestions for additional studies are made.     

Two-level decomposition algorithm for crew rostering problems with fair working condition

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.