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.     

Convex/stochastic programming and multilocation inventory problems

This paper examines a convex programming problem that arises in several contexts. In particular, the formulation was motivated by a generalization of the stochastic multilocation problem of inventory theory. The formulation also subsumes some “active” models of stochastic programming. A qualititative analysis of the problem is presented and it is shown that optimal policies have a certain geometric form. Properties of the optimal policy and of the optimal value function are described.     

Prediction with zero-one loss structure

This paper poses a prediction problem in which a linear model is assumed. With a “zero-one” loss structure as the loss from incorrect prediction, it is suggested that least squares may not be appropriate for estimating the parameters of the model. An alternate criterion is proposed and integer programming is used in order to find the estimates, given the proposed criterion.     

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     

Programming with linear fractional functionals

Charnes and Cooper [1] showed that a linear programming problem with a linear fractional objective function could be solved by solving at most two ordinary linear programming problems. In addition, they showed that where it is known a priori that the denominator of the objective function has a unique sign in the feasible region, only one problem need be solved. In the present note it is shown that if a finite solution to the problem exists, only one linear programming problem must be solved. This is because the denominator cannot have two different signs in the feasible region, except in ways which are not of practical importance.     

A generalized recursive algorithm for a class of non-stationary regeneration (scheduling) problems

Recent efforts in the field of dynamic programming have explored the feasibility of solving certain classes of integer programming problems by recursive algorithms. Special recursive algorithms have been shown to be particularly effective for problems possessing a 0–1 attribute matrix displaying the “nesting property” studied by, Ignall and Veinott in inventory theory and by Glover in network flows. This paper extends the class of problem structures that has been shown amenable to recursive exploitation by providing an efficient dynamic programming approach for a general transportation scheduling problem. In particular, we provide alternative formulations lor the scheduling problem and show how the most general of these formulations can be readily solved vis a vis recursive techniques.     

An exact ceiling point algorithm for general integer linear programming

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1-ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP-relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1-ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.     

An explicit general solution in linear fractional programming

A complete analysis and explicit solution is presented for the problem of linear fractional programming with interval programming constraints whose matrix is of full row rank. The analysis proceeds by simple transformation to canonical form, exploitation of the Farkas-Minkowki lemma and the duality relationships which emerge from the Charnes-Cooper linear programming equivalent for general linear fractional programming. The formulations as well as the proofs and the transformations provided by our general linear fractional programming theory are here employed to provide a substantial simplification for this class of cases. The augmentation developing the explicit solution is presented, for clarity, in an algorithmic format.     

An analysis of degeneracy

Degeneracy in linear programming models has been analyzed for its impacts on algorithmic properties. A complementary analysis here is on what the solutions mean. The framework presented is couched in marginal sensitivity analysis, introducing concepts of “compatible bases” and “transition graphs”.     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

The machine sequencing problem – review and extensions

The deterministic sequencing problem is reviewed from the points of view of variety, models, context, methodology, and current state of the art. The relationship between the theory of sequencing and other areas of control is illustrated with the relationship of sequencing to inventory. The “cyclical EMQ (Economical Manufacturing Quantities)” problem is discussed and new formulations are presented which promise a computationally feasible resolution of this outstanding problem.     

一类多目标模糊系数线性规划问题

讨论了一类所有系数均为模糊数的多目标线性规划问题 .通过对模糊数的比较 ,将模糊多目标线性规划模型转化为清晰的多目标模型 ,并应用一种基于线性隶属函数的模糊规划算法求其协调解 .最后给出了一个数值例子 .     

A note on duality in homogeneous fractional programming

For a linear fractional programming problem, Sharma and Swarup have constructed a dual problem, also a linear fractional program, in which the objective functions of both primal and dual problems are the same. Craven and Mond have extended this result to a nonlinear fractional programming problem with linear constraints, and a dual problem for which the objective function is the same as that of the primal. This theorem is now further extended from linear to differentiable convex constraints.     

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.     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Computing bounds for the optimal value in linear programming

Consider a standard linear programming problem and suppose that there are bounds available for the decision variables such that those bounds are not violated at an optimal solution of the problem (but they may be violated at some other feasible solutions of the problem). Thus, these bounds may not appear explicitly in the problem, but rather they may have been derived from some prior knowledge about an optimal solution or from the explicit constraints of the problem. In this paper, the bounds on variables are used to compute bounds on the optimal value when the problem is being solved by the simplex method. The latter bounds may then be used as a termination criteria for the simples iterations for the purpose of finding a “sufficiently good” near optimal solution. The bounds proposed are such that the computational effort in evaluating them is insignificant compared to that involved in the simplex iterations. A numerical example is given to demonstrate their performance.     

A squared-variable transformation approach to nonlinear programming optimality conditions

We show that the well-known necessary and sufficient conditions for a relative maximum of a nonlinear differentiable objective function with nonnegative variables constrained by nonlinear differentiable inequalities may be derived using the classical theory of equality constrained optimization problems with unrestricted variables. To do this we transform the original inequality-constrained problem to an equivalent equality-constrained problem by means of a well-known squared-variable transformation. Our major result is to show that second order conditions must be used to obtain the Kuhn-Tucker conditions by this approach. Our nonlinear programming results are motivated by the development of some well-known linear programming results by this approach.     

Concave minimization over a convex polyhedron

A general algorithm is developed for minimizing a well defined concave function over a convex polyhedron. The algorithm is basically a branch and bound technique which utilizes a special cutting plane procedure to' identify the global minimum extreme point of the convex polyhedron. The indicated cutting plane method is based on Glover's general theory for constructing legitimate cuts to identify certain points in a given convex polyhedron. It is shown that the crux of the algorithm is the development of a linear undrestimator for the constrained concave objective function. Applications of the algorithm to the fixed-charge problem, the separable concave programming problem, the quadratic problem, and the 0-1 mixed integer problem are discussed. Computer results for the fixed-charge problem are also presented.     

An examination of the effects of the criterion functional on optimal fire-support policies

This paper examines the dependence of the structure of optimal time-sequential fire-support policies on the quantification of military objectives by considering four specific problems, each corresponding to a different quantification of objectives (i.e. criterion functional). We consider the optimal time-sequential allocation of supporting fires during the “approach to contact” of friendly infantry against enemy defensive positions. The combat dynamics are modelled by deterministic Lanchester-type equations of warfare, and the optimal fire-support policy for each one-sided combat optimization problem is developed via optimal control theory. The problems are all nonconvex, and local optima are a particular difficulty in one of them. For the same combat dynamics, the splitting of supporting fires between two enemy forces in any optimal policy (i.e. the optimality of singular subarcs) is shown to depend only on whether the terminal payoff reflects the objective of attaining an “overall” military advantage or a “local” one. Additionally, switching times for changes in the ranking of target priorities are shown to be different (sometimes significantly) when the decision criterion is the difference and the ratio of the military worths (computed according to linear utilities) of total infantry survivors and also the difference and the ratio of the military worths (computed according to linear utilities) of total infantry survivors and also the difference and the ratio of the military worths of the combatants' total infantry losses. Thus, the optimal fire-support policy for this attack scenario is shown to be significantly influenced by the quantification of military objectives.     

Quadratic as parametric linear programming

This paper describes an approximate solution procedure for quadratic programming problems using parametric linear programming. Limited computational experience suggests that the approximation can be expected to be “good”.