Discounted semi-Markov decision processes: linear programming and policy iteration

For semi-Markov decision processes with discounted rewards we derive the well known results regarding the structure of optimal strategies (nonrandomized, stationary Markov strategies) and the standard algorithms (linear programming, policy iteration). Our analysis is completely based on a primal linear programming formulation of the problem.     

An algorithm for the generalized transportation problem

This paper describes a new computational technique for solving spatial economic equilibrium problems which are generalizations of the classic transportation problem. This technique makes use of a type of algorithm which has been developed in recent years to compute Kakutani fixed points and solve related problems. Existing algorithms for the generalized transportation problem employ quadratic programming, and therefore require that demand and supply functions be linear. By contrast, the algorithm of this paper can handle demand and supply relationships which are nonlinear or even semi-continuous. It can also handle non-constant transport costs and various other complications. The technique is capable of yielding highly accurate solutions, and appears to be computationally efficient on problems of reasonable size.     

A chance-constrained multiobjective model for mental health services planning.

Mental health services planning, and particularly the planning for deinstitutionalization, is a very complex problem. This paper suggests a chance-constrained goal programming (CCGP) approach to mental health services planning. The CCGP approach is based on the sequential solution of a linear programming formulation, allowing efficient solution of large-scale planning problems using commercially available linear programming computer codes. The procedure is demonstrated with a case example and implementation of the approach is discussed.     

Constrained Kalman Filtering: Additional Results

This paper deals with linear state space modelling subject to general linear constraints on the state vector. The discussion concentrates on four topics: the constrained Kalman filtering versus the recursive restricted least squares estimator; a new proof of the constrained Kalman filtering under a conditional expectation framework; linear constraints under a reduced state space modelling; and state vector prediction under linear constraints. The techniques proposed are illustrated in two real problems. The first problem is related to investment analysis under a dynamic factor model, whereas the second is about making constrained predictions within a GDP benchmarking estimation.     

A note on spatial and temporal price and allocation modeling: Quadratic programming or linear complementary programming?

This paper presents a clarification of the specific conditions under which the linear complementary programming (LCP) formulation, instead of the quadratic programming (QP) formulation, is applicable in such areas as spatial and temporal price and allocation modeling. An important condition for the use of the LCP formulation is that the coefficient matrix of the demand and/or supply functions is asymmetric. Dynamic formulations can be treated as a LCP but it is demonstrated that the problem can be reformulated in a standard QP format.     

A Hybrid Approach to Quantitative Software Project Scheduling Within Agile Frameworks

In this article we focus on the quantitative project scheduling problem in IT companies that apply the agile management philosophy and Scrum, in particular. We combine mathematical programming with an agile project flow using a modified multi‐mode resource constrained project scheduling model for software projects (MRCPS^SP). The proposed approach can be used to generate schedules as benchmarks for agile development iterations. Computational experiments based on real project data indicate that this approach significantly reduces the project cycle time. The approach can be a useful addition to agile project management, especially for software projects with predefined deadlines and budgets.     

Currently practiced formulations for the assembly line balance problem

New formulations for the assembly line balance problem are proposed based on interviews and surveys of practicing engineers. These formulations are the basis for a model in goal programming form. A branch-and-bound algorithm is developed which can solve the model for an optimum solution. Computational studies show that computer run time is very modest for moderate size problems.Interviews and a survey of practicing engineers were used to develop a list of goals or constraints germane to the assembly line balance problem. These included minimizing working areas or employees, making sure tasks assigned to a station do not exceed the cycle time, and adhering to sequence constraints. These constraints are included in most traditional models. However, additional goals were mentioned. These included avoiding changes in workload assigned to a work area, adhering to layout requirements of the plant, making combinations of tasks interesting, avoiding the combination of physiologically demanding tasks, etc.The additional goals above are incorporated in a new formulation for the assembly line balance problem. This formulation is in goal programming form. The goal programming model attempts to minimize deviations from goals. If deviations are necessary, lowest ranked goals are violated first. The objective function of the model is based on an ordinal ranking of goals only. The survey mentioned above showed that engineers did not find it difficult to rank the importance of goals.The proposed goal programming model is a mixed integer linear program. Previous studies have shown that cutting plane and implicit enumeration techniques are inferior to branch-and-bound algorithms. A branch-and-bound method, called GoalOriented Algorithm for Line Balance (GOAL), is developed to solve the formulations proposed in the paper.GOAL was computationally tested with 50 problems. These problems varied in size from 4 to 35 tasks. One of the problems was an engine cradle assembly problem encountered by an automobile manufacturer. Computer run times appeared reasonable. For example, the engine cradle problem 35 tasks) required only 16.3 seconds CPU on the DEC PDF at California State University, Northridge. GOAL's execution time appeared linearly proportional to the number of tasks required for most problems.     

一种基于线段树的动态规划优化算法

动态规划是解决多阶段决策最优化问题的一种思想方法，也是ACM程序设计竞赛中常用的算法。本文首先讨论了动态规划的基本思想和解题步骤。但基本动态规划对于数据规模很大的问题，在解题过程中还是存在效率和占用空间非常大的问题，本文巧妙利用线段树优化动态规划，提高对大规模数据处理的方法和技巧，在线段树基础上利用树状数组合理地解决了动态规划占用大量内存的问题。     

A Unifying Framework and Comparison of Algorithms for Non-negative Matrix Factorisation

Non-negative matrix factorisation (NMF) is an increasingly popular unsupervised learning method. However, parameter estimation in the NMF model is a difficult high-dimensional optimisation problem. We consider algorithms of the alternating least squares type. Solutions to the least squares problem fall in two categories. The first category is iterative algorithms, which include algorithms such as the majorise–minimise (MM) algorithm, coordinate descent, gradient descent and the Févotte-Cemgil expectation–maximisation (FC-EM) algorithm. We introduce a new family of iterative updates based on a generalisation of the FC-EM algorithm. The coordinate descent, gradient descent and FC-EM algorithms are special cases of this new EM family of iterative procedures. Curiously, we show that the MM algorithm is never a member of our general EM algorithm. The second category is based on cone projection. We describe and prove a cone projection algorithm tailored to the non-negative least square problem. We compare the algorithms on a test case and on the problem of identifying mutational signatures in human cancer. We generally find that cone projection is an attractive choice. Furthermore, in the cancer application, we find that a mix-and-match strategy performs better than running each algorithm in isolation.     

Evaluation of scheduling techniques for solving flowshop problems with no intermediate storage

The flowshop scheduling problem with no intermediate storage (NIS problem) was studied in this research. This problem, a modification of the classical flowshop scheduling problem, arises when a set of jobs, once started, must be processed with no wait between consecutive machines. By eliminating the need for intermediate storage, reduction of capital investment in work-in-process inventory can be achieved. This approach can be practically applied to a steel mill, in which the metal should be continuously processed in order to maintain high temperature, as well as many other similar processes.To provide insight into selecting an appropriate scheduling technique for solving the NIS problem, six methods were compared in terms of the quality and efficiency of the scheduling solutions they produced. The quality of solution was measured by makespan and the efficiency of solution was measured by the computational time requirements. The six methods examined in this study included: the Gupta algorithm, the Szwarc algorithm, an integer linear programming method, the Campbell et al. algorithm, the Dannenbring rapid access with extensive search algorithm, and a mixed integer linear programming procedure.The problem factors considered in this study were number of jobs, number of machines, and range of processing times. Relatively small-sized problems were tested with up to ten jobs, five machines, and 1–100 processing time units. Six solution techniques were selected and compared, with respect to makespan and computational time requirements, for multiple combinations of the three problem variables.The resulting test data were investigated using graphical procedures and formal statistical analyses. Initially, plots of mean values were used to graphically compare the six solution methods for the two performance criteria. Next, a multivariate analysis of variance study was conducted to investigate the quality and efficiency of the algorithms with respect to the problem factors. Then, a multiple comparison procedure was employed to analyze treatment mean differences among the six solution techniques. Results from the statistical analyses are summarized in this article.It was concluded that the two mathematical programming methods, the integer linear programming procedure and the mixed integer linear programming methods, produced the best performance in terms of makespan. These two methods, however, used a far greater amount of computational time than the other four solution techniques. Producing moderately good results as far as quality of performance, the Gupta and the Szwarc algorithms were comparable with the Campbell et al. and the Dannenbring algorithms in terms of computational efficiency. By comparison, the Campbell et al. and the Dannenbring algorithms produced the poorest performance with respect to the quality of solutions.Certain limitations were imposed for this study. The problem size considered was relatively small and the sample size was also limited to ten problems per cell. In addition, a uniform distribution function was used for generating processing times within certain ranges. These limitations were necessary in order to allow the various scheduling problems to be solved within a reasonable amount of computer time.Finally, some suggestions were provided for future research in the NIS problem area. The integer linear programming method was recommended as a standard of evaluation, owing to its best overall performance. A possible area for future research would involve the improvement of the Gupta and the Szwarc algorithms through the use of backtracking procedures within the branch-and-bound technique, so that they might be competitive with the mathematical programming methods with respect to quality of performance. Other distribution functions could be investigated in terms of the influence of the distribution of processing times on the performance measures.     

Scheduling identical jobs on uniform parallel machines

We address the problem of scheduling n identical jobs on m uniform parallel machines to optimize scheduling criteria that are nondecreasing in the job completion times. It is well known that this can be formulated as a linear assignment problem, and subsequently solved in O ( n ³) time. We give a more concise formulation for minsum criteria, and show that general minmax criteria can be minimized in O ( n ²) time. We present faster algorithms, requiring only O ( n + m log m ) time for minimizing makespan and total completion time, O ( n log n ) time for minimizing total weighted completion time, maximum lateness, total tardiness and the weighted number of tardy jobs, and O ( n log² n ) time for maximum weighted tardiness. In the case of release dates, we propose an O ( n log n ) algorithm for minimizing makespan, and an O ( mn ^2m+1) time dynamic programming algorithm for minimizing total completion time.     

Optimal strategies in linear multisector models: Value function and optimality conditions

In this paper we study an optimal control problem with mixed constraints related to a multisector linear model with endogenous growth. The main aim is to establish a set of necessary and a set of sufficient conditions which are the basis for studying the qualitative properties of optimal trajectories. The presence of possibly degenerate mixed constraints, the unboundedness and non-strict convexity of the Hamiltonian, make the problem difficult to deal with. We develop first the dynamic programming approach, proving that the value function is a bilateral viscosity solution to the associated Hamilton–Jacobi–Bellman (HJB) equation. Then, using our results, we give a set of sufficient and a set of necessary optimality conditions which involve so-called co-state inclusion: this can be interpreted as the existence of a dual path of prices supporting the optimal path.     

基于动态规划改进求解VRP问题节约法的DSM模型及其拓展分析

提出了改进求解VRP问题节约法的DSM模型(动态规划节约法),将代表启发式算法的节约法与代表精确算法的动态规划相结合,建立不断增加节约量的动态规划数学模型,使其得到全局最优解。该法计算过程平稳收敛,对增加约束条件的情况更易接受。     

A nonsmooth approach to envelope theorems

We develop a nonsmooth approach to envelope theorems applicable to a broad class of parameterized constrained nonlinear optimization problems that arise typically in economic applications with nonconvexities and/or nonsmooth objectives. Our methods emphasize the role of the Strict Mangasarian–Fromovitz Constraint Qualification (SMFCQ), and include envelope theorems for both the convex and nonconvex case, allow for noninterior solutions as well as equality and inequality constraints. We give new sufficient conditions for the value function to be directionally differentiable, as well as continuously differentiable. We apply our results to stochastic growth models with Markov shocks and constrained lattice programming problems.     

Design method evaluation—an experiment with corridor selection

The improvement of the process of design requires the evaluation of alternative design methods. A framework for evaluating graphically based, intuitive design methods is (1) solve a set of problems with a proven algorithm, (2) have a sample of designers solve the same set of problems, and (3) compare the results to identify the success of each designer or design method. A proto-typical experiment using the problem of corridor selection is used to illustrate the approach, with solutions obtained by twelve students being compared to solutions obtained by discrete dynamic programming for a set of three problems. An important distinction is drawn between measuring the success of the solution vs the success of the problem solving procedure. An extension to evaluate the handling of separately defined objectives is suggested, and questions concerning the stability of a solution with respect to minor changes in the algorithms identified.     

On the two armed bandit with one probability known

Summary The dynamic programming approach to the solution of the two armed bandit problem with one probability known is discussed, for a general prior distribution for the unknown probability. Properties of the objective function and of the stopping boundaries are obtained. The problem of costly observations is discussed.     

Optimizing the credit term decisions in supply chain finance

We study a credit term determination problem in the context of a supplier-buyer supply chain. The supplier's credit term decision is simultaneously made with its production and inventory decisions, and most importantly, it is impacted by the buyer's order quantity. We present a new game-theoretic framework to model this problem, which captures the interaction between the supplier's credit term decision and the buyer's order decision in a multi-period setting. An exact method based on nonlinear programming is implemented to obtain the optimal solutions. We apply our methodologies on a real world case. The computational results show that our approach significantly outperforms the heuristics with fixed credit terms, and either a short or a long credit term can be sub-optimal for the supplier in profitability. Our work offers the first data-driven model and solution approach that assists purchasing and supply managers to make optimal dynamic credit term decision in conjunction with production, ordering and inventory decisions in a game-theoretic setting.     

Verification results for age-structured models of economic–epidemics dynamics

In this paper we propose a macro-dynamic age-structured set-up for the analysis of epidemics/economic dynamics in continuous time.The resulting optimal control problem is reformulated in an infinite dimensional Hilbert space framework where we perform the basic steps of dynamic programming approach.Our main result is a verification theorem which allows to guess the feedback form of optimal strategies. This will be a departure point to discuss the behavior of the models of the family we introduce and their policy implications.     

Stochastic Programming

This report presents an approach to stochastic programming. It treats mainly the difficulties arising in formulating the problem and the possibilities to derive a deterministic problem by which it can be replaced. In a sense the approach of this report unifies different viewpoints on stochastic programming problems as they have been published in the literature.