Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

乳制品安全监管中的多阶段进化博弈分析

乳制品安全风险存在于生产与组织的多个阶段。在各个阶段中,政府监管部门虽统一监管,但由于采取的监管策略不同,使其与厂商之间的博弈情景存在差异,这将影响风险控制的成果。为探索多阶段监管的有效途径,找寻降低监管风险的方法,本文分析了乳制品安全监管中的多阶段进化博弈。首先阐述多阶段厂商监管的相关组织关系,构建进化博弈模型;其次基于模型进行进化博弈分析,分别得出了不同监管情景下的演化稳定策略,识别了多阶段策略选择的稳定条件;最后归纳了进化博弈分析结果,通过模拟仿真以及案例分析加以验证。     

Restart procedures for the conjugate gradient method

A compact and flexible updating procedure using matrix augmentation is developed. It is shown that the representation of the updated inverse does not grow monotonically in size, and may actually decrease during certain simplex iterations. Angular structures, such as GUB, are handled naturally within the partitioning framework, and require no modifications of the simplex method.     

Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming

We discuss methods for the solution of a multi-stage stochastic programming formulation for the resource-constrained scheduling of clinical trials in the pharmaceutical research and development pipeline. First, we present a number of theoretical properties to reduce the size and improve the tightness of the formulation, focusing primarily on non-anticipativity constraints. Second, we develop a novel branch and cut algorithm where necessary non-anticipativity constraints that are unlikely to be active are removed from the initial formulation and only added if they are violated within the search tree. We improve the performance of our algorithm by combining different node selection strategies and exploring different approaches to constraint violation checking.     

Basis properties and algorithmic specializations for gub transformed networks

Applying standard transformations of generalized upper bounding (GUB) theory to a pure or generalized network basis is shown to yield a reduced working basis that is itself a basis for a reduced network. As a result, the working basis can be represented via specialized data structures for networks. The resultant GUB based specializations to the network simplex algorithm are described.     

Time Consistent Dynamic Risk Measures

We introduce the time-consistency concept that is inspired by the so-called “principle of optimality” of dynamic programming and demonstrate – via an example – that the conditional value-at-risk (CVaR) need not be time-consistent in a multi-stage case. Then, we give the formulation of the target-percentile risk measure which is time-consistent and hence more suitable in the multi-stage investment context. Finally, we also generalize the value-at-risk and CVaR to multi-stage risk measures based on the theory and structure of the target-percentile risk measure.     

A multi-stage stochastic programming approach in master production scheduling

Master Production Schedules (MPS) are widely used in industry, especially within Enterprise Resource Planning (ERP) software. The classical approach for generating MPS assumes infinite capacity, fixed processing times, and a single scenario for demand forecasts. In this paper, we question these assumptions and consider a problem with finite capacity, controllable processing times, and several demand scenarios instead of just one. We use a multi-stage stochastic programming approach in order to come up with the maximum expected profit given the demand scenarios. Controllable processing times enlarge the solution space so that the limited capacity of production resources are utilized more effectively. We propose an effective formulation that enables an extensive computational study. Our computational results clearly indicate that instead of relying on relatively simple heuristic methods, multi-stage stochastic programming can be used effectively to solve MPS problems, and that controllability increases the performance of multi-stage solutions.     

A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms

In this paper, we develop a multi-objective model to optimally control the lead time of a multi-stage assembly system, using genetic algorithms. The multi-stage assembly system is modelled as an open queueing network. It is assumed that the product order arrives according to a Poisson process. In each service station, there is either one or infinite number of servers (machines) with exponentially distributed processing time, in which the service rate (capacity) is controllable. The optimal service control is decided at the beginning of the time horizon. The transport times between the service stations are independent random variables with generalized Erlang distributions. The problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. The objective functions are the total operating costs of the system per period (to be minimized), the average lead time (min), the variance of the lead time (min) and the probability that the manufacturing lead time does not exceed a certain threshold (max). Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed genetic algorithm approach.     

R&D pipeline management: Task interdependencies and risk management

Maintaining a rich research and development (R&D) pipeline is the key to remaining competitive in many industrial sectors. Due to its nature, R&D activities are subject to multiple sources of uncertainty, the modeling of which is compounded by the ability of the decision maker to alter the underlying process. In this paper, we present a multi-stage stochastic programming framework for R&D pipeline management, which demonstrates how essential considerations can be modeled in an efficient manner including: (i) the selection and scheduling of R&D tasks with general precedence constraints under pass/fail uncertainty, and (ii) resource planning decisions (expansion/contraction and outsourcing) for multiple resource types. Furthermore, we study interdependencies between tasks in terms of probability of success, resource usage and market impact. Finally, we explore risk management approaches, including novel formulations for value at risk and conditional value at risk.     

Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method

The nested L-shaped method is used to solve two- and multi-stage linear stochastic programs with recourse, which can have integer variables on the first stage. In this paper we present and evaluate a cut consolidation technique and a dynamic sequencing protocol to accelerate the solution process. Furthermore, we present a parallelized implementation of the algorithm, which is developed within the COIN-OR framework. We show on a test set of 51 two-stage and 42 multi-stage problems, that both of the developed techniques lead to significant speed ups in computation time.     

A Partitioned Inverse in Linear Programming

This note deals with linear programs in which a subset of the constraints have a special structure. This structure allows linear equations involving these constraints only to be solved particularly easily, e.g. GUB rows. A method is described for restricting the gaussian elimination in LU decomposition to the non-special rows.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

A column generation approach to the discrete barycenter problem

The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through linear programming, the underlying linear program can be extremely large. For worst-case input, a best known linear programming formulation is exponential in the number of variables, but has a low number of constraints, making it an interesting candidate for column generation.In this paper, we devise and study two column generation strategies: a natural one based on a simplified computation of reduced costs, and one through a Dantzig–Wolfe decomposition. For the latter, we produce efficiently solvable subproblems, namely, a pricing problem in the form of a classical transportation problem. The two strategies begin with an efficient computation of an initial feasible solution. While the structure of the constraints leads to the computation of the reduced costs of all remaining variables for setup, both approaches may outperform a computation using the full program in speed, and dramatically so in memory requirement. In our computational experiments, we exhibit that, depending on the input, either strategy can become a best choice.     

Layering strategies for creating exploitable structure in linear and integer programs

The strategy of subdividing optimization problems into layers by splitting variables into multiple copies has proved useful as a method for inducing exploitable structure in a variety of applications, particularly those involving embedded pure and generalized networks. A framework is proposed in this paper which leads to new relaxation and restriction methods for linear and integer programming based on our extension of this strategy. This framework underscores the use of constructions that lead to stronger relaxations and more flexible strategies than previous applications. Our results establish the equivalence of all layered Lagrangeans formed by parameterizing the equal value requirement of copied variables for different choices of the principal layers. It is further shown that these Lagrangeans dominate traditional Lagrangeans based on incorporating non-principal layers into the objective function. In addition a means for exploiting the layered Lagrangeans is provided by generating subgradients based on a simple averaging calculation. Finally, we show how this new layering strategy can be augmented by an integrated relaxation/restriction procedure, and indicate variations that can be employed to particular advantage in a parallel processing environment. Preliminary computational results on fifteen real world zero-one personnel assignment problems, comparing two layering approaches with five procedures previously found best for those problems, are encouraging. One of the layering strategies tested dominated all non-layering procedures in terms of both quality and solution time.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222 with the Center for Business Decision Analysis and by the US Department of Agriculture Contract 51-3142-4020 with Management Science Software Systems.     

Bounding multi-stage stochastic programs from above

The purpose of this paper is to present general approaches for bounding some multi-stage stochastic programs from above. The results are based on restricting the solution set, such that the remaining multi-stage stochastic program is easy to solve. An example where the methods can be applied is presented.Supported in part by NATO Collaborative Research Grant No. 0785/87.     

多约束的多阶段积极投资组合模型及实证研究

构建投资组合时需要衡量其风险, 除了考虑组合本身的风险暴露, 还需考虑其相对基准组合的风险暴露. 再者, 确定组合权重时需要根据市场的规则加入合适的约束. 基于此, 为了较为完整地考虑现实投资组合面临的风险及交易约束, 将绝对风险(CVaR)和相对风险(跟踪误差)作为风险约束, 将交易成本、卖空限制和多元权值作为交易限制约束, 构建一个新的多阶段投资组合模型, 并利用动态规划和非线性优化方法进行求解. 最后, 利用上证50成分股中41只股票构建投资组合进行实证研究. 实证结果表明构建的多阶段投资组合模型能持续战胜基准组合且优于单阶段投资组合, 同时也表明模型考虑多元权值约束具有现实意义.     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

A mixed R&D projects and securities portfolio selection model

The business environment is full of uncertainty. Allocating the wealth among various asset classes may lower the risk of overall portfolio and increase the potential for more benefit over the long term. In this paper, we propose a mixed single-stage R&D projects and multi-stage securities portfolio selection model. Specifically, we present a bi-objective mixed-integer stochastic programming model. Moreover, we use semi-absolute deviation risk functions to measure the risk of mixed asset portfolio. Based on the idea of moments approximation method via linear programming, we propose a scenario generation approach for the mixed single-stage R&D projects and multi-stage securities portfolio selection problem. The bi-objective mixed-integer stochastic programming problem can be solved by transforming it into a single objective mixed-integer stochastic programming problem. A numerical example is given to illustrate the behavior of the proposed mixed single stage R&D projects and multi-stage securities portfolio selection model.     

Using mathematical programming to solve Factored Markov Decision Processes with Imprecise Probabilities

This paper investigates Factored Markov Decision Processes with Imprecise Probabilities (MDPIPs); that is, Factored Markov Decision Processes (MDPs) where transition probabilities are imprecisely specified. We derive efficient approximate solutions for Factored MDPIPs based on mathematical programming. To do this, we extend previous linear programming approaches for linear approximations in Factored MDPs, resulting in a multilinear formulation for robust “maximin” linear approximations in Factored MDPIPs. By exploiting the factored structure in MDPIPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches, in exchange for relatively low approximation errors, on a difficult class of benchmark problems with millions of states.