Implicit algorithms for solving the Cauchy problem for the equations of the dynamics of mechanical systems

It is shown that in the numerical solution of the Cauchy problem for systems of second-order ordinary differential equations, when solved for the highest-order derivative, it is possible to construct simple and economical implicit computational algorithms for step-by-step integration without using laborious iterative procedures based on processes of the Newton-Raphson iterative type. The initial problem must first be transformed to a new argument — the length of its integral curve. Such a transformation is carried out using an equation relating the initial parameter of the problem to the length of the integral curve. The linear acceleration method is used as an example to demonstrate the procedure of constructing an implicit algorithm using simple iterations for the numerical solution of the transformed Cauchy problem. Propositions concerning the computational properties of the iterative process are formulated and proved. Explicit estimates are given for an integration stepsize that guarantees the convergence of the simple iterations. The efficacy of the proposed procedure is demonstrated by the numerical solution of three problems. A comparative analysis is carried out of the numerical solutions obtained with and without parametrization of the initial problems in these three settings. As a qualitative test the problem of the celestial mechanics of the “Pleiades” is considered. The second example is devoted to modelling the non-linear dynamics of an elastic flexible rod fixed at one end as a cantilever and coiled in its initial (static) state into a ring by a bending moment. The third example demonstrates the numerical solution of the problem of the “unfolding” of a mechanical system consisting of three flexible rods with given control input.     

On the determination of the control parameters of the optimal can-order policy

This paper considers the well-known class of can-order policies. This type of coordinated replenishment policies accounts for a joint set-up cost structure, where a major set-up cost is incurred for any order and an individual minor set-up cost is charged for each item in the replenishment. Recent comparative studies have pointed out that the performance of the optimal can-order policy is poor, compared to other coordinated replenishment strategies, when the major set-up cost is high. This paper shows that it is the approximate decomposition method to calculate the optimal canorder parameters which performs bad in such situations and not the policy itself. Attention is focused to a subclass of can-order policies, which is close to the optimal can-order policy for high major set-up costs. A solution procedure is developed to calculate the optimal control parameters of this policy. It is shown that a properly chosen combination of the solution procedures to calculate can-order parameters leads to a can-order strategy which performs as well as other coordinated replenishment policies.     

An Alternative Procedure for Determining the Optimal Policy for an Inventory Item Having Linear Trend in Demand

In this paper we develop an iterative procedure for determining the optimal replenishment policy for an item having linear trend in demand. Shortages are permitted for the inventory item and can be backordered. Our optimal procedure is easier to apply than an earlier solution method reported in inventory literature with linearly time-varying demand and shortages. Two examples are included to illustrate the iterative procedure.     

Minimum Spanning Trees with Sums of Ratios

We present an algorithm for finding a minimum spanning tree where the costs are the sum of two linear ratios. We show how upper and lower bounds may be quickly generated. By associating each ratio value with a new variable in `image space,' we show how to tighten these bounds by optimally solving a sequence of constrained minimum spanning tree problems. The resulting iterative algorithm then finds the globally optimal solution. Two procedures are presented to speed up the basic algorithm. One relies on the structure of the problem to find a locally optimal solution while the other is independent of the problem structure. Both are shown to be effective in reducing the computational effort. Numerical results are presented.     

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.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

An optimal solution technique for the joint replenishment problem with storage and transport capacities and budget constraints

The joint replenishment problem, which is concerned with the problem of coordinating the replenishment of a group of items that may be ordered jointly, has been studied extensively and many heuristic solution procedures have been presented in the literature. To obtain the minimum of the total cost, the main complexity lies in determining the appropriate lower bound of the basic cycle time. Also there is a lack of a global optimal solution technique of the problem. This paper presents its extended model to include some practical issues and develops a simple procedure to calculate the appropriate lower bound of the basic cycle time. By a comparative study of a numerical example, it demonstrates the inabilities of the available lower bound formulae in the literature. It also develops a generalized global optimal solution algorithm of the extended model and illustrates this with a numerical example. Then a comparative study of the results of seven numerical examples is carried out to highlight the global optimality of the solution technique.     

Adaptive policies for multi-mode project scheduling under uncertainty

In this paper we propose an adaptive model for multi-mode project scheduling under uncertainty. We assume that there is a due date for concluding the project and a tardiness penalty for failing to meet this due date, and that several distinct modes may be used to undertake each activity. We define scheduling policies based on a set of thresholds. The starting time of the activity is compared with those thresholds in order to define the execution mode.We propose a procedure, based on the electromagnetism heuristic, for choosing a scheduling policy. In computational tests, we conclude that the adaptive scheduling policy found by using the model and the heuristic solution procedure is consistently better than the optimal non-adaptive policy. When the different modes have very different characteristics and there is a reasonable difference between the average duration of the project and the due date, the cost advantage of the adaptive policy becomes very significant.     

Fixed Point Methods for the Complementarity Problem

This paper is concerned with iterative procedures for the monotone complementarity problem. Our iterative methods consist of finding fixed points of appropriate continuous maps. In the case of the linear complementarity problem, it is shown that the problem is solvable if and only if the sequence of iterates is bounded in which case summability methods are used to find a solution of the problem. This procedure is then used to find a solution of the nonlinear complementarity problem satisfying certain regularity conditions for which the problem has a nonempty bounded solution set.     

Production-inventory control policy under warm/cold state-dependent fixed costs and stochastic demand: partial characterization and heuristics

The motivation for our study comes from some production and inventory systems in which ordering/producing quantities that exceed certain thresholds in a given period might eliminate some setup activities in the next period. Many examples of such systems have been discussed in prior research but the analysis has been limited to production settings under deterministic demand. In this paper, we consider a periodic-review production-inventory model under stochastic demand and incorporate the following fixed-cost structure into our analysis. When the order quantity in a given period exceeds a specified threshold value, the system is assumed to be in a “warm” state and no fixed cost is incurred in the next period regardless of the order quantity; otherwise the system state is considered “cold” and a positive fixed cost is required to place an order. Assuming that the unsatisfied demand is lost, we develop a dynamic programming formulation of the problem and utilize the concepts of quasi-K-convexity and non-K-decreasing to show some structural results on the optimal cost-to-go functions. This analysis enables us to derive a partial characterization of the optimal policy under the assumption that the demands follow a Pólya or uniform distribution. The optimal policy is defined over multiple decision regions for each system state. We develop heuristic policies that are aimed to address the partially characterized decisions, simplify the ordering policy, and save computational efforts in implementation. The numerical experiments conducted on a large set of test instances including uniform, normal and Poisson demand distributions show that a heuristic policy that is inspired by the optimal policy is able to find the optimal solution in almost all instances, and that a so-called generalized base-stock policy provides quite satisfactory results under reasonable computational efforts. We use our numerical examples to generate insights on the impact of problem parameters. Finally, we extend our analysis into the infinite horizon setting and show that the structure of the optimal policy remains similar.     

Minimizing the Total Cost in an Integrated Vendor—Managed Inventory System

In this paper we consider a complex production-distribution system, where a facility produces (or orders from an external supplier) several items which are distributed to a set of retailers by a fleet of vehicles. We consider Vendor-Managed Inventory (VMI) policies, in which the facility knows the inventory levels of the retailers and takes care of their replenishment policies. The production (or ordering) policy, the retailers replenishment policies and the transportation policy have to be determined so as to minimize the total system cost. The cost includes the fixed and variable production costs at the facility, the inventory costs at the facility and at the retailers and the transportation costs, that is the fixed costs of the vehicles and the traveling costs. We study two different types of VMI policies: The order-up-to level policy, in which the order-up-to level quantity is shipped to each retailer whenever served (i.e. the quantity delivered to each retailer is such that the maximum level of the inventory at the retailer is reached) and the fill-fill-dump policy, in which the order-up-to level quantity is shipped to all but the last retailer on each delivery route, while the quantity delivered to the last retailer is the minimum between the order-up-to level quantity and the residual transportation capacity of the vehicle. We propose two different decompositions of the problem and optimal or heuristic procedures for the solution of the subproblems. We show that, for reasonable initial values of the variables, the order in which the subproblems are solved does not influence the final solution. We will first solve the distribution subproblem and then the production subproblem. The computational results show that the fill-fill-dump policy reduces the average cost with respect to the order-up-to level policy and that one of the decompositions is more effective. Moreover, we compare the VMI policies with the more traditional Retailer-Managed Inventory (RMI) policy and show that the VMI policies significantly reduce the average cost with respect to the RMI policy.     

Examining military medical evacuation dispatching policies utilizing a Markov decision process model of a controlled queueing system

Military medical planners must develop dispatching policies that dictate how aerial medical evacuation (MEDEVAC) units are utilized during major combat operations. The objective of this research is to determine how to optimally dispatch MEDEVAC units in response to 9-line MEDEVAC requests to maximize MEDEVAC system performance. A discounted, infinite horizon Markov decision process (MDP) model is developed to examine the MEDEVAC dispatching problem. The MDP model allows the dispatching authority to accept, reject, or queue incoming requests based on a request’s classification (i.e., zone and precedence level) and the state of the MEDEVAC system. A representative planning scenario based on contingency operations in southern Afghanistan is utilized to investigate the differences between the optimal dispatching policy and three practitioner-friendly myopic policies. Two computational experiments are conducted to examine the impact of selected MEDEVAC problem features on the optimal policy and the system performance measure. Several excursions are examined to identify how the 9-line MEDEVAC request arrival rate and the MEDEVAC flight speeds impact the optimal dispatching policy. Results indicate that dispatching MEDEVAC units considering the precedence level of requests and the locations of busy MEDEVAC units increases the performance of the MEDEVAC system. These results inform the development and implementation of MEDEVAC tactics, techniques, and procedures by military medical planners. Moreover, an analysis of solution approaches for the MEDEVAC dispatching problem reveals that the policy iteration algorithm substantially outperforms the linear programming algorithms executed by CPLEX 12.6 with regard to computational effort. This result supports the claim that policy iteration remains the superlative solution algorithm for exactly solving computationally tractable Markov decision problems.     

Computing a Stationary Base-Stock Policy for a Finite Horizon Stochastic Inventory Problem with Non-linear Shortage Costs

Abstract

We consider a periodic-review stochastic inventory problem in which demands for a single product in each of a finite number of periods are independent and identically distributed random variables. We analyze the case where shortages (stockouts) are penalized via fixed and proportional costs simultaneously. For this problem, due to the finiteness of the planning horizon and non-linearity of the shortage costs, computing the optimal inventory policy requires a substantial effort as noted in the previous literature. Hence, our paper is aimed at reducing this computational burden. As a resolution, we propose to compute “the best stationary policy.” To this end, we restrict our attention to the class of stationary base-stock policies, and show that the multi-period, stochastic, dynamic problem at hand can be reduced to a deterministic, static equivalent. Using this important result, we introduce a model for computing an optimal stationary base-stock policy for the finite horizon problem under consideration. Fundamental analytic conclusions, some numerical examples, and related research findings are also discussed.     

Optimal EOQ Models for Deteriorating Items with Time-Varying Demand

In this paper, optimal inventory lot-sizing models are developed for deteriorating items with general continuous time-varying demand over a finite planning horizon and under three replenishment policies. The deterioration rate is assumed to be a constant fraction of the on-hand inventory. Shortages are permitted and are completely backordered. The proposed solution procedures are shown to generate global minimum replenishment schedules for both general increasing and decreasing demand patterns. An extensive empirical comparison using randomly generated linear and exponential demands revealed that the replenishment policy which starts with shortages in every cycle is the least cost policy and the replenishment policy which prohibits shortages in the last cycle exhibited the best service level effectiveness. An optimal procedure for the same problem with trended inventory subject to a single constraint on the minimum service level (maximum fraction of time the inventory system is out of stock during the planning horizon) is also proposed in this paper.     

Fuzzy clustering algorithms and their cluster validity

A non metric clustering algorithm based on a fuzzy objective function which reflects proximity based on some global dissimilarity measure is proposed.The global optimal solution is shown to be difficult to obtain and an alternative iterative procedure is presented. This procedure is easily implemented and converges to a local optimum.Some validity functionals which measure the effectiveness with which cluster structure has been identified are compared in relation with the iterative procedures described in the paper.     

A branch-and-cut algorithm for the equicut problem

We describe an algorithm for solving the equicut problem on complete graphs. The core of the algorithm is a cutting-plane procedure that exploits a subset of the linear inequalities defining the convex hull of the incidence vectors of the edge sets that define an equicut. The cuts are generated by several separation procedures that will be described in the paper. Whenever the cutting-plane procedure does not terminate with an optimal solution, the algorithm uses a branch-and-cut strategy. We also describe the implementation of the algorithm and the interface with the LP solver. Finally, we report on computational results on dense instances with sizes up to 100 nodes.     

The mathematical model and optimistic algorithm of two protein structures alignment

Protein structure alignment is one of the most important computational problems in molecular biology. From the viewpoint of computational complexity, a pairwise structure alignment is a NP-hard problem. In this paper, based on the discrepancy of two proteins, we define the structure alignment as a mixed integer-programming (MIP) problem with the simpler form and prove the existence of optimal solution. The optimal alignment is achieved by incorporating improved complete information set method used to modify the score matrix into iterative double dynamic programming algorithm. Convergence of algorithm is proved. A number of benchmark examples are tested. The results show that our model and approach are general and improve computational efficiency as well as quality of the structure alignment.     

Optimal Continuous Policies for Repair and Replacement

This paper investigates the problem of finding optimal replacement policies for equipment subject to failures with randomly distributed repair costs, the degree of reliability of the equipment being considered as a state of a Markov process. Algorithms have been devised to find optimal combined policies both for preventive replacement and for replacement in case of failure by using repair-limit strategies.First a simple procedure to obtain an optimal discrete policy is described. Then an algorithm is formulated in order to calculate an optimal continuous policy: it is shown how the optimal repair limit is the solution to an ordinary differential equation, and how the value of the repair limit determines the optimal preventive replacement policy.     

Optimal Stopping with a Probabilistic Constraint

We present an efficient method for solving optimal stopping problems with a probabilistic constraint. The goal is to optimize the expected cumulative cost, but constrained by an upper bound on the probability that the cost exceeds a specified threshold. This probabilistic constraint causes optimal policies to be time-dependent and randomized, however, we show that an optimal policy can always be selected with “piecewise-monotonic” time-dependence and “nearly-deterministic” randomization. We prove these properties using the Bellman optimality equations for a Lagrangian relaxation of the original problem. We present an algorithm that exploits these properties for computational efficiency. Its performance and the structure of optimal policies are illustrated on two numerical examples.