Pattern search ranking and selection algorithms for mixed variable simulation-based optimization

The class of generalized pattern search (GPS) algorithms for mixed variable optimization is extended to problems with stochastic objective functions. Because random noise in the objective function makes it more difficult to compare trial points and ascertain which points are truly better than others, replications are needed to generate sufficient statistical power to draw conclusions. Rather than comparing pairs of points, the approach taken here augments pattern search with a ranking and selection (R&S) procedure, which allows for comparing many function values simultaneously. Asymptotic convergence for the algorithm is established, numerical issues are discussed, and performance of the algorithm is studied on a set of test problems.     

应用数据挖掘的束流状态描述建模

聚类分析是描述数据群体特征的有效方法.然而,随着挖掘数据库规模的增大,评分函数极值搜索是计算复杂度很高的问题.文中提出了一种新的算法,并将其运用到束流状态描述建模中.试验结果表明,该算法快速有效.同时,重复性是电子储存环的重要指标,聚类模型可作为机器研究和决策的依据,具有指导意义.     

多车场有时间窗的多车型车辆调度及其禁忌算法研究

本文针对物流配送中的多车场车辆调度问题提出了两种多车场的处理方法，介绍了多车场车辆调度问题中容量、时间窗、多车型等多种约束的处理方法，并且根据具体约束情况设计了禁忌算法，对多车场有时间窗的多车型车辆调度问题加以实现，给出了一个具有代表性的算例试验结果和结果分析，通过试验表明了此方法对优化有时间窗的多车型车辆调度问题的有效性．     

General variable neighborhood search for the continuous optimization

We suggest a new heuristic for solving unconstrained continuous optimization problems. It is based on a generalized version of the variable neighborhood search metaheuristic. Different neighborhoods and distributions, induced from different metrics are ranked and used to get random points in the shaking step. We also propose VNS for solving constrained optimization problems. The constraints are handled using exterior point penalty functions within an algorithm that combines sequential and exact penalty transformations. The extensive computer analysis that includes the comparison with genetic algorithm and some other approaches on standard test functions are given. With our approach we obtain encouraging results.     

Complexity of local search for the p-median problem

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0–1 local saddle points, and classical Karush–Kuhn–Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.     

Comparing different metaheuristic approaches for the median path problem with bounded length

In this paper we consider the Bounded Length Median Path Problem which can be defined as the problem of locating a path-shaped facility that departures from a given origin and arrives at a given destination in a network. The length of the path is assumed to be bounded by a given maximum length. At each vertex of the network (customer-point) the demand for the service is given and the cost to reach the closest service-point is computed. The objective is to minimize the sum of these costs over all the customer-points in the network.     

Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

A two pass heuristic algorithm for scheduling ‘blocked out’ units in continuous process industry

This paper addresses the problem of scheduling cascaded ‘blocked out’ continuous processing units separated by finite capacity storage tanks. The raw materials for the product lines arrive simultaneously on the input side of the first unit. But every unit can process only one product line at a time, thus giving rise to the possibility of spillage of raw material due to limited storage capacity. The need to process multiple product lines and the added constraint of multiple intermediate upliftment dates aggravate the problem. This problem is quite common in petrochemical industry. The paper provides a MINLP (Mixed Integer Non-Linear Programming) formulation of the problem. However, for any realistic scheduling horizon, the size of the problem is too large to be solved by standard packages. We have proposed a depth first branch and bound algorithm, guided by heuristics, to help planners in tackling the problem. The suggested algorithm could output near optimal solutions for scheduling horizons of 30 time periods when applied to real life situations involving 3 units and 3 product lines. Preliminary version of the paper appeared in the proceedings of MISTA, 2005.     

A general model for cyclic machine scheduling problems

A general framework for modeling and solving cyclic scheduling problems is presented. The objective is to minimize the cycle time. The model covers different cyclic versions of the job-shop problem found in the literature, robotic cell problems, the single hoist scheduling problem and tool transportation between the machines.It is shown that all these problems can be formulated as mixed integer linear programs which have a common structure. Small instances are solved with CPLEX. For larger instances tabu search procedures have been developed. The main ideas of these methods are indicated.     

A descent method with inexact linear search for nonsmooth equilibrium problems

A descent method with respect to the gap function is formulated and justified for the nonsmooth equilibrium problem. It uses the procedure of inexact linear search of the Armijo type. The proposed method converges under the same assumptions as the methods with exact linear search.