Integer linear programming formulation of the material requirements planning problem

Lot sizing procedures for discrete and dynamic demand form a distinct class of inventory control problems, usually referred to asmaterial requirements planning. A general integer programming formulation is presented, covering an extensive range of problems: single-item, multi-item, and multi-level optimization; conditions on lot sizes and time phasing; conditions on storage and production capacities; and changes in production and storage costs per unit. The formulation serves as a uniform framework for presenting a problem and a starting point for developing and evaluating heuristic and tailor-made optimum-seeking techniques.     

Computation of material requirements for production planning

Efficient methods for the determination of unique part levels, the generation of the total requirement matrix and the computation of parts requirements in a manufacturing system are presented. The algorithms discussed here achieve substantial reduction in both core storage and execution times.     

Optimized material requirements planning for semiconductor manufacturing

This paper describes a custom operational research algorithm, which is run nightly by IBM to create a material requirements plan for its semiconductor fabrication facility in Vermont, USA. To model alternative manufacturing processes and part substitutions, this application interweaves linear programming and heuristic methods to reap the benefits of each decision technology. At each level of the bills of materials supply chain with complex decision choices to be made, parallel linear programmes are invoked and their results are fed into a material requirements planning (MRP) heuristic, which processes parts through multiple iterations. The results from processing one level of the bills of materials supply chain are exploded to create demand for the next level and the interweaving of the two decision technologies continues. The algorithm creates recommended manufacturing releases and work-in-process priorities. These outputs point out opportunities for improvement in order to satisfy all demands on time. The output can be interpreted with well-known MRP assumptions.     

A surrogate for linear programs with random requirements

An approach to linear programs with random requirements is suggested. The procedure involves choosing actions which minimize the expected value of a certain loss function. These actions are then taken as goals, and optimal values of the decision variables are found by solving a simple linear goal programming problem.     

Focusing material requirements planning (MRP) towards performance

This paper looks at the successes and disappointments of MRP. It studies numerous articles to determine what the key shortcomings of MRP are. Next, it investigates if these failures are correctable, and what the consequences of not correcting these deficiencies means. This article considers alternatives that have been discussed in the current literature. Last of all this article discusses whether the improvements these alternatives suggest are sufficient to make MRP worth salvaging, or whether MRP is a system that needs to be discarded in favor of systems such as JIT (Just-in-Time), Optimized Production Technology (OPT), Theory of Constraints (TOC), and Bottleneck Allocation Methodology (BAM).     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

Entropy in linear programs

This paper treats entropy constrained linear programs from modelling as well as computational aspects. The optimal solutions to linear programs with one additional entropy constraint are expressed in terms of Lagrange-multipliers. Conditions for uniqueness are given. Sensitivity and duality are studied. The Newton—Kantorovich method is used to obtain a locally convergent iterative procedure. Related problems based on maximum entropy or minimum information are discussed.     

Optimal selectors for stochastic linear programs

The “distribution problem” of stochastic linear programming consists in answering the following two questions: Is the optimal value of a given stochastic linear program—regarded as a function—measurable, and if so, what is its distribution? In the present note we make use of a general selection theorem to answer the first question positively. By this approach, an answer to the second question is obtained—at least theoretically—at the same time.     

Postoptimality for multistage stochastic linear programs

The contamination technique is presented as a flexible and relatively easily tractable tool to postoptimality analysis for scenario based multistage stochastic linear programs. It is promising especially in cases when the influence of additional or out-of-sample scenarios on the already solved problem is to be explored.Research supported in part by the Grant Agency of the Czech Republic under Grant No. 402/93/0631.     

Purification for separated continuous linear programs

This paper presents a purification algorithm for a class of infinite-dimensional linear programs called separated continuous linear programs (SCLP). This takes an initial feasible solution and produces an extreme point solution without a decrease in objective function value. The algorithm presented here for SCLP is also shown to be the best possible purification algorithm in a certain class.     

Improved smoothing-type methods for the solution of linear programs

Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem collection. Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001     

Parameterisation algorithms for the integer linear programs in binary variables

In this paper we consider the integer programmiing problem: minimize z(x) = c · x subject to Ax?b,x binary.Roodman appended the objective function z(x) to the body of the constraints and presented a modified version of the Balas additive algorithm by which each fathomed partial solution is attributed to the constraint which caused the fathoming. Exploiting this information, he conducted (a) ranging analysis, i.e. calculating bounds on the values of the parameters which leave the original optimal solution unchanged, and (b) parameter change analysis, i.e. determining new optimal solutions (if any) for revised values of the parameters outside the ranging bounds.We extend Roodman's results and construct parametric functions of the following form. Let Σ be any parameter of c or b or A, and replace Σ by Σ(λ) = Σ + λ. Then, holding every other parameter of the program fixed, and varying λ in the set of real numbers we construct the parametric function $\text{z}{}^1\text{(Σ(λ))}$ which matches non-overlapping intervals of λ with optimal solutions. This replaces by exact bounds in the linear programming sense, the bounds underestimated by Roodman's ranging analysis. It also determines optimal solutions for any values of λ, rather than for a revised set of values. Finally some results of computational experience are presented.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

An implication basis for linear forms

The main results of this paper are a generalization of the results of S. Fajtlowicz and J. Mycielski on convex linear forms. We show that if V_n is the variety generated by all possible algebras , where R denotes the real numbers and , for some , then any basis for the set of all identities satisfied by V_n is infinite. But on the other hand, the identities satisfied by V_n are a consequence of gL and μ_n, where μ_n is the n-ary medial law and the inference rule gL is an implication patterned after the classical rigidity lemma of algebraic geometry. We also prove that the identities satisfied by are a consequence of gL and μ_n iff {p₁, ... , p_n} is algebraically independent. We then prove analagous results for algebras of arbitrary type τ and in the final section of this paper, we show that analagous results hold for Abelian group hyperidentities. This paper is dedicated to Walter Taylor. Received July 16, 2005; accepted in final form January 12, 2006. The research of both authors was supported by an operating grant ODP0008215 from NSERC.     

Affine-scaling for linear programs with free variables

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.     

Multi-stage stochastic linear programs for portfolio optimization

The paper demonstrates how multi-period portfolio optimization problems can be efficiently solved as multi-stage stochastic linear programs. A scheme based on a blending of classical Benders decomposition techniques and a special technique, called importance sampling, is used to solve this general class of multi-stochastic linear programs. We discuss the case where stochastic parameters are dependent within a period as well as between periods. Initial computational results are presented.Research and reproduction of this report were partially supported by the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089, the Electric Power Research Institute Contract RP-8010-09, CSA-4O05335, and the Austrian Science Foundation, Fonds zur Förderung der wissenschaftlichen Forschung, Grant J0323-Phy. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do NOT necessarily reflect the views of the above sponsors. The comments of anonymous referees are gratefully acknowledged.     

Parallel interior-point solver for structured linear programs

 Issues of implementation of an object-oriented library for parallel interior-point methods are addressed. The solver can easily exploit any special structure of the underlying optimization problem. In particular, it allows a nested embedding of structures and by this means very complicated real-life optimization problems can be modelled. The efficiency of the solver is illustrated on several problems arising in the optimization of networks. The sequential implementation outperforms the state-of-the-art commercial optimization software. The parallel implementation achieves speed-ups of about 3.1-3.9 on 4-processors parallel systems and speed-ups of about 10-12 on 16-processors parallel systems. Received: December 4, 2000 / Accepted: January 2003 Published online: April 10, 2003 RID="⋆" ID="⋆" Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/M68169.     

Valid inequalities for mixed integer linear programs

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.