Search

We propose a new nonconvex regularization scheme to improve the performance of the stochastic dual dynamic programming (SDDP) algorithm for solving large-scale multistage stochastic programs. Specifically, we use a class of nonconvex regularization functions, namely folded concave penalty functions, to improve solution quality and the convergence rate of the SDDP procedure. We develop a strategy based on mixed-integer programming to guarantee global optimality of the nonconvex regularization problem. Moreover, we establish provable convergence guarantees for our customized SDDP algorithm. The benefits of our regularization scheme are demonstrated by solving large-scale instances of two multistage stochastic optimization problems. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0255) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0255). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We introduce a new optimization model, dubbed the display optimization problem, that captures a common aspect of choice behavior, known as the framing bias. In this setting, the objective is to optimize how distinct items (corresponding to products, web links, ads, etc.) are being displayed to a heterogeneous audience, whose choice preferences are influenced by the relative locations of items. Once items are assigned to vertically differentiated locations, customers consider a subset of the items displayed in the most favorable locations before picking an alternative through multinomial logit choice probabilities. The main contribution of this paper is to derive a polynomial-time approximation scheme for the display optimization problem. Our algorithm is based on an approximate dynamic programming formulation that exploits various structural properties to derive a compact state space representation of provably near-optimal item-to-position assignment decisions. As a byproduct, our results improve on existing constant-factor approximations for closely related models and apply to general distributions over consideration sets. We develop the notion of approximate assortments that may be of independent interest and applicable in additional revenue management settings. Lastly, we conduct extensive numerical studies to validate the proposed modeling approach and algorithm. Experiments on a public hotel booking data set demonstrate the superior predictive accuracy of our choice model vis-à-vis the multinomial logit choice model with location bias, proposed in earlier literature. In synthetic computational experiments, our approximation scheme dominates various benchmarks, including natural heuristics—greedy methods, local search, priority rules—and state-of-the-art algorithms developed for closely related models. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

In 1964, Kenneth Lane proposed an algorithm to optimize the production schedule of a single-metal, single-processor open pit mine. For this, he proposed a policy based on varying, over time, the so-called "cutoff grade"—or grade threshold used to determine if extracted material should be ore (processed material) or waste (thrown away). Lane's algorithm had a profound impact on the mining industry. However, though it has been used in multiple commercial software systems and has traditionally been taught to every aspiring mining engineer, it is widely considered a heuristic, and little is known regarding the quality of the solutions it produces. In this paper, we formally study Lane's problem. We show that Lane's algorithm can be viewed as an approximate dynamic programming scheme and that Lane's optimality conditions can be formally derived in two different ways: by considering a variant of the problem where the future value function is linearly approximated or by deriving the optimality conditions of a continuous-time version of the problem. We further show that Lane's algorithm can naturally be extended to this continuous-time version of the problem and that when this algorithm converges, it converges to an optimal solution. Finally, through a reformulation, we show that Lane's original problem can be solved using convex mixed-integer programming. Though hypothetical counterexamples can be constructed, computational experiments prove that Lane's algorithm can produce the optimal solution in every real-world data set tested, thereby lending solid support for its practical application. This paper was accepted by Chung Piaw Teo, optimization. [ABSTRACT FROM AUTHOR]

In the paper, "Optimistic Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds," the authors propose an extension to Monte Carlo tree search that uses the idea of "sampling the future" to produce noisy upper bounds on nodes in the decision tree. These upper bounds can help guide the tree expansion process and produce decision trees that are deeper rather than wider, in effect concentrating computation toward more useful parts of the state space. The algorithm's effectiveness is illustrated in a ride-sharing setting, where a driver/vehicle needs to make dynamic decisions regarding trip acceptance and relocations. Monte Carlo tree search (MCTS), most famously used in game-play artificial intelligence (e.g., the game of Go), is a well-known strategy for constructing approximate solutions to sequential decision problems. Its primary innovation is the use of a heuristic, known as a default policy, to obtain Monte Carlo estimates of downstream values for states in a decision tree. This information is used to iteratively expand the tree toward regions of states and actions that an optimal policy might visit. However, to guarantee convergence to the optimal action, MCTS requires the entire tree to be expanded asymptotically. In this paper, we propose a new "optimistic" tree search technique called primal-dual MCTS that uses sampled information relaxation upper bounds on potential actions to make tree expansion decisions, creating the possibility of ignoring parts of the tree that stem from highly suboptimal choices. The core contribution of this paper is to prove that despite converging to a partial decision tree in the limit, the recommended action from primal-dual MCTS is optimal. The new approach shows promise when used to optimize the behavior of a single driver navigating a graph while operating on a ride-sharing platform. Numerical experiments on a real data set of taxi trips in New Jersey suggest that primal-dual MCTS improves on standard MCTS (upper confidence trees) and other policies while exhibiting a reduced sensitivity to the size of the action space. [ABSTRACT FROM AUTHOR]

In the paper "Robust Dual Dynamic Programming," Angelos Georghiou, Angelos Tsoukalas, and Wolfram Wiesemann propose a novel solution scheme for addressing planning problems with long horizons. Such problems can be formulated as multistage robust optimization problems. The proposed method takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. The proposed scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. The promising performance of the algorithm is shown in a stylized inventory-management problem in which the proposed algorithm achieved the optimal solution in problem instances with 100 time stages in a few minutes. Multistage robust optimization problems, where the decision maker can dynamically react to consecutively observed realizations of the uncertain problem parameters, pose formidable theoretical and computational challenges. As a result, the existing solution approaches for this problem class typically determine suboptimal solutions under restrictive assumptions. In this paper, we propose a robust dual dynamic programming (RDDP) scheme for multistage robust optimization problems. The RDDP scheme takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. For problems with uncertain technology matrices and/or constraint right-hand sides, our RDDP scheme determines an optimal solution in finite time. Also, if the objective function and/or the recourse matrices are uncertain, our method converges asymptotically (but deterministically) to an optimal solution. Our RDDP scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. We show the promising performance of our algorithm in a stylized inventory management problem. Supplemental material is available at https://doi.org/10.1287/opre.2018.1835. [ABSTRACT FROM AUTHOR]

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

Sensitivities for Stochastic Optimization In optimization, sensitivities of optimal values with respect to the data of the problem are of practical as well as theoretical interest. In the paper "Envelope Theorems for Multistage Linear Stochastic Optimization," Terça and Wozabal propose a framework to compute derivatives of optimal values for a certain class of stochastic optimization problems. The results make use of classical envelope theorems and almost sure smoothness properties for optimal values of linear optimization problems, which are derived using tools from real algebraic topology. The authors show that derivatives can be sampled based on solutions obtained from stochastic dual dynamic programming and discuss two numerical case studies, demonstrating that the approach is superior, both in terms of accuracy as well as computationally, to naïve methods of computing derivatives that are based on difference quotients. We propose a method to compute derivatives of multistage linear stochastic optimization problems with respect to parameters that influence the problem's data. Our results are based on classical envelope theorems and can be used in problems directly solved via their deterministic equivalents as well as in stochastic dual dynamic programming for which the derivatives of the optimal value are sampled. We derive smoothness properties for optimal values of linear optimization problems, which we use to show that the computed derivatives are valid almost everywhere under mild assumptions. We discuss two numerical case studies, demonstrating that our approach is superior, both in terms of accuracy and computationally, to naïve methods of computing derivatives that are based on difference quotients. [ABSTRACT FROM AUTHOR]

Transforming Dynamic Optimization Problems for Enhanced Computational Efficiency Dynamic programming is one of the core algorithms for solving optimization problems in operations research, economics, finance, computer science, and numerous other fields. Although the theory itself is relatively straightforward, implementation can be computationally expensive, inhibiting application to interesting and realistic problems. This research considers a variety of transformations that can be applied to optimization problems and the key equations associated with the dynamic programming algorithm. It investigates the range of possible transformations, clarifies their links with optimality, and applies specific transformations to generate large speed gains in high-dimensional problems. Several economic applications are considered. Some approaches to solving challenging dynamic programming problems, such as Q-learning, begin by transforming the Bellman equation into an alternative functional equation to open up a new line of attack. Our paper studies this idea systematically with a focus on boosting computational efficiency. We provide a characterization of the set of valid transformations of the Bellman equation, for which validity means that the transformed Bellman equation maintains the link to optimality held by the original Bellman equation. We then examine the solutions of the transformed Bellman equations and analyze correspondingly transformed versions of the algorithms used to solve for optimal policies. These investigations yield new approaches to a variety of discrete time dynamic programming problems, including those with features such as recursive preferences or desire for robustness. Increased computational efficiency is demonstrated via time complexity arguments and numerical experiments. [ABSTRACT FROM AUTHOR]

A moving walkway (also denoted as moving sidewalk, travelator, autowalk, pedestrian conveyor, or skywalk) is a slow moving conveyor that transports standing or walking people horizontally over a short to medium distance. Constantly moving walkways have a long-lasting tradition especially inside large buildings, such as airport terminals and railway stations. Novel technological developments allow to accelerate walkways in their middle sections up to 12 km/h, while still providing a safe and much slower entrance and exit. Furthermore, first applications of moving walkways as environmentally friendly and space-efficient alternatives for urban public transport exist. In this context, our paper aims to support the layout design of moving walkways with optimization. Given a straight corridor (e.g., an airport terminal) and the passenger flows within the corridor (e.g., among gates), we aim to optimally place bidirectional walkway segments. We show that the resulting optimization problem is efficiently solvable by dynamic programming even if multiple relevant extensions, such as multiple objectives, budget constraints, and minimum safety distances, among subsequent segments are relevant. We apply our algorithm to explore the impact of constantly moving and accelerating walkways on total travel times and benchmark solutions without walkway support in a real-world case study. Our results reveal that wrongly placed walkways may considerably slow down passenger transport, but a very simple design rule leads to near-optimal results. [ABSTRACT FROM AUTHOR]

When dealing with dynamic optimization problems, time consistency is a desirable property as it allows one to solve the problem efficiently through a backward recursion. The mean-risk problem is known to be time inconsistent when considered in its scalarized form. However, when left in its original bi-objective form, it turns out to satisfy a more general time consistency property that seems better suited to a vector optimization problem. In "Time Consistency of the Mean-Risk Problem," Kováĉova and Rudloff introduce a set-valued version of the famous Bellman principle and show that the bi-objective mean-risk problem does satisfy it. Then, the upper image, a set that contains the efficient frontier on its boundary, recurses backward in time. Kováĉova and Rudloff present conditions under which this recursion can be exploited directly to compute a solution in the spirit of dynamic programming. This opens the door for a new branch in mathematics: dynamic multivariate programming. Choosing a portfolio of risky assets over time that maximizes the expected return at the same time as it minimizes portfolio risk is a classical problem in mathematical finance and is referred to as the dynamic Markowitz problem (when the risk is measured by variance) or, more generally, the dynamic mean-risk problem. In most of the literature, the mean-risk problem is scalarized, and it is well known that this scalarized problem does not satisfy the (scalar) Bellman's principle. Thus, the classical dynamic programming methods are not applicable. For the purpose of this paper we focus on the discrete time setup, and we will use a time-consistent dynamic convex risk measure to evaluate the risk of a portfolio. We will show that, when we do not scalarize the problem but leave it in its original form as a vector optimization problem, the upper images, whose boundaries contain the efficient frontiers, recurse backward in time under very mild assumptions. Thus, the dynamic mean-risk problem does satisfy a Bellman's principle, but a more general one, that seems more appropriate for a vector optimization problem: a set-valued Bellman's principle. We will present conditions under which this recursion can be exploited directly to compute a solution in the spirit of dynamic programming. Numerical examples illustrate the proposed method. The obtained results open the door for a new branch in mathematics: dynamic multivariate programming. [ABSTRACT FROM AUTHOR]

We study a new class of scheduling problems that capture common settings in service environments, in which one has to serve a collection of jobs that have a priori uncertain attributes (e.g., processing times and priorities) and the service provider has to decide how to dynamically allocate resources (e.g., people, equipment, and time) between testing (diagnosing) jobs to learn more about their respective uncertain attributes and processing jobs. The former could inform future decisions, but could delay the service time for other jobs, while the latter directly advances the processing of the jobs but requires making decisions under uncertainty. Through novel analysis we obtain surprising structural results of optimal policies that provide operational managerial insights, efficient optimal and near-optimal algorithms, and quantification of the value of testing. We believe that our approach will lead to further research to explore this important practical trade-off. The online appendix is available at https://doi.org/10.1287/mnsc.2017.2973. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

This paper addresses the dispatching problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process and dispatches them in batches for the last-mile distribution. The operator of the center aims to find the cost-minimizing consolidation policy, depending on the orders at hand, preannounced orders, and stochastic arrivals. We present this problem as a variant of the delivery dispatching problem that includes dispatch windows and define a corresponding Markov decision model. Larger instances of the problem suffer from intractably large state-, outcome-, and action spaces. We propose an approximate dynamic programming (ADP) algorithm that can handle such instances, using a linear value function approximation to estimate the downstream costs. To design the value function approximation, we construct various sets of basis functions, numerically evaluate their suitability, and discuss the properties of good basis functions for the dispatching problem. Numerical experiments on toy-sized instances show that the best set of basis functions approximates the optimal values with an error of less than 3%. To cope with large action spaces, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We test the performance of ADP on a variety of networks. ADP consistently outperforms the benchmark policies, performing particularly well when there is sufficient flexibility in dispatch times. The online appendix is available at https://doi.org/10.1287/trsc.2017.0773. [ABSTRACT FROM AUTHOR]

Recent research on location-routing problems has been focusing on locating facilities as the starting and end point of routes. In this paper, we investigate a new type of location-routing problem. In the location-routing problem with intra-route facilities, the location of depots is known, whereas the location of facilities for intermediate stops has to be determined to keep vehicles operational. We present an adaptive large neighborhood search which is enhanced by local search and dynamic programming components, and derive new penalty functions for time-efficient neighborhood evaluation. We show that this algorithm is suitable for solving various problems with intra-route facilities by deriving new best known solutions for the recently published electric location-routing problem with time windows and partial recharging, as well as for the battery swap station electric vehicle location-routing problem. Additionally, we create new real-world benchmark instances and show results as well. Furthermore, we assess the competitiveness of our algorithm on the electric vehicle routing problem with time windows for full and partial recharging, and derive new best known solutions for both problem variants. [ABSTRACT FROM AUTHOR]

This paper proposes a general framework for a large class of multiperiod principal-agent problems. In this framework, a principal has a primary stake in the performance of a system but delegates its control to an agent. The underlying system is a Markov decision process, where the state of the system can only be observed by the agent but the agent's action is observed by both parties. This paper develops a dynamic programming algorithm to derive optimal long-term contracts for the principal. The principal indirectly controls the underlying system by offering the agent a menu of continuation utility vectors along public information paths; the agent's best response, expressed in his choice of continuation utilities, induces truthful state revelation and results in actions that maximize the principal's expected payoff. This problem is meaningful to the operations research community because it can be framed as the problem of optimally designing the reward structure of a Markov decision process with hidden states and has many applications of interest as discussed in this paper [ABSTRACT FROM AUTHOR]

We develop a new method for pricing American options. The main practical contribution of this paper is a general algorithm for constructing upper and lower bounds on the true price of the option using any approximation to the option price. We show that our bounds are tight, so that if the initial approximation is close to the true price of the option, the bounds are also guaranteed to be close. We also explicitly characterize the worst-case performance of the pricing bounds. The computation of the lower bound is straightforward and relies on simulating the suboptimal exercise strategy implied by the approximate option price. The upper bound is also computed using Monte Carlo simulation. This is made feasible by the representation of the American option price as a solution of a properly defined dual minimization problem, which is the main theoretical result of this paper. Our algorithm proves to be accurate on a set of sample problems where we price call options on the maximum and the geometric mean of a collection of stocks. These numerical results suggest that our pricing method can be successfully applied to problems of practical interest. [ABSTRACT FROM AUTHOR]

The article presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network (N, A) with distances c(i, j). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty. A special feature of this linear program is that there can never be a loop in the basis, because the vectors corresponding to the variables of a loop are linearly dependent. The last comment is related to the dynamic programming algorithm. One is allowed to pass through a node more than once in the shortest route . The proposed method for solving this program consists of converting it into a shortest route problem containing exactly q arcs. But for some arbitrary reason, the dynamic program is formulated in such a way that one can never have starting node 1 more than once in the final solution.

We analyze a finite-horizon dynamic pricing model in which demand at each period depends on not only the current price but also past prices through reference prices. A unique feature but also a significant challenge in this model is the asymmetry in reference price effect, which implies that the underlying optimization problem is nonsmooth and no standard optimization methods can be applied. We identify a few key structural properties of the problem, which enable us to develop strongly polynomial-time algorithms to compute the optimal prices for several plausible scenarios. We complement our exact algorithms by proposing an approximation heuristic and provide an upper bound on the optimal objective value. Finally, we conduct numerical experiments to study the optimal price path and demonstrate the value of dynamic pricing when demands are seasonal. We further compare numerically one of the exact algorithms with the heuristic and offer managerial suggestions. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different "pockets." This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines. [ABSTRACT FROM AUTHOR]

This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]

We consider the multilevel lot-sizing problem with production capacities (MLSP-PC), in which production and trans- portation decisions are made for a serial supply chain with capacitated production and concave cost functions. Existing approaches to the multistage version of this problem are limited to nonspeculative cost functions--up to now, no algorithm for the multistage version of this model with general concave cost functions has been developed. In this paper, we develop the first polynomial algorithm for the MLSP-PC with general concave costs at all of the stages, and we introduce a novel approach to overcome the limitations of previous approaches. In contrast to traditional approaches to lot-sizing problems, in which the problem is decomposed by time periods and is analyzed unidirectionally in time, we solve the problem by introducing the concept of a basis path, which is characterized by time and stage. Our dynamic programming algorithm proceeds both forward and backward in time along this basis path, enabling us to solve the problem in polynomial time. [ABSTRACT FROM AUTHOR]

This paper studies an infinite horizon adverse selection model with an underlying Markov information process. It introduces a graphic representation of continuation contracts and continuation payoff frontiers, namely finite policy graph, and provides an algorithm to approximate the optimal policy graph through iterations. The algorithm performs an additional step after each value iteration--replacing dominated points on the previous continuation payoff frontier by points on the new frontier and reevaluating the new frontier. This dominance-free reevaluation step accelerates the convergence of the continuation payoff frontiers. Numerical examples demonstrate the effectiveness of this algorithm and properties of the optimal contracts. [ABSTRACT FROM AUTHOR]

This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In 1958, Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, a fundamental model that is embedded in many practical production planning problems. In this paper, we consider a basic version of this model in which problem parameters are stochastic: the stochastic uncapacitated lot-sizing problem. We define the production-path property of an optimal solution for our model and use this property to develop a backward dynamic programming recursion. This approach allows us to show that the value function is piecewise linear and right continuous. We then use these results to show that a full characterization of the optimal value function can be obtained by a dynamic programming algorithm in polynomial time for the case that each nonleaf node contains at least two children. Moreover, we show that our approach leads to a polynomial-time algorithm to obtain an optimal solution to any instance of the stochastic uncapacitated lot-sizing problem, regardless of the structure of the scenario tree. We also show that the value function for the problem without setup costs is continuous, piecewise linear, and convex, and therefore an even more efficient dynamic programming algorithm can be developed for this special case. [ABSTRACT FROM AUTHOR]

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n²k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n²k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning. [ABSTRACT FROM AUTHOR]

This paper considers a dynamic and stochastic routing problem in which information about customer locations and probabilistic information about future service requests are used to maximize the expected number of customers served by a single uncapacitated vehicle. The problem is modeled as a Markov decision process, and analytical results on the structure of the optimal policy are derived. For the case of a single dynamic customer, we completely characterize the optimal policy. Using the analytical results, we propose a real-time heuristic and demonstrate its effectiveness compared with a series of other intuitively appealing heuristics. We also use computational tests to determine the heuristic value of knowing both customer locations and probabilistic information about future service requests. [ABSTRACT FROM AUTHOR]

Continuous review stock systems are considered in this paper. They are modeled using discrete time dynamic programming, which in contrast to previous continuous time formulations of the problem, yields a reasonable algorithm for computational purposes. The model is used to establish the optimal forms of stationary ordering policies under various cost assumptions. [ABSTRACT FROM AUTHOR]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

In this paper we study a class of modified policy iteration algorithms for solving Markov decision problems. These correspond to performing policy evaluation by successive approximations. We discuss the relationship of these algorithms to Newton-Kantorovich iteration and demonstrate their covergence. We show that all of these algorithms converge at least as quickly as successive approximations and obtain estimates of their rates of convergence. An analysis of the computational requirements of these algorithms suggests that they may be appropriate for solving problems with either large numbers of actions, large numbers of states, sparse transition matrices, or small discount rates. These algorithms are compared to policy iteration, successive approximations, and Gauss-Seidel methods on large randomly generated test problems. [ABSTRACT FROM AUTHOR]

One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period--we call it a demand time window--during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T²) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T³). [ABSTRACT FROM AUTHOR]

This paper approaches the assembly-line balancing problem as a sequencing problem involving precedence constraints that prohibit the occurrence of certain orderings. This approach permits the formulation of a dynamic programming algorithm for the exact solution of small assembly-line balancing problem. A generalization of this algorithm combined with a successive approximations technique is used for the solution of large problems. In addition, certain combinatorial problems associated with partially ordered sets are formulated and discussed in detail. These problems arise whenever sequencing problems with precedence constraints are treated by dynamic programming techniques. [ABSTRACT FROM AUTHOR]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

This paper develops dynamic-programming and other shortest-route algorithms for optimizing sequentially patterned questioning procedures, called diagnostic questionnaires. It uses graph-theoretic methods and solves certain combinatorial problems associated with the Catalan numbers. The paper obtains general properties of optimal questionnaires, including an ordering relation, a convexity result, and the determination of essentially complete classes of questionnaires. It explores a logarithmic charging scheme in detail and obtains a minimax result. Finally, the paper examines the relation with Huffman coding of information theory, and a simple method of Shannon efficiency. [ABSTRACT FROM AUTHOR]

In this paper we examine computational complexity issues and develop algorithms for a class of"shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is "easy" because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the combined routing and scheduling problem is nontrivial. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing the maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics that are bounded by constant. We also discuss how these algorithms perform on practical data. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of the capacitated dynamic lot size problem, where, over time, the setup costs are nonincreasing, the unit holding costs have arbitrary pattern, the unit production costs are nonincreasing and the capacities are nondecreasing. We investigate the properties of the optimal solution for the problem and develop the concept of candidate subplan. It is proven that only the candidate subplans need to be examined in searching for an optimal solution. A dynamic programming algorithm, incorporating the concept of candidate subplan, is then devised which has run time complexity of O(T[SUP2]). [ABSTRACT FROM AUTHOR]

The solution technique developed in this paper integrates the simplex search algorithm into the recursive calculations of dynamic programming in order to mitigate the "curse-of-dimensionality." Since differentiation is not required as a means of optimization procedure, it is expected that this technique will have an important impact on planning problems, such as the multiple resource allocation problems which involve nondifferentiable and/or highly nonlinear performance functions. Applications of the technique to very complex problems seem to confirm the anticipated polynomial average performance. [ABSTRACT FROM AUTHOR]

This paper describes a decentralized linear programming solution procedure. Unlike the classic Dantzig-Wolfe decomposition algorithm, this procedure is a complete decentralization, where the subproblems act independently to generate the optimal solution. In Dantzig-Wolfe decomposition, the master problem must "dictate" the final optimal solution. Our procedure is an improvement over Dantzig-Wolfe decomposition in this sense. The procedure works by adding a "coercion" function to the subproblem objective. Under proper conditions, this function "coerces" the subproblem to behave as desired. Such total decentralization is important for loosely coupled systems where it is not possible for the master level to dictate optimal decision values for the subsystems. [ABSTRACT FROM AUTHOR]

One of the major contributions to the planning and management of Research and Development organizations is the evolution of methods for dealing with PERT-Cost or CPM-Cost problems. Classically however, variations of the critical path-cost (CPM-Cost) problem, arising when different cost duration relationships are assumed, have been mostly studied via techniques other than dynamic programming. If the precedence relations possess a serial structure, one can develop two essentially equivalent dynamic programming formulations, of the resource allocation variety, by minimizing either the project cost or the completion time. When nonserial precedence relationships are involved, this problem cannot be solved by routine invocation of conventional dynamic programming formulations or algorithms. The intent of this paper is to show that efficient nonserial dynamic programming formulations can be developed for several complex nonserial CPM-Cost problem situations. In particular, the project time minimization procedure results in less complex dynamic programming models and is thus employed in this paper. Three recent computational reduction techniques based primarily on the introduction of the artifice of pseudo-tasks and pseudo-stages are invoked to treat different variations of this essentially nonserial critical path-cost problem. Considerable savings in computational requirements are achieved by consolidating all phases preceding a junction node prior to the invocation of the dynamic programming procedure. The advantages of these approaches over existing mathematical programming methods include their ability to handle nonlinear cost functions and constraints, as well as their highly efficient parametrization capabilities. Further, the complexity of the dynamic programming formulation does not, unlike other methods, increase with the number of phases (tasks) but only with the degree in which the additional tasks change the structure of the precedence relations. [ABSTRACT FROM AUTHOR]

Many nonlinear programming algorithms utilize a one-dimensional search along directions generated by the algorithm. This paper describes a method for performing this search. The method finds 3 points which bracket the minimum, fits a quadratic through them to yield a fourth point, then fits successive cubics through 4 points, discarding one each time, until certain stop criteria are met. No gradient evaluations are required. Detailed flow charts of this procedure are given, and its performance is compared with that of 2 other algorithms. Eight test problems are used in this comparison, each solved using both exterior and interior penalty functions. The Davidon-Fletcher-Powell method is used to generate the search directions. Results show that the proposed procedure requires about ½ to ¾ the computer time of its nearest competitor, a procedure designed to be especially efficient when applied to penalty functions, and about &frac13 the time of the other competitor, the 2 point cubic search using derivatives. [ABSTRACT FROM AUTHOR]

This paper explores the normative theory of simulation within the context of an optimization algorithm for a linear programming model of the experimental setting. The simulation is viewed as a random generalized mathematical function which provides an uncertain evaluation of any policy within a specified constraint set. A sequential experimental design aimed at identifying the feasible levels of the policy variables which provide the optimal level of expected response is presented and analyzed. The results of numerical tests of the proposed procedure are discussed. [ABSTRACT FROM AUTHOR]

In this paper, we study a multiechelon uncapacitated lot-sizing problem in series (m-ULS), where the output of the intermediate echelons has its own external demand and is also an input to the next echelon. We propose a polynomial-time dynamic programming algorithm, which gives a tight, compact extended formulation for the two-echelon case (2-ULS). Next, we present a family of valid inequalities for m-ULS, show its strength, and give a polynomial-time separation algorithm. We establish a hierarchy between the alternative formulations for 2-ULS. In particular, we show that our valid inequalities can be obtained from the projection of the multicommodity formulation. Our computational results show that this extended formulation is very effective in solving our uncapacitated multi-item two-echelon test problems. In addition, for capacitated multi-item, multiechelon problems, we demonstrate the effectiveness of a branch-and-cut algorithm using the proposed inequalities. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for finding a minimum-weight generalized matching in a weighted bipartite graph. Computational evidence is given that indicates that the time required to find a least-cost assignment of n jobs to n workers goes roughly as n[sub2] for 10=

This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish ship-owning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master program in the decomposition algorithm is an LP problem with only zero-one elements in the matrix and the right-hand side. Integer solutions are not guaranteed, but generation and solution of a large number of problems indicates that the frequency of fractional solutions is as small as 1-2 per cent. Problems with about 40 ships and 50 cargoes are solved in about 2.5 minutes on an IBM 7090. In order to resolve the fractional cases, some integer programming experiments have been made. The results will be reported in a forthcoming paper. [ABSTRACT FROM AUTHOR]

Randomly-generated linear programming problems of three different types and five different sizes were solved by the criss-cross method and by the simplex method. One hundred problems of each type and size were solved, and the results are overwhelmingly favorable to the criss-cross method. An improvement to the criss-cross method used in these tests is given, and the extension of the results of the paper to variations of the criss-cross and simplex methods is discussed. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

This paper presents a grouping procedure which yields improved solutions to Bomberger's Lot Size Scheduling Problem [1]. The group definition is a generalization of the group definition proposed by Stankard and Gupta [3]. Moreover, the generalization leads to a pseudo dynamic programming procedure which is readily programmable. Computational experience has shown the procedure to be extremely efficient. [ABSTRACT FROM AUTHOR]

This paper extends the results of "Duality in Discrete Programming" [1] to the case of quadratic objective functions. The paper is, however, self-contained. A pair of symmetric dual quadratic programs is generalized by constraining some of the variables to belong to arbitrary sets of real numbers. Quadratic all-integer and mixed-integer programs are special cases of these problems. The resulting primal problem is shown, subject to a qualification, to have an optimal solution if and only if the dual has one, and in this case the values of their respective objective functions are equal. The dual of a mixed-integer quadratic program can be formulated as a minimax problem whose quadratic objective function is linear in the integer-constrained variables, and whose linear constraint set does not contain the latter. Based on this approach an algorithm is developed for solving integer and mixed-integer quadratic programs. [ABSTRACT FROM AUTHOR]

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered, it is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules. [ABSTRACT FROM AUTHOR]

This paper presents results which apply to convex programming problem in parametric form. The results secured are also related to the problem of fractional programming in a way which indicates computational possibilities for the latter class of problems. The results are extended to general non-linear programming problems with special reference to continuous criterion functions. As a particular case, the linear fractional programming problem is considered and, in conclusion, the results secured here are pointed up by reference to existing algorithms for the latter class of problems. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of dynamic programming problems requiring the determination of optimal policies for the control of a special class of stochastic processes when the time horizon of the planning period is at infinity. These processes can be mathematically described as discrete time parameter Markov chains with a finite number of states which have been "embedded" in continuous time in the sense that the time between transitions is a random variable whose probability distribution depends only on the states between which the transition takes place. Such processes are called Markov-renewal processes. The Markov processes considered by R. A. Howard in [1] are really two special cases of this somewhat wider class of stochastic processes. In these two special cases, the algorithm of this paper is identical with Howard's. In fact, with only slight modification, Howard's algorithm can be extended to this wider class of stochastic processes. [ABSTRACT FROM AUTHOR]

The well known chemical equilibrium problem is expressed in the form of minimizing the free energy of a mixture in order to compute the chemical composition at equilibrium. By piece-wise linear approximations to the free energy function, the problem becomes a linear program which can be solved by a standard code on a computing machine. Successive approximations give any degree of accuracy. [ABSTRACT FROM AUTHOR]