Ordinal optimization based metaheuristic algorithm for optimal inventory policy of assemble-to-order systems

Assemble-to-order (ATO) systems refer to a manufacturing process in which a customer must first place an order before the ordered item is manufactured. An ATO system that operates under a continuous-review base-stock policy can be formulated as a stochastic simulation optimization problem (SSOP) with a huge search space, which is known as NP-hard. This work develops an ordinal optimization (OO) based metaheuristic algorithm, abbreviated to OOMH, to determine a near-optimal design (target inventory level) in ATO systems. The proposed approach covers three main modules, which are meta-modeling, exploration, and exploitation. In the meta-modeling module, the extreme learning machine (ELM) is used as a meta-model to estimate the approximate objective value of a design. In the exploration module, the elite teaching-learning-based optimization (TLBO) approach is utilized to select N candidate designs from the entire search space, where the fitness of a design is evaluated using the ELM. In the exploitation module, the sequential ranking-and-selection (R&S) scheme is used to optimally allocate the computing resource and budget for effective selecting the critical designs from the N candidate designs. Finally, the proposed algorithm is applied to two general ATO systems. The large ATO system comprises 12 items on eight products and the moderately sized ATO system is composed of eight items on five products. Test results that are obtained using the OOMH approach are compared with those obtained using three heuristic methods and a discrete optimization-via-simulation (DOvS) algorithm. Analytical results reveal that the proposed method yields solutions of much higher quality with a much higher computational efficiency than the three heuristic methods and the DOvS algorithm.     

An evolutionary programming approach to mixed-variable optimization problems

Many engineering optimization problems frequently encounter discrete variables as well as continuous variables and the presence of nonlinear discrete variables considerably adds to the solution complexity. Very few of the existing methods can find a globally optimal solution when the objective functions are non-convex and non-differentiable. In this paper, we present a mixed-variable evolutionary programming (MVEP) technique for solving these nonlinear optimization problems which contain integer, discrete, zero-one and continuous variables. The MVEP provides an improvement in global search reliability in a mixed-variable space and converges steadily to a good solution. An approach to handle various kinds of variables and constraints is discussed. Some examples of mixed-variable optimization problems in the literature are tested, which demonstrate that the proposed approach is superior to current methods for finding the best solution, in terms of both solution quality and algorithm robustness.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs

Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give a posteriori error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining the approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig—Wolfe decomposition method.     

Ordinal Optimization of G/G/1/K Polling Systems with <Emphasis Type="Italic">k</Emphasis>-Limited Service Discipline

In this paper, we propose an ordinal optimization theory based algorithm to solve the optimization problem of G/G/1/K polling system with k-limited service discipline for a good enough solution using limited computation time. We assume that the arrival rates do not deteriorate visibly within a very short period. Our approach consists of two stages. In the first stage, we employ a typical genetic algorithm to select N=1024 roughly good solutions from the huge discrete solution space Ω using an offline trained artificial neural network as a surrogate model for fitness evaluation. The second stage consists of several substages to select estimated good enough solutions from the previous N, and the solution obtained in the last substage is the good enough solution that we seek. Using numerous tests, we demonstrate: (i) the computational efficiency of our algorithm in the aspect that we can apply our algorithm in real-time based on the arrival rate assumption; (ii) the superiority of the good enough solution, which achieves drastic objective value reduction in comparison with other existing service disciplines. We provide a performance analysis for our algorithm based on the derived models. The results show that the good enough solution that we obtained is among the best 3.31×10⁻⁶% in the solution space with probability 0.99. This research work was supported in part by the National Science Council of Taiwan, ROC, Grant NSC95-2221-E-009-099-MY2.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

Algorithm robust for the bicriteria discrete optimization problem

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.     

Approximating the Pareto optimal set using a reduced set of objective functions

Real-world applications of multi-objective optimization often involve numerous objective functions. But while such problems are in general computationally intractable, it is seldom necessary to determine the Pareto optimal set exactly. A significantly smaller computational burden thus motivates the loss of precision if the size of the loss can be estimated. We describe a method for finding an optimal reduction of the set of objectives yielding a smaller problem whose Pareto optimal set w.r.t. a discrete subset of the decision space is as close as possible to that of the original set of objectives. Utilizing a new characterization of Pareto optimality and presuming a finite decision space, we derive a program whose solution represents an optimal reduction. We also propose an approximate, computationally less demanding formulation which utilizes correlations between the objectives and separates into two parts. Numerical results from an industrial instance concerning the configuration of heavy-duty trucks are also reported, demonstrating the usefulness of the method developed. The results show that multi-objective optimization problems can be significantly simplified with an induced error which can be measured.     

Progressive genetic algorithm for solution of optimization problems with nonlinear equality and inequality constraints

A new approach, identified as progressive genetic algorithm (PGA), is proposed for the solutions of optimization problems with nonlinear equality and inequality constraints. Based on genetic algorithms (GAs) and iteration method, PGA divides the optimization process into two steps; iteration and search steps. In the iteration step, the constraints of the original problem are linearized using truncated Taylor series expansion, yielding an approximate problem with linearized constraints. In the search step, GA is applied to the problem with linearized constraints for the local optimal solution. The final solution is obtained from a progressive iterative process. Application of the proposed method to two simple examples is given to demonstrate the algorithm.     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.     

Textile porosity determination based on a nonlinear heat and moisture transfer model

The inverse problems of textile materials design on heat and moisture transfer properties are important and indispensable in applications in the body-clothing-environment system. We present an inverse problem of textile porosity determination (IPTPD) based on a nonlinear heat and moisture transfer model. Adopting the idea of the least-squares, the mathematical formulation of IPTPD is deduced to a regularized optimization problem with collocation method applied. The continuity of the regularized minimization problem is proved. By means of genetic algorithm (GA), the approximate solution of the IPTPD is numerically obtained. To reduce the computational cost, an improved algorithm based on BP neural network with GA is proposed in the numerical simulation. Compared with the direct GA searching, the computational cost is greatly reduced, which presents a similar result.     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.     

An efficient interval computing technique for bound-constrained uncertain optimization problems

In this article, a competent interval-oriented approach is proposed to solve bound-constrained uncertain optimization problems. This new class of problems is considered here as an extension of the classical bound-constrained optimization problems in an inexact environment. The proposed technique is nothing but an imitation of the well-known interval analysis-based branch-and-bound optimization approach. Efficiency of this technique is strongly dependent on division, bounding, selection/rejection and termination criteria. The technique involves a multisection division criterion of the accepted/proposed search region. Then, we have employed the interval-ranking definitions with respect to the pessimistic decision makers’ point of view given by Mahato and Bhunia [Interval-arithmetic-oriented interval computing technique for global optimization, Appl. Math. Res. Express 2006 (2006), pp. 1–19] to compare the interval-valued objectives calculated in each subregion and also to select the subregion containing the best interval objective value. The process is continued until the interval width for each variable in the accepted subregion is negligible and ultimately the global or close-to-global interval-valued optimal solution is obtained. The proposed technique has been evaluated numerically using a wide set of newly introduced univariate/multivariate test problems. Finally, to compare the computational results obtained by the proposed method, the graphical representation for some test problems is given.     

Using support vector machines to learn the efficient set in multiple objective discrete optimization

We propose using support vector machines (SVMs) to learn the efficient set in multiple objective discrete optimization (MODO). We conjecture that a surface generated by SVM could provide a good approximation of the efficient set. As one way of testing this idea, we embed the SVM-approximated efficient set information into a Genetic Algorithm (GA). This is accomplished by using a SVM-based fitness function that guides the GA search. We implement our SVM-guided GA on the multiple objective knapsack and assignment problems. We observe that using SVM improves the performance of the GA compared to a benchmark distance based fitness function and may provide competitive results.     

Using the WOWA operator in robust discrete optimization problems

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by introducing a scenario set containing a finite number of cost scenarios. A probability distribution over the set of scenarios is available. In order to choose a solution the weighted OWA criterion (WOWA) is applied. This criterion allows decision makers to take into account both probabilities for scenarios and the degree of pessimism/optimism. In this paper the complexity of the considered class of discrete optimization problems is described and some exact and approximation algorithms for solving it are proposed. Applications to the selection and the assignment problems, together with results of computational tests are shown.     

A novel three-phase trajectory informed search methodology for global optimization

A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases. The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method.     

Approximately global optimization for assortment problems using piecewise linearization techniques

Recently, Li and Chang proposed an approximate model for assortment problems. Although their model is quite promising to find approximately global solution, too many 0–1 variables are required in their solution process. This paper proposes another way for solving the same problem. The proposed method uses iteratively a technique of piecewise linearization of the quadratic objective function. Numerical examples demonstrate that the proposed method is computationally more efficient than the Li and Chang method.     

A survey on the global optimization problem: General theory and computational approaches

Several different approaches have been suggested for the numerical solution of the global optimization problem: space covering methods, trajectory methods, random sampling, random search and methods based on a stochastic model of the objective function are considered in this paper and their relative computational effectiveness is discussed. A closer analysis is performed of random sampling methods along with cluster analysis of sampled data and of Bayesian nonparametric stopping rules.     

A trust-region method with a conic model for unconstrained optimization

In this paper, we propose and analyze a new conic trust-region algorithm for solving the unconstrained optimization problems. A new strategy is proposed to construct the conic model and the relevant conic trust-region subproblems are solved by an approximate solution method. This approximate solution method is not only easy to implement but also preserves the strong convergence properties of the exact solution methods. Under reasonable conditions, the locally linear and superlinear convergence of the proposed algorithm is established. The numerical experiments show that this algorithm is both feasible and efficient. Copyright © 2008 John Wiley & Sons, Ltd.