Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.     

Solving air traffic conflict problems via local continuous optimization

This paper first introduces an original trajectory model using B-splines and a new semi-infinite programming formulation of the separation constraint involved in air traffic conflict problems. A new continuous optimization formulation of the tactical conflict-resolution problem is then proposed. It involves very few optimization variables in that one needs only one optimization variable to determine each aircraft trajectory. Encouraging numerical experiments show that this approach is viable on realistic test problems. Not only does one not need to rely on the traditional, discretized, combinatorial optimization approaches to this problem, but, moreover, local continuous optimization methods, which require relatively fewer iterations and thereby fewer costly function evaluations, are shown to improve the performance of the overall global optimization of this non-convex problem.     

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.     

Global optimization of higher order moments in portfolio selection

We discuss the global optimization of the higher order moments of a portfolio of financial assets. The proposed model is an extension of the celebrated mean variance model of Markowitz. Asset returns typically exhibit excess kurtosis and are often skewed. Moreover investors would prefer positive skewness and try to reduce kurtosis of their portfolio returns. Therefore the mean variance model (assuming either normally distributed returns or quadratic utility functions) might be too simplifying. The inclusion of higher order moments has therefore been proposed as a possible augmentation of the classical model in order to make it more widely applicable. The resulting problem is non-convex, large scale, and highly relevant in financial optimization. We discuss the solution of the model using two stochastic algorithms. The first algorithm is Differential Evolution (DE). DE is a population based metaheuristic originally designed for continuous optimization problems. New solutions are generated by combining up to four existing solutions plus noise, and acceptance is based on evolutionary principles. The second algorithm is based on the asymptotic behavior of a suitably defined Stochastic Differential Equation (SDE). The SDE consists of three terms. The first term tries to reduce the value of the objective function, the second enforces feasibility of the iterates, while the third adds noise in order to enable the trajectory to climb hills.     

Focused ultrasonic therapy planning: Metamodeling,optimization, visualization

We present a generic approach for focused ultrasonic therapy planning on the basis of numerical simulation, multi-objective optimization, stochastic analysis and visualization in virtual environments. A realistic test case is used to demonstrate the approach. RBF metamodeling of simulation results is performed for continuous representation of two optimization objectives. The non-convex Pareto front of the objectives is determined by means of non-dominated set and local improvement algorithms. Uncertainties of metamodeling are estimated by means of a cross-validation procedure. The 3D visualization in virtual environment framework Avango allows detailed inspection of MRT images, the corresponding material model and spatial distribution of the resulting thermal dose.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

A dynamic genetic algorithm based on continuous neural networks for a kind of non-convex optimization problems

This paper presents a kind of dynamic genetic algorithm based on a continuous neural network, which is intrinsically the steepest decent method for constrained optimization problems. The proposed algorithm combines the local searching ability of the steepest decent methods with the global searching ability of genetic algorithms. Genetic algorithms are used to decide each initial point of the steepest decent methods so that all the initial points can be searched intelligently. The steepest decent methods are employed to decide the fitness of genetic algorithms so that some good initial points can be selected. The proposed algorithm is motivated theoretically and biologically. It can be used to solve a non-convex optimization problem which is quadratic and even more non-linear. Compared with standard genetic algorithms, it can improve the precision of the solution while decreasing the searching scale. In contrast to the ordinary steepest decent method, it can obtain global sub-optimal solution while lessening the complexity of calculation.     

A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables

Geometric branch-and-bound techniques are well-known solution algorithms for non-convex continuous global optimization problems with box constraints. Several approaches can be found in the literature differing mainly in the bounds used.     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

Dynamic Capacity Acquisition and Assignment under Uncertainty

Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochastic programming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.     

Trajectory Modeling of Robot Manipulators in the Presence of Obstacles

This paper presents two different strategies for the problem of the optimal trajectory planning of robot manipulators in the presence of fixed obstacles. The first strategy is related to the situation where the trajectory must pass through a given number of points. The second strategy corresponds to the case where only the initial and final points are given. The optimal traveling time and the minimum mechanical energy of the actuators are considered together to build a multiobjective function. The trajectories are defined using spline functions and are obtained through offline computation for online operation. Sequential unconstrained minimization techniques (SUMT) have been used for the optimization. The obstacles are considered as three-dimensional objects sharing the same workspace performed by the robot. The obstacle avoidance is expressed in terms of the distances between potentially colliding parts. Simulation results are presented and show the efficiency of the general methodology used in this paper.     

Cell-to-cell mapping method for time-optimal trajectory planning of multiple robot arm systems

This paper presents the results obtained by applying the cell-to-cell mapping method to solve the problem of the time-optimal trajectory planning for coordinated multiple robotic arms handling a common object along a specified geometric path. Based on the structure of the time-optimal trajectory control law, the continuous dynamic model of multiple arms is first approximated by a discrete and finite cell-to-cell mapping on a two-dimensional cell space over a phase plane. The optimal trajectory and the corresponding control are then determined by using the cell-to-cell mapping and a simple search algorithm. To further improve the computational efficiency and to allow for parallel computation, a hierarchical search algorithm consisting of a multiple-variable optimization on the top level and a number of cell-to-cell searches on the bottom level is proposed and implemented in the paper. Besides its simplicity, another distinguishing feature of the cell-to-cell mapping methods is the generation of all optimal trajectories for a given final state and all possible initial states through a single searching process. For most of the existing trajectory planning methods, the planning process can be started only when both the initial and final states have been specified. The cell-to-cell method can be generalized to any optimal trajectory planning problem for a multiple robotic arms system.     

A General Cavitation Model for the Highly Nonlinear Mie-Grüneisen Equation of State

A general one-fluid cavitation model is proposed for a family of Mie-Grüneisen equations of state (EOS), which can provide a wide application of cavitation flows, such as liquid-vapour transformation and underwater explosion. An approximate Riemann problem and its approximate solver for the general cavitation model are developed. The approximate solver, which provides the interface pressure and normal velocity by an iterative method, is applied in computing the numerical flux at the phase interface for our compressible multi-medium flow simulation on Eulerian grids. Several numerical examples, including Riemann problems and underwater explosion applications, are presented to validate the cavitation model and the corresponding approximate solver.     

双值约束非凸三次规化问题的全局最优性条件

考虑一类带有双值约束的非凸三次优化问题, 给出了该问题的一个全局最优充分必要条件. 结果改进并推广了一些文献中所给出的全局最优性条件, 同时还通过数值例子来说明所给出的全局最优充要条件是易验证的.     

Identification of mechanical properties of arteries with certification of global optimality

In this study, we consider identification of parameters in a non-linear continuum-mechanical model of arteries by fitting the models response to clinical data. The fitting of the model is formulated as a constrained non-linear, non-convex least-squares minimization problem. The model parameters are directly related to the underlying physiology of arteries, and correctly identified they can be of great clinical value. The non-convexity of the minimization problem implies that incorrect parameter values, corresponding to local minima or stationary points may be found, however. Therefore, we investigate the feasibility of using a branch-and-bound algorithm to identify the parameters to global optimality. The algorithm is tested on three clinical data sets, in each case using four increasingly larger regions around a candidate global solution in the parameter space. In all cases, the candidate global solution is found already in the initialization phase when solving the original non-convex minimization problem from multiple starting points, and the remaining time is spent on increasing the lower bound on the optimal value. Although the branch-and-bound algorithm is parallelized, the overall procedure is in general very time-consuming.

     

A mathematical programming-based scheduling framework for multitasking environments

A new paradigm along with a mixed (binary) integer-linear programming model is developed for scheduling tasks in multitasking environments, for which the number of completed tasks is not a good measure. One special case falls into the realm of deteriorating jobs. Polynomial time optimal solution algorithms are presented for this and one other special case. As the complexity of the original problem is believed to be strongly NP-hard, an efficient solution algorithm, based on tabu search, is developed to solve the problem. Small, medium, and large size problems are solved, and the solution obtained from the algorithm is compared with that of the optimal solution or the upper bound found from using the Lagrangian relaxation. Where it was measurable, the search algorithm gave quantifiably good quality solutions, and in all cases it had a much better time efficiency than the branch-and-bound enumeration method. A detailed statistical experiment, based on the split-plot design, is developed to identify the characteristics of the tabu search algorithm, thus guaranteeing a solution that is significantly better in quality. A conjecturing technique is introduced for problems with very large planning horizons. This technique had remarkable time efficiency with no apparent loss of quality.     

Accurate and robust body position trajectory tracking of six-legged walking robots with nonsingular terminal sliding mode control method

Many tasks, such as walking in narrow environments, detecting land mines, coordinating with manipulators, and avoiding obstacles, demand multi-legged walking robots to accurately and robustly track predefined body trajectories. Tracking body position trajectory must be accurate and robust in these situations, but research on this topic is rarely carried out. In this study, we propose a nonsingular terminal sliding mode (NTSM) control algorithm to implement accurate and robust body position trajectory tracking of six-legged walking robots. The NTSM control algorithm is constructed on the basis of the body position trajectory tracking model with a new NTSM reaching law. The performance of the NTSM control method is evaluated through several verifications. Results demonstrate that the proposed algorithm is effective for accurate and robust body position trajectory tracking. The findings of this study can provide insights into improving multi-legged walking robots’ walking and operation abilities in special environments and expanding the application fields of these robots.     

Iterative Algorithms for Multiscale State Estimation, Part 1: Concepts

The objective of the present investigation is to explore the potential of multiscale refinement schemes for the numerical solution of dynamic optimization problems arising in connection with chemical process systems monitoring. State estimation is accomplished by the solution of an appropriately posed least-squares problem. To offer at any instant of time an approximate solution, a hierarchy of successively refined problems is designed using a wavelet-based Galerkin discretization. In order to fully exploit at any stage the approximate solution obtained also for an efficient treatment of the arising linear algebra tasks, we employ iterative solvers. In particular, we will apply a nested iteration scheme to the hierarchy of arising equation systems and adapt the Uzawa algorithm to the present context. Moreover, we show that, using wavelets for the formulation of the problem hierarchy, the largest eigenvalues of the resulting linear systems can be controlled effectively with scaled diagonal preconditioning. Finally, we deduce appropriate stopping criteria and illustrate the characteristics of the solver with a numerical example.     

Multi-Path Approach for Reliability-Redundancy Allocation Using a Scaling Method

The reliability-redundancy allocation problem is an optimization problem that achieves better system reliability by determining levels of component redundancies and reliabilities simultaneously. The problem is classified with the hardest problems in the reliability optimization field because the decision variables are mixed-integer and the system reliability function is nonlinear, non-separable, and non-convex. Thus, iterative heuristics are highly recommended for solving the problem due to their reasonable solution quality and relatively short computation time. At present, most iterative heuristics use sensitivity factors to select an appropriate variable which significantly improves the system reliability. The sensitivity factor represents the impact amount of each variable to the system reliability at a designated iteration. However, these heuristics are inefficient in terms of solution quality and computation time because the sensitivity factor calculations are performed only at integer variables. It results in degradation of the exploration and growth in the number of subsequent continuous nonlinear programming (NLP) subproblems. To overcome the drawbacks of existing iterative heuristics, we propose a new scaling method based on the multi-path iterative heuristics introduced by Ha (2004). The scaling method is able to compute sensitivity factors for all decision variables and results in a decreased number of NLP subproblems. In addition, the approximation heuristic for NLP subproblems helps to avoid redundant computation of NLP subproblems caused by outlined solution candidates. Numerical experimental results show that the proposed heuristic is superior to the best existing heuristic in terms of solution quality and computation time.