On VLSI interconnect optimization and linear ordering problem

Some well-known VLSI interconnect optimizations problems for timing, power and cross-coupling noise immunity share a property that enables mapping them into a specialized Linear Ordering Problem (LOP). Unlike the general LOP problem which is NP-complete, this paper proves that the specialized one has a closed-form solution. Let f(x,y):?²→? be symmetric, non-negative, defined for x≥0 and y≥0, and let f(x,y) be twice differentiable, satisfying ? ² f(x,y)/?x?y<0. Let π be a permutation of {1,…,n}. The specialized LOP comprises n objects, each associated with a real value parameter r _i , 1≤i≤n, and a cost f(r _i ,r _j ) associated to any two objects if |π(i)?π(j)|=1,1≤i,j≤n, and f(r _i ,r _j )=0 otherwise. We show that the permutation π which minimizes \(\sum_{i= 1}^{n - 1} f( r_{\pi^{ - 1}( i )},r_{\pi^{ - 1}( i + 1 )} )\), called “symmetric hill”, is determined upfront by the relations between the parameter values r _i .     

An optimal ordering strategy for a third-party managed supply chain

The rapid pace of new product introduction and global sourcing of raw materials and manufacturing facilities have created a complex and fragmented supply chain. Retailers in many consumer product industries are relying on third-party supply-chain managers (SCMs) to manage the global supply chain cost-effectively with short production lead times. To meet delivery requirements, the SCM must start the production process before receiving a firm order from retailers. We assume a two-stage production process where, in stage 1, a base product is produced. In stage 2, the base product is customised. The SCM absorbs the penalties associated with over- or underestimating retailers’ demand. Hence, the SCM has to decide on (a) the optimal production quantity of the base products and (b) the number of base products to be customised without delay. We develop a profit maximisation model for this strategy using a nonlinear objective function with two decision variables and one constraint. Applying Kuhn–Tucker conditions, closed-form solutions are obtained for the two decision variables. Also, formulations are given for two additional strategies: postpone customisation of all products and produce customised products only. An example illustrates the use of our model. We also examine the impact of demand variability on the effectiveness of the three strategies. Results show that postponement may not always be the best strategy for an SCM.     

An optimal control problem in estimating the optimal control force for the force vibration system

An optimal control problem for the force vibration system based on the iterative regularization method, i.e. the conjugate gradient method (CGM), is examined to estimate the optimal control force in a damped system having time‐dependent system parameters such that the desire (or design) system displacements can be satisfied. It is assumed that no prior information is available on the functional form of the unknown control function in the present study, thus, it is classified as the function estimation. Numerical simulations are performed to test the validity of the present algorithm by using different types of the desire system displacements. Results show that an excellent estimation on the optimal control force can be obtained with arbitrary initial guesses within a couple of second's CPU time at Pentium III‐500 MHz PC. Copyright © 2001 John Wiley & Sons, Ltd.     

Parallelization of the Volterra algorithm for linear optimal open loop control

If and when the time variation of optimal controls of a linear system subject to known forces is required, they can be obtained by the computationally advantageous open loop Volterra formulation (as opposed to the costlier Riccati formulation). For the computation, the Volterra equation is discretized in the time domain via such schemes as trapezoidal integration or SIMPSON's rule and the resulting linear system is solved to obtain the control vector values at discrete time points within the control timeT. In the case of very large order systems (degrees of freedom 5000) a parallel technique is absolutely neccessary, and this paper enunciates an efficient parallel stratagem with efficiencies in the range of 80% and 100%. The algorithm uses s + 1 processors, s being the number of intervals within the control timeT, and typically each processor characterizes one time point.The research described herein was carried out at the Jet Propulsion Laboratory, California Institute of Technology under contract with the National Aeronautics and Space Administration (NASA)     

Beam analogy for optimal control of linear dynamic systems

 Optimal control problems for linear dynamic systems with quadratic performance index are solved using the beam analogy. The governing equations for the optimal maneuver are derived in the form of coupled fourth order differential equations in the time domain. These equations are uncoupled using modal variables. Next, each independent equation is made analogous to the corresponding problem of a beam on an elastic foundation. The beam problem in the spatial domain is solved using standard FEM software. Finally the FEM results are transferred back to the time domain where they represent the optimal trajectories and controls for the dynamic system. Received 12 October 1999     

An optimal procedure for solving the hierarchical network design problem

The hierarchical network design problem consists of finding a minimum cost bilevel network that connects all the nodes in a set, created by a loopless main path and a forest. The main path is formed by primary (higher cost) arcs, providing a path between an origin node and a destination node. The forest, built using secondary (lower cost) arcs, connects all the nodes not on the main path, to the path itself. We state and prove some properties of the problem, which allow finding good upper bounds to the solution in polynomial time when the primary costs are proportional to secondary costs. We also propose an O(n⁴) procedure to improve on these bounds. In turn, these bounds are used to significantly reduce the number of nodes and arcs of the problem. Once the problem is reduced, large instances can be solved to optimality. At this stage, we use one of two linear integer optimization formulations. The first and preferred one is based on multicommodity flows, which avoids the formation of subtours. The second formulation avoids subtours by iteratively adding ad hoc constraints. We show some examples and provide computational experiments performed on networks with sizes up to 600 nodes and 14 000 arcs.     

Efficient formulation and heuristics for multi-item single source ordering problem with transportation cost

Integrated inventory and transportation decisions are critical in the supply chain, providing significant gains for all parties. In this paper, we present a mathematical formulation for the dynamic demand multi-item single source replenishment problem with a piecewise linear transportation cost. Through an extensive experimental study, we find that the new formulation provides a tighter LP relaxation of the problem, while requiring fewer computational resources to optimally solve the problem when compared with existing model in the literature. We also present a new metaheuristic for this general class of coordinated capacitated replenishment problems. On average, the solutions from heuristics are within 1.23% of the optimal solution for the comprehensive set of test problems.     

Phase equilibrium and interphase transition layer as an ordering problem

The model of a binary ordering alloy, developed previously based on the conventional distribution method, is used for describing spatially inhomogeneous multiphase equilibrium systems of gas-solid, liquid-gas or crystal-liquid types, including the structure of an interphase transition layer. General results are illustrated by specific predictions for a two-phase crystal-gas system.Academic Scientific Complex A. V. Luikov Heat and Mass Transfer Institute of the Belarussian Academy of Sciences, Minsk. Translated from Inzhenerno-Fizicheskii Zhurnal, Vol. 65, No. 2, pp. 198–206, August, 1993.     

Boundary element method for the Cauchy problem in linear elasticity

In this paper, the iterative algorithm proposed by Kozlov et al. [Comput Maths Math Phys 32 (1991) 45] for obtaining approximate solutions to ill-posed boundary value problems in linear elasticity is analysed. The technique is then numerically implemented using the boundary element method (BEM). The numerical results obtained confirm that the iterative BEM produces a convergent and stable numerical solution with respect to increasing the number of boundary elements and decreasing the amount of noise added into the input data. An efficient stopping regularizing criterion is given and in addition, the accuracy of the iterative algorithm is improved by using a variable relaxation procedure. Analytical formulae for the integration constants resulting from the direct application of the BEM for an isotropic linear elastic medium are also presented.     

Selection of an optimal set of cutting-tools for a general triangular pocket

The size(s) of the cutting-tool (end-mill) chosen for machining a given pocket has a significant impact on the machining time. However, the selection of cutting-tool sizes is typically based on human judgment and estimates, and is therefore prone to be conservative and non-optimal. The focus of this paper is on the development of a procedure for selection of an optimal set of cutting-tools for staircase milling of general triangular pockets with round corners, such that the machining time is minimized. We first derive analytical models for determining the time for machining the pocket using a given cutting-tool. Subsequently, we employ a dynamicprogramming based approach that utilizes these analytical models to determine the best set of cutting-tools, from the available inventory of cutting-tools, to machine the pocket. The proposed approach can be extended for optimal selection of cutting-tools for rough-machining of 3-D sculptured cavities.     

The optimal production and shipment policy for the single-vendor singlebuyer integrated production-inventory problem

This paper considers the problem of a vendor (manufacturer) supplying a product to a buyer (customer). The vendor manufactures the product in batches at a finite rate and ships the output to the buyer. The buyer then consumes the product at a fixed rate. The objective is to minimize the mean total cost per unit time of manufacturing set-up, stock transfer and stock holding. Previously published work has concentrated on finding optimal solutions from within given classes of policy. We derive the structure of the globally-optimal solution, set out an algorithm for obtaining it and illustrate the process with two numerical examples.     

Finite element methods for an optimal steady-state control problem

An optimal steady-state control problem governed by an elliptic state equation is solved by several finite element methods. Finite element discretizations are applied to different variational formulations of the problem yielding accurate numerical results as compared with the given analytical solution. It is sated that, for minimum computational effort and high accuracy, ‘mixed’ finite elements requiring only C° continuity, and approximating the control and state functions simultaneously are better suited to similar ‘fourth order’ problems.     

Computational method for optimal machine scheduling problem with maintenance and production

This paper considers an optimal scheduling problem of maintenance and production for a machine. Firstly, the problem is formulated as a stochastic switched impulsive optimal control problem. However, there exists the stochastic disturbance in this model. Thus, it is difficult to solve the problem by conventional optimisation techniques. To overcome this difficulty, the stochastic switched impulsive optimal control problem is transformed into a deterministic switched impulsive optimal control problem with continuous state inequality constraints. Then, by combining a time-scaling transformation, a second-order smoothing technique and a penalty function method, an improved Newton algorithm is developed for solving this problem. Convergence results indicate that the algorithm is globally convergent with quadratic rate. Finally, two numerical examples are provided to illustrate the effectiveness of the developed algorithm.     

Normed linear spaces and optimal design of discrete systems

Summary The behaviour of discrete mechanical or electrical systems under the action of disturbances shall be weighted. In a space which contains the solutions of the corresponding differential equations appropriate norms are introduced. The optimal design problem can then be interpreted as an approximation problem for the zero solution. A method for the delivering from the initial conditions is proposed.     

Central limit theorem for the estimator of the value of an optimal stopping problem

We consider an optimal stopping problem defined on a finite Markov chain whose transition probabilities are unknown. We prove a central limit theorem for the maximum likelihood estimator and the stretch estimator of the optimal value of the optimal stopping problem. Also, we propose a perturbation technique to weaken the hypotheses of the central limit theorem. The author was supported by a grant from the SpanishScretaría de Estado de Educación y Universidades in cooperation with the European Social Funds.     

A simple linear heuristic for the service constrained random yield problem

We consider the problem of setting order quantities for purchased components subject to uncertainty in the delivery amounts. Assuming the periodic production volumes (demands)to be known and constant, we model this as a random yield problem with the objective of minimizing average inventory cost subject to a service level constraint over the infinite horizon. We first demonstrate that under conditions of random yield, conventional definitions of service can be inappropriate. Then we refine the definition of service for random yield cases and use this to formulate an optimization model. Exact solution of this model proves to be computationally impractical and, as we show, the common heuristic of inflating demands by a constant proportion is not robustly accurate. Therefore, we develop a new heuristic, which we term the linear inflation policy, that specifies a linear function for the inflation factors. Numerical tests indicate that this heuristic can substantially outperform the traditional constant inflation policy and works well relative to a lower bound on the optimal solution on a range of examples.