Type II sensitivity analysis of cost coefficients in the degenerate transportation problem

This paper focuses on sensitivity analysis of the degenerate transportation problem (DTP) when perturbation occurs on one cost coefficient. The conventional Type I sensitivity analysis of the transportation problem (TP) determines the perturbation ranges for the invariant optimal basis. Due to different degenerate optimal basic solutions yielding different Type I ranges, the Type I range is misleading for the DTP. Type II sensitivity analysis, which determines the perturbation ranges for the invariant shipping pattern, is more practical for the DTP. However, it is too tedious to obtain Type II ranges by enumerating all optimal basic solutions and all primal optimal basic solutions while getting the union of each corresponding Type I ranges. Here, we propose two labeling algorithms to determine the Type II ranges of the cost coefficient. Besides, three lemmas are provided for obtaining the upper bound or lower bound of the Type II ranges of the cost coefficient directly under specific conditions of the DTP. A numerical example is given to demonstrate the procedure of the proposed labeling algorithms and computational results have been provided.     

Postoptimality Analyses of the Transportation Problem

We develop here a new approach to postoptimality analyses of the transportation problem (TP) through the use of perturbation analysis. In contrast to the usual sensitivity analysis the proposed methods allow for simultaneous, independent (or dependent) perturbation of the supplies, demands and transportation rates cost from their nominal values whilst preserving the current optimal basis. The essential parts of the calculation involve the same manipulations as the solution algorithm used in solving the parametric perturbed supply-demand version of the nominal TP. Furthermore, the coefficient of the perturbed parameters in the optimal parametric cost function is used to indicate the existence of a cheaper (or equivalent cost) solution than the current optimal one by shipping more total goods. The proposed approach permits computation of the maximal allowable additional units and distribution of these extra units in a systematic manner. The proposed unified procedures are demonstrated by numerical examples.     

Optimal PID control in case of random initial conditions

The aim of this presentation is to construct a robust optimal PID feedback controller, taking into account stochastic uncertainties in the initial conditions. Usually, a precomputed feedback control is based on exactly known model parameters. However, in practice, often exact information about model parameters and initial values is not given. Hence, having an inital point, which differs from the nominal values, a standard precomputed controller may produce bad results. Supposing now that the probability distribution of the random parameter variations is known, in the following stochastic optimisation methods will be applied in order to obtain robust optimal feedback controls. Taking into account stochastic parameter variations at the initial point, the method works with expected total costs arising from the primary control expenses and the tracking error. Furthermore, the free regulator parameters are selected then such that the expected total costs are minimized. After Taylor expansion to calculate expected cost functions and a few transformations an approximate deterministic substitute control problem follows. Here, retaining only linear terms, approximation of expectations and variances of the expected cost functions can be calculated explicitly. By means of splines, numerical approximations of the objective function and the differential equations are obtained then. Using stochastic optimization methods, random parameter variations are incorporated into the optimal control process. Hence, robust optimal feedback controls are obtained. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Use of the Transportation Method of Linear Programming in Production Planning: A Case Study<Superscript>†</Superscript>

An application of the transportation method of linear programming to a production planning problem of a large footwear manufacturer is described. Factors affecting the choice of approach are discussed along with details of data requirements and their implications. Results, including a comparison of the analytic solution with that obtained by management judgement, and related sensitivity analyses are presented. The model used in one sub-problem is detailed in the appendix and incorporates spare capacity constraints and conditions on product mix but preserves the standard transportation format. An additional ratio constraint is satisfied algebraically after obtaining an original optimal solution.     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

多阶段生产系统最优生产批量和原材料订购决策模型

Sarker和Parija(1996)建立了生产系统最优生产批量和原材料订购决策模型。然而他们的模型仅局限于单阶段生产系统,本文将他们的模型扩展到多阶段生产系统,我们首先建立了使整个多阶段生产系统总成本最小的各阶段最优生产批量、原材料订购批量及阶段之间的运输批量模型,然后分析了原材料订购费、半成品运费及设备安装费的敏感性。最后,我们结合实例综合分析了原材料订购费、半成品运输费和设备安装费的变化及最小值点取整后对原材料订购决策、最优生产批量和总成本的影响。     

Optimal stopping with continuous control of piecewise deterministic Markov processes

In this paper we consider the problem of optimal stopping and continuous control on some local parameters of a piecewise-deterministic Markov processes (PDP's). Optimality equations are obtained in terms of a set of variational inequalities as well as on the first jump time operator of the PDP. It is shown that if the final cost function is absolutely continuous along trajectories then so is the value function of the optimal stopping problem with continuous control. These results unify and generalize previous ones in the current literature.     

A supply chain design problem with facility location and bi-objective transportation choices

A supply chain design problem based on a two-echelon single-product system is addressed. The product is distributed from plants to distribution centers and then to customers. There are several transportation channels available for each pair of facilities between echelons. These transportation channels introduce a cost?Ctime tradeoff in the problem that allows us to formulate it as a bi-objective mixed-integer program. The decisions to be taken are the location of the distribution centers, the selection of the transportation channels, and the flow between facilities. Three variations of the classic ??-constraint method for generating optimal Pareto fronts are studied in this paper. The procedures are tested over six different classes of instance sets. The three sets of smallest size were solved completely obtaining their efficient solution set. It was observed that one of the three proposed algorithms consistently outperformed the other two in terms of their execution time. Additionally, four schemes for obtaining lower bound sets are studied. These schemes are based on linear programming relaxations of the model. The contribution of this work is the introduction of a new bi-objective optimization problem, and a computational study of the ??-constraint methods for obtaining optimal efficient fronts and the lower bounding schemes.     

Optimal control of assignment of jobs to processors under heavy traffic

The paper is concerned with the optimal control of the assignment of jobs from several arriving random streams to one of a bank of processors. Owing to the difficulty of the general problem, a heavy traffic approach is used. The required work depends on the processor to which it is assigned. The information that the assignment can be based on is quite flexible, and several information structures (data on which the control is based) are considered. The assignment can be made on arrival or when the job is to be processed. There can be bursty arrivals (the bursts depending on randomly varying environmental factors), rather general nonlinear cost functions and other complications. It is shown, under reasonably general conditions, that the optimal costs for the physical systems converge to the optimal cost for the heavy traffic limit problem, as the heavy traffic parameter goes to its limit. Numerical data is presented to illustrate some of the potential uses of the limit process for obtaining optimal contros, or controls satisfying optimal tradeoffs among competing criteria. The methods of proof are quite powerful tools for such optimal control problems     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

Optimal control of greenhouse climate: methodology

This report describes a methodology for obtaining optimal operating rules for the equipment influencing the climatic conditions inside a greenhouse. The optimization is based on an economic criterion which takes into account the expected income from the crops versus the cost of operating and maintaining the greenhouse.The optimal control function is characterized and the analytic conditions for optimality are derived. A numerical scheme for obtaining the desired control is described and a sensitivity analysis is then carried out. This analysis enables derivation of simple operating rules for a real greenhouse.     

Optimum life testing plans in presence of hybrid censoring: A cost function approach

Hybrid censoring scheme is a combination of Type‐I and Type‐II censoring schemes. Determination of optimum hybrid censoring scheme is an important practical issue in designing life testing experiments to enhance the information on reliability of the product. In this work, we consider determination of optimum life testing plans under hybrid censoring scheme by minimizing the total cost associated with the experiment. It is shown that the proposed cost function is scale invariant for some selected distributions. Optimum solution cannot be obtained analytically. We propose a method for obtaining the optimum solution and consider Weibull distribution for illustration. We also studied the sensitivity of the optimal solution to the misspecification of parameter values and cost components through a well‐designed sensitivity analysis. Copyright © 2013 John Wiley & Sons, Ltd.     

Numerical Computation of Optimal Feed Rates for a Fed-Batch Fermentation Model

In this paper, we consider a model for a fed-batch fermentation process which describes the biosynthesis of penicillin. First, we solve the problem numerically by using a direct shooting method. By discretization of the control variable, we transform the basic optimal control problem to a finite-dimensional nonlinear programming problem, which is solved numerically by a standard SQP method. Contrary to earlier investigations (Luus, 1993), we consider the problem as a free final time problem, thus obtaining an improved value of the penicillin output. The results indicate that the assumption of a continuous control which underlies the discretization scheme seems not to be valid. In a second step, we apply classical optimal control theory to the fed-batch fermentation problem. We derive a boundary-value problem (BVP) with switching conditions, which can be solved numerically by multiple shooting techniques. It turns out that this BVP is sensitive, which is due to the rigid behavior of the specific growth rate functions. By relaxation of the characteristic parameters, we obtain a simpler BVP, which can be solved by using the predicted control structure (Lim et al., 1986). Now, by path continuation methods, the parameters are changed up to the original values. Thus, we obtain a solution which satisfies all first-order and second-order necessary conditions of optimal control theory. The solution is similar to the one obtained by direct methods, but in addition it contains certain very small bang-bang subarcs of the control. Earlier results on the maximal output of penicillin are improved.     

Optimal mode-switching for hybrid systems with varying initial states

This paper concerns a particular aspect of the optimal control problem for switched systems that change modes whenever the state intersects certain switching surfaces. These surfaces are assumed to be parameterized by a finite dimensional switching parameter, and the optimization problem we consider is that of minimizing a given cost-functional with respect to the switching parameter under the assumption that the initial state of the system is not a priori known. We approach this problem from two different vantage points by first minimizing the worst possible cost over the given set of initial states using results from min–max optimization. The second approach is based on a sensitivity analysis in which variational arguments give the derivative of the switching parameters with respect to the initial conditions.     

An Efficient Monte Carlo Method for Optimal Control Problems with Uncertainty

A general framework is proposed for what we call the sensitivity derivative Monte Carlo (SDMC) solution of optimal control problems with a stochastic parameter. This method employs the residual in the first-order Taylor series expansion of the cost functional in terms of the stochastic parameter rather than the cost functional itself. A rigorous estimate is derived for the variance of the residual, and it is verified by numerical experiments involving the generalized steady-state Burgers equation with a stochastic coefficient of viscosity. Specifically, the numerical results show that for a given number of samples, the present method yields an order of magnitude higher accuracy than a conventional Monte Carlo method. In other words, the proposed variance reduction method based on sensitivity derivatives is shown to accelerate convergence of the Monte Carlo method. As the sensitivity derivatives are computed only at the mean values of the relevant parameters, the related extra cost of the proposed method is a fraction of the total time of the Monte Carlo method.     

Optimal PID controller of robots under stochastic uncertainty

In practice often it is not possible to specify exact model parameters. Hence, precomputed controller based on some parameter estimates can produce bad results. In this presentation the aim is to combine classical PID control theory and stochastic optimisation methods in order to obtain robust optimal feedback control. The method works with cost functions being minimized and takes into account stochastic parameter varations. After Taylor expansion to calculate expected cost functions and a few transformations an approximate deterministic substitute PID control problem follows. Here, retaining only linear terms, approximation of expectations and variances of the expected cost functions can be calculated explicitly. By means of splines, numerical approximations of the objective function and the differential equations are obtained then. Using stochastic optimization methods, random parameter variations are incorporated into the optimal control process. Hence, robust optimal feedback controls are obtained. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sensitivity of constrained Markov decision processes

We consider the optimization of finite-state, finite-action Markov decision processes under constraints. Costs and constraints are of the discounted or average type, and possibly finite-horizon. We investigate the sensitivity of the optimal cost and optimal policy to changes in various parameters. We relate several optimization problems to a generic linear program, through which we investigate sensitivity issues. We establish conditions for the continuity of the optimal value in the discount factor. In particular, the optimal value and optimal policy for the expected average cost are obtained as limits of the dicounted case, as the discount factor goes to one. This generalizes a well-known result for the unconstrained case. We also establish the continuity in the discount factor for certain non-stationary policies. We then discuss the sensitivity of optimal policies and optimal values to small changes in the transition matrix and in the instantaneous cost functions. The importance of the last two results is related to the performance of adaptive policies for constrained MDP under various cost criteria [3,5]. Finally, we establish the convergence of the optimal value for the discounted constrained finite horizon problem to the optimal value of the corresponding infinite horizon problem.     

Optimal sensitivity based on IPOPT

We introduce a flexible, open source implementation that provides the optimal sensitivity of solutions of nonlinear programming (NLP) problems, and is adapted to a fast solver based on a barrier NLP method. The program, called sIPOPT evaluates the sensitivity of the Karush?CKuhn?CTucker (KKT) system with respect to perturbation parameters. It is paired with the open-source IPOPT NLP solver and reuses matrix factorizations from the solver, so that sensitivities to parameters are determined with minimal computational cost. Aside from estimating sensitivities for parametric NLPs, the program provides approximate NLP solutions for nonlinear model predictive control and state estimation. These are enabled by pre-factored KKT matrices and a fix-relax strategy based on Schur complements. In addition, reduced Hessians are obtained at minimal cost and these are particularly effective to approximate covariance matrices in parameter and state estimation problems. The sIPOPT program is demonstrated on four case studies to illustrate all of these features.     

Optimal observation network in geostatistics and underground hydrology

Mathematical models and algorithms for the optimal design of data collection for regionalized variables are presented. The topics considered subsume as a special case optimal drilling strategies in hydrology, the mining industries and other geostatistical applications. In these disciplines an optimal design is a critical consideration since data, can only be obtained through an expensive drilling process.The methods given here are based on the theory of regionalized variables and of kriging. The basis of the methods for locating a single additional data point, and for locating multiple points, is the theory of minimizing uncertainty in parameter estimation. That is, the possible locations of additional points must be determined on the basis of surface analysis with respect to the projected costs of obtaining this data.After a summary of basic kriging techniques, four models are discussed. The first deals with the optimal location problem for a single experimental point, and the second, third and fourth models pertain to the case of multiple additional points. (Unfortunately the repeated application of the single-point model leads only to approximations of the global optima, since the global optima are usually unobtainable as a simple sum of the partial optima.) In the second model, an optimal regular observation network is to be designed to minimize the uncertainty of the estimation process subject to either the given number of additional data, or an upper bound for the cost of the additional data. In the fourth model, the number or cost of additional points is minimized subject to bounded uncertainty conditions. Finally, a numerical example will be used to illustrate the models and algorithms.     

Choosing Optimal Parameters in Iterative Processes

We consider the problem of choosing optimal parameters in certain iterative procedures. Specifically, we are interested in finite-step processes for which it is possible to estimate the computational cost and the error relaxation in terms of the process parameters. The problem of finding the optimal process that provides the required error relaxation with a minimal total computational cost is defined and studied. To solve the problem, it is generally necessary to solve a series of mathematical programming problems with rapidly increasing dimension. We suggest two ways to avoid that difficulty. The first is to find a process that is close to the optimal process, by solving only one mathematical programming problem. The second is to define optimal processes in some special cases when this problem can be simplified. We define conditions under which processes with geometrically decreasing error are optimal or asymptotically optimal. The methods of finding parameters of such processes are also provided. We illustrate our ideas with two examples: the bilevel gradient method for unconstrained function minimization and the iterative process for solving an optimal design problem.