Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

On convergence proofs in system identification – a general principle using ideas from learning theory

It is shown that learning theory offers convergence analysis tools that are useful in system identification problems. They allow analysis in a parameter-free context, which elevates the analysis from parameter sets to model sets and from parameter identification to model identification. When a parameterization is eventually introduced, this leads to alternative assumptions on the parameterization and parameter set. Moreover, structural identification can be analyzed within the same framework. Another advantage is that the proofs are technically and conceptually simple.     

An experimental evaluation of simplicity in rule learning

While recent research on rule learning has focused largely on finding highly accurate hypotheses, we evaluate the degree to which these hypotheses are also simple, that is small. To realize this, we compare well-known rule learners, such as CN2, RIPPER, PART, FOIL and C5.0 rules, with the benchmark system SL² that explicitly aims at computing small rule sets with few literals. The results show that it is possible to obtain a similar level of accuracy as state-of-the-art rule learners using much smaller rule sets.     

A study of equivalent electrical circuit fitting to electrochemical impedance using a stochastic method

Modeling electrochemical impedance spectroscopy is usually done using equivalent electrical circuits. These circuits have parameters that need to be estimated properly in order to make possible the simulation of impedance data. Despite the fitting procedure is an optimization problem solved recurrently in the literature, rarely statistical significance of the estimated parameters is evaluated. In this work, the optimization process for the equivalent electrical circuit fitting to the impedance data is detailed. First, a mathematical development regarding the minimization of residual least squares is presented in order to obtain a statistically valid objective function of the complex nonlinear regression problem. Then, the optimization method used in this work is presented, the Differential Evolution, a global search stochastic method. Furthermore, it is shown how a population-based stochastic method like this can be used directly to obtain confidence regions to the estimated parameters. A sensitivity analysis was also conducted. Finally, the equivalent circuit fitting is done to model synthetic experimental data, in order to demonstrate the adopted procedure.     

Optimal polygonal approximation of digitized curves using the sum of square deviations criterion

We address the problem of finding an optimal polygonal approximation of digitized curves. Several optimal algorithms have already been proposed to determine the minimum number of points that define a polygonal approximation of the curve, with respect to a criterion error. We present a new algorithm with reasonable complexity to determine the optimal polygonal approximation using the mean square error norm. The idea is to estimate the remaining number of segments and to integrate the cost in the A^* algorithm. The solution is optimal in the minimum number of segments.     

Error analysis of a stochastic immersed boundary method incorporating thermal fluctuations

A stochastic numerical scheme for an extended immersed boundary method which incorporates thermal fluctuations for the simulation of microscopic biological systems consisting of fluid and immersed elastica was introduced in reference [2]. The numerical scheme uses techniques from stochastic calculus to overcome stability and accuracy issues associated with standard finite difference methods. The numerical scheme handles a range of time steps in a unified manner, including time steps which are greater than the smallest time scales of the system. The time step regimes we shall investigate can be classified as small, intermediate, or large relative to the time scales of the fluid dynamics of the system. Small time steps resolve in a computationally explicit manner the dynamics of all the degrees of freedom of the system. Large time steps resolve in a computationally explicit manner only the degrees of freedom of the immersed elastica, with the contributions of the dynamics of the fluid degrees of freedom accounted for in only a statistical manner over a time step. Intermediate time steps resolve in a computationally explicit manner only some degrees of freedom of the fluid with the remaining degrees of freedom accounted for statistically over a time step. In this paper, uniform bounds are established for the strong error of the stochastic numerical method for each of the time step regimes. The scaling of the numerical errors with respect to the parameters of the method is then discussed.     

Robust nonlinear feedback–feedforward control of a coupled kinetic Monte Carlo–finite difference simulation

Robust nonlinear feedforward–feedback controllers are designed for a multiscale system that dynamically couples kinetic Monte Carlo (KMC) and finite difference (FD) simulation codes. The coupled codes simulate the copper electrodeposition process for manufacturing on-chip copper interconnects in electronic devices. The control objective is to regulate the current density subject to the condition that the steady-state fluctuation of the overpotential remains bounded within ±0.01 V. The controller designs incorporate a low-order stochastic model that captures the input–output behavior of the coupled KMC–FD code. The controllers achieve the objectives and the closed-loop responses implemented on the low-order model and the coupled KMC–FD code match well within stochastic variations. The nonlinear feedforward control reduces the rise time of the controller response while the feedback control ensures robustness in the presence of model uncertainty.     

Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm

This letter presents a formal stochastic convergence analysis of the standard particle swarm optimization (PSO) algorithm, which involves with randomness. By regarding each particle's position on each evolutionary step as a stochastic vector, the standard PSO algorithm determined by non-negative real parameter tuple {ω,c₁,c₂} is analyzed using stochastic process theory. The stochastic convergent condition of the particle swarm system and corresponding parameter selection guidelines are derived.     

An estimate on the convergence of MKZ–Bézier operators

The pointwise approximation properties of the MKZ–Bézier operators M_n,α(f,x) for α≥1 have been studied in [X.M. Zeng, Rates of approximation of bounded variation functions by two generalized Meyer–König–Zeller type operators, Comput. Math. Appl. 39 (2000) 1–13]. The aim of this paper is to study the pointwise approximation of the operators M_n,α(f,x) for the other case 0<α<1. By means of some new estimate techniques and a result of Guo and Qi [S. Guo, Q. Qi, The moments for the Meyer–König and Zeller operators, Appl. Math. Lett. 20 (2007) 719–722], we establish an estimate formula on the rate of convergence of the operators M_n,α(f,x) for the case 0<α<1.     

On the convergence of multivariant optimization algorithm

In this paper, we introduce a new global optimization method and study its global convergence property through theoretical and experimental approaches. The proposed method is named as multivariant optimization algorithm (MOA) because the intelligent searchers, which are called as atoms, not only are divided into multiple subgroups but also are variant in responsibility. That is, global atoms explore the whole solution space in the hope of finding potential areas where local atoms start the local exploitation. The proposed method is characterized by two important features. On one hand, global atoms do the global exploration in each loop to jump out from local traps. On the other hand, global and local atoms conduct the global exploration and the local exploitation according to their own responsibility, respectively. These features contribute to increasing the chance of converging to the global best. To study the convergence property of MOA, we carried out the convergence analysis, numerical optimization experiments and the shortest path planning experiments. And the results demonstrate that MOA is globally convergent and superior to the compared methods in the global convergence accuracy and probability in solving complex challenging problems which have one or more features such as deceptiveness, randomly located optimum, asymmetry or multiple traps.     

Parallel variable neighborhood search for the min–max order batching problem

Warehousing is a key part of supply chain management. It primarily focuses on controlling the movement and storage of materials within a warehouse and processing the associated transactions, including shipping, receiving, and picking. From the tactical point of view, the main decision is the storage policy, that is, to decide where each product should be located. Every day a warehouse receives several orders from its customers. Each order consists of a list of one or more items that have to be retrieved from the warehouse and shipped to a specific customer. Thus, items must be collected by a warehouse operator. We focus on situations in which several orders are put together into batches, satisfying a fixed capacity constraint. Then, each batch is assigned to an operator, who retrieves all the items included in those orders grouped into the corresponding batch in a single tour. The objective is then to minimize the maximum retrieving time for any batch. In this paper, we propose a parallel variable neighborhood search algorithm to tackle the so‐called min–max order batching problem. We additionally compare this parallel procedure with the best previous approach. Computational results show the superiority of our proposal, confirmed with statistical tests.     

机器看管问题中维修人数的最优配置

在随机服务系统理论中，有一个著名的机器看管问题。尽管其数学模型已经建立，但表达式过于复杂，无法求出最优维修工人数的解析解。本文利用计算机技术，研究求解机器看管问题中维修工人数的最优配置问题，导出了计算最优值的拟合公式。利用该式，可查找出相应的维修工人的最优配置数。     

A Brownian control problem for a simple queueing system in the Halfin–Whitt regime

We consider a formal diffusion limit for a control problem of a multi-type multi-server queueing system, in the regime proposed by Halfin and Whitt. This takes the form of a control problem where the dynamics are driven by a Brownian motion. In one dimension, a pathwise minimum is obtained and is characterized as the solution to a stochastic differential equation. The pathwise solution to a special multi-dimensional problem (corresponding to a multi-type system) follows.     

About the convergence of POD and EPOD modes computed from CFD simulation

In most fluid mechanic applications, the dominant high energy content POD modes are generally well converged justifying the great use of POD to extract the associated large scale flow structures of a turbulent flow. However for particular studies related to the characterization of smaller flow structures, it is necessary to take into account high order POD modes. In this paper based on a particular numerical database available on a finite-discrete spatio-temporal domain, the sensibility of POD modes to both spatial discretization and independent temporal samples is highlighted as a function of integral time and space scale content. A systematic procedure is then proposed in order to verify the spatial convergence of POD modes for a given number of points per integral space scale and per integral time scale and also for a given number of uncorrelated samples that is the number of integral time scale contained in the original signal. The convergence of Extended POD modes is also verified by an error threshold definition that permits to avoid any misinterpretation of the results. A new extension of the EPOD procedure based on the snapshot POD technique is then proposed aiming at using only the converged EPOD modes to characterize the correlated part of the signal.     

Tracking control of uncertain Euler–Lagrange systems with finite‐time convergence

A unified solution is presented to the tracking control problem of Euler–Lagrange systems with finite‐time convergence. A reconstruction module is designed to estimate the overall of unmodeled dynamics, disturbance, actuator misalignment, and multiple actuator faults. That reconstruction is accomplished in finite time with zero error. A nonsingular terminal sliding mode controller is then synthesized, and the resultant closed‐loop system is also shown to be finite‐time stable with the reference trajectory followed in finite time. Unlike most sliding mode control methods to handle system uncertainties, the designed control has less conservativeness and stronger fault tolerant capability. A rigid spacecraft system is used to demonstrate the effectiveness and potential of the proposed scheme. Copyright © 2014 John Wiley & Sons, Ltd.     

Monotonic convergence and robustness of higher‐order gain‐adaptive iterative learning control

For a class of repetitive linear discrete time‐invariant systems with higher relative degree, a higher‐order gain‐adaptive iterative learning control (HOGAILC) is developed while minimizing the energy increment of two adjacent tracking errors with the argument being the iteration‐time‐variable learning‐gain vector (ITVLGV). By taking advantage of rows/columns exchanging transformation of matrix, the ITVLGV is achieved in an explicit form which is dependent upon the system Markov parameters and adaptive to the iterationwise tracking‐error vector. Algebraic derivation demonstrates that the HOGAILC is strictly monotonously convergent. On the basis of the adaptive mode, a damping quasi‐HOGAILC strategy is exploited while the uncertainties of the system Markov parameters exist. Rigorous analysis delivers that the damping quasi‐scheme is strictly monotonically convergent and thus the HOGAILC mechanism is robust to a wider range of uncertainty of system parameters and the damping factor may relax the uncertainty range. Numerical simulations are made to illustrate the validity and the effectiveness.     

A comparison of five heuristics for the multiple depot vehicle scheduling problem

Given a set of timetabled tasks, the multi-depot vehicle scheduling problem consists of determining least-cost schedules for vehicles assigned to several depots such that each task is accomplished exactly once by a vehicle. In this paper, we propose to compare the performance of five different heuristics for this well-known problem, namely, a truncated branch-and-cut method, a Lagrangian heuristic, a truncated column generation method, a large neighborhood search heuristic using truncated column generation for neighborhood evaluation, and a tabu search heuristic. The first three methods are adaptations of existing methods, while the last two are new in the context of this problem. Computational results on randomly generated instances show that the column generation heuristic performs the best when enough computational time is available and stability is required, while the large neighborhood search method is the best alternative when looking for good quality solutions in relatively fast computational times.     

Exploring the fitness landscape and the run-time behaviour of an iterated local search algorithm for cost-based abduction

Cost-based abduction (CBA) is an important problem in reasoning under uncertainty, and can be considered a generalization of belief revision. CBA is known to be NP-hard and has been a subject of considerable research over the past decade. In this paper, we investigate the fitness landscape for CBA, by looking at fitness–distance correlation for local minima and at landscape ruggedness. Our results indicate that stochastic local search techniques would be promising on this problem. We go on to present an iterated local search algorithm based on hill-climbing, tabu search, and simulated annealing. We compare the performance of our algorithm to simulated annealing, and to Santos' integer linear programming method for CBA.     

Dependency treelet translation: the convergence of statistical and example-based machine-translation?

We describe a novel approach to MT that combines the strengths of the two leading corpus-based approaches: Phrasal SMT and EBMT. We use a syntactically informed decoder and reordering model based on the source dependency tree, in combination with conventional SMT models to incorporate the power of phrasal SMT with the linguistic generality available in a parser. We show that this approach significantly outperforms a leading string-based Phrasal SMT decoder and an EBMT system. We present results from two radically different language pairs, and investigate the sensitivity of this approach to parse quality by using two distinct parsers and oracle experiments. We also validate our automated bleu scores with a small human evaluation.