Optimal power control in a wireless network using a model with stochastic link coefficients

This paper addresses optimal power allocation in a wireless communication network under uncertainty. The paper introduces a framework for optimal transmit power allocation in a wireless network where both the useful and interference coefficients are random. The new approach to power control is based on a stochastic programming formulation with probabilistic SIR constraints. This allows to state the power allocation problem as a convex optimization problem assuming normally or log‐normally distributed communication link coefficients. Numerical examples illustrate the performance of the optimal stochastic power allocation. A distributed algorithm for the decentralized solution of the stochastic power allocation problem is discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Optimal capacity in a coordinated supply chain

We consider a supply chain in which a retailer faces a stochastic demand, incurs backorder and inventory holding costs and uses a periodic review system to place orders from a manufacturer. The manufacturer must fill the entire order. The manufacturer incurs costs of overtime and undertime if the order deviates from the planned production capacity. We determine the optimal capacity for the manufacturer in case there is no coordination with the retailer as well as in case there is full coordination with the retailer. When there is no coordination the optimal capacity for the manufacturer is found by solving a newsvendor problem. When there is coordination, we present a dynamic programming formulation and establish that the optimal ordering policy for the retailer is characterized by two parameters. The optimal coordinated capacity for the manufacturer can then be obtained by solving a nonlinear programming problem. We present an efficient exact algorithm and a heuristic algorithm for computing the manufacturer's capacity. We discuss the impact of coordination on the supply chain cost as well as on the manufacturer's capacity. We also identify the situations in which coordination is most beneficial. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Robust capacity planning in semiconductor manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to identify a set of tools that is a good compromise for all these scenarios. More precisely, we formulate a mixed‐integer program in which expected value of the unmet demand is minimized subject to capacity and budget constraints. This is a difficult two‐stage stochastic mixed‐integer program which cannot be solved to optimality in a reasonable amount of time. We instead propose a heuristic that can produce near‐optimal solutions. Our heuristic strengthens the linear programming relaxation of the formulation with cutting planes and performs limited enumeration. Analyses of the results in some real‐life situations are also presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Statistical decision analysis of stochastic linear programming problems

This paper presents a statistical decision analysis of a one-stage linear programming problem with deterministic constraints and stochastic criterion function. Procedures for obtaining numerical results are given which are applicable to any problem having this general form. We begin by stating the statistical decision problems to be considered, and then discuss the expected value of perfect information and the expected value of sample information. In obtaining these quantities, use is made of the distribution of the optimal value of the linear programming problem with stochastic criterion function, and so we discuss Monte Carlo and numerical integration procedures for estimating the mean of this distribution. The case in which the random criterion vector has a multivariate Normal distribution is discussed separately, and more detailed methods are offered. We discuss dual problems, including some relationships of this work with other work in probabilistic linear programming. An example is given in Appendix A showing application of the methods to a sample problem. In Appendix B we consider the accuracy of a procedure for approximating the expected value of information.     

The discrete max-min problem

The historic max-min problem is examined as a discrete process rather than in its more usual continuous mode. Since the practical application of the max-min model usually involves discrete objects such as ballistic missiles, the discrete formulation of the problem seems quite appropriate. This paper uses an illegal modification to the dynamic programming process to obtain an upper bound to the max-min value. Then a second but legal application of dynamic programming to the minimization part of the problem for a fixed maximizing vector will give a lower bound to the max-min value. Concepts of optimal stopping rules may be applied to indicate when sufficiently near optimal solutions have been obtained.     

Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

A two product dynamic economic lot size production model with either-or production constraints

This paper considers the production of two products with known demands over a finite set of periods. The production and inventory carrying costs for each product are assumed to be concave. We seek the minimum cost production schedule meeting all demands, without backlogging, assuming that at most one of the two products can be produced in any period. The optimization problem is first stated as a nonlinear programming problem, which allows the proof of a result permitting the search for the optimal policy to be restricted to those which produce a product only when its inventory level is zero. A dynamic programming formulation is given and the model is then formulated as a shortest route problem in a specially constructed network.     

Robust tower location for code division multiple access networks

Designing Code Division Multiple Access networks includes determining optimal locations of radio towers and assigning customer markets to the towers. In this paper, we describe a deterministic model for tower location and a stochastic model to optimize revenue given a set of constructed towers. We integrate these models in a stochastic integer programming problem with simple recourse that optimizes the location of towers under demand uncertainty. We develop algorithms using Benders' reformulation, and we provide computational results. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

Probability density function of a stochastic linear programming problem

A stochastic linear programming problem under the “wait-and-see” situation is studied. After the conditions for the interchange of the order of integration and differentiation are surveyed, an explicit form of the probability density function of the stochastic linear programming problem is found. An example is also given to illustrate the result.     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

A note on parallel machine replacement

Jones, Zydiak, and Hopp [1] consider the parallel machine replacement problem (PMRP), in which there are both fixed and variable costs associated with replacing machines. Increasing maintenance cost motivates replacements, and a fixed replacement cost provides incentive for replacing machines of the same age in clusters. They prove two intuitive but important results for finite- or infinite-horizon PMRPs, which significantly reduce the size of the linear programming (LP) formulation of the problem and computing efforts required to obtain an optimal replacement policy. Their results are the no-splitting rule (NSR) and the older cluster replacement rule (OCRR). Under a slightly weaker set of assumptions, we prove a third rule, the all-or-none rule (AONR), which states that in any period, an optimal policy is to keep or to replace all the machines regardless of age. This result further reduces the size of the LP formulation of the PMRP. © 1993 John Wiley & Sons, Inc.     

A stochastic programming approach for chemotherapy appointment scheduling

Chemotherapy appointment scheduling is a challenging problem due to the uncertainty in premedication and infusion durations. In this paper, we formulate a two‐stage stochastic mixed integer programming model for the chemotherapy appointment scheduling problem under limited availability of nurses and infusion chairs. The objective is to minimize the expected weighted sum of nurse overtime, chair idle time, and patient waiting time. The computational burden to solve real‐life instances of this problem to optimality is significantly high, even in the deterministic case. To overcome this burden, we incorporate valid bounds and symmetry breaking constraints. Progressive hedging algorithm is implemented in order to solve the improved formulation heuristically. We enhance the algorithm through a penalty update method, cycle detection and variable fixing mechanisms, and a linear approximation of the objective function. Using numerical experiments based on real data from a major oncology hospital, we compare our solution approach with several scheduling heuristics from the relevant literature, generate managerial insights related to the impact of the number of nurses and chairs on appointment schedules, and estimate the value of stochastic solution to assess the significance of considering uncertainty.     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

一种新的装备配置优化模型

传统的装备配置优化问题一般采用确定性的数学规划方法解决,难以满足高技术条件下现代战争中需要对大量随机现象和模糊现象进行精确定量分析的实际要求。在分析了高技术条件下装备配置问题一般特性的基础上,根据机会约束规划和模糊机会约束规划的思想,提出了一种新的建立装备配置优化模型的思路和方法,并给出了基于随机模拟的遗传算法的实值算例,算例结果与实际情况基本相符,反映了模型的科学性与实用性。     

Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach

This paper considers the two different flow shop scheduling problems that arise when, in a two machine problem, one machine is characterized by sequence dependent setup times. The objective is to determine a schedule that minimizes makespan. After establishing the optimally of permutation schedules for both of these problems, an efficient dynamic programming formulation is developed for each of them. Each of these formulations is shown to be comparable, from a computational standpoint, to the corresponding formulation of the traveling salesman problem. Then, the relative merits of the dynamic programming and branch and bound approaches to these two scheduling problems are discussed.     

Optimal state-dependent pricing policies for a class of stochastic multiunit service systems

This paper models a k-unit service system (e.g., a repair, maintenance, or rental facility) with Poisson arrivals, exponential service times, and no queue. If we denote the number of units that are busy as the state of the system, the state-dependent pricing model formalizes the intuitive notion that when most units are idle, the price (i.e., the service charge per unit time) should be low, and when most units are busy, the price should be higher than the average. A computationally efficient algorithm based on a nonlinear programming formulation of the problem is provided for determination of the optimal state-dependent prices. The procedure ultimately reduces to the search on a single variable in an interval to determine the unique intersection point of a concave increasing function and a linear decreasing function. The algorithm takes, on the average, only about 1/2 second per problem on the IBM 360/65 (FORTRAN G Compiler). A discrete optimal-control approach to the problem is shown to result in essentially the same procedure as the nonlinear-programming formulation. Several properties of the optimal state-dependent prices are given. Comparisons of the optimal values of the objective function for the state-dependent and state-independent pricing policies show that the former is on the average, only about 0.7% better than the latter, which may explain partly why state-dependent pricing is not prevalent in many service systems. Potential generalizations of the model are discussed.