Facets and algorithms for capacitated lot sizing

DOI10.1007/BF01589110zbMath0681.90060OpenAlexW2063682953MaRDI QIDQ1823857

Thomas L. Magnanti, Janny M. Y. Leung, Rita Vachani

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01589110

zbMATH Keywords

valid inequalitiesComputational resultspolyhedral structurecutting plane/branch and bounddynamic economic lot sizingmulti-item applicationssingle-item capacitated version

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Integer programming (90C10) Production models (90B30) Inventory, storage, reservoirs (90B05) Polytopes and polyhedra (52Bxx)

Related Items (35)

Coordination of production and distribution planning ⋮ A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers ⋮ A joint chance-constrained programming approach for the single-item capacitated lot-sizing problem with stochastic demand ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ Multi-product valid inequalities for the discrete lot-sizing and scheduling problem ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Partial objective inequalities for the multi-item capacitated lot-sizing problem ⋮ A cutting plane approach to capacitated lot-sizing with start-up costs ⋮ A risk-averse two-stage stochastic programming model for a joint multi-item capacitated line balancing and lot-sizing problem ⋮ Source sink flows with capacity installation in batches ⋮ A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs ⋮ Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups ⋮ A polyhedral study of lot-sizing with supplier selection ⋮ Classical cuts for mixed-integer programming and branch-and-cut ⋮ The multi-item capacitated lot-sizing problem with setup times and shortage costs ⋮ Improved algorithms for dynamic lot sizing problems with incremental discount ⋮ Improved exact algorithms to economic lot-sizing with piecewise linear production costs ⋮ Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution ⋮ The item dependent stockingcost constraint ⋮ A framework for modelling setup carryover in the capacitated lot sizing problem ⋮ MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs ⋮ Integrated inventory model for similar products under a two-echelon supply chain environment: an empirical study ⋮ Heuristics for theN-product,M-stage, economic lot sizing and scheduling problem with dynamic demand ⋮ An integrated model for inventory and production planning in a two-stage hybrid production system ⋮ An application of Lagrangean decomposition to the capacitated multi-item lot sizing problem ⋮ Efficient post-optimization analysis procedure for the dynamic lot-sizing problem ⋮ Grouping in decomposition method for multi-item capacitated lot-sizing problem with immediate lost sales and joint and item-dependent setup cost ⋮ Valid inequalities and facets of the capacitated plant location problem ⋮ Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds ⋮ Single item lot sizing problems ⋮ On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra ⋮ A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem ⋮ A technique for speeding up the solution of the Lagrangean dual ⋮ A new dynamic programming algorithm for the single item capacitated dynamic lot size model ⋮ Restrictive aggregation of items in multi-stage production systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Valid inequalities and separation for capacitated economic lot sizing
• Lot-size models with backlogging: Strong reformulations and cutting planes
• Production scheduling and sequencing for multi-stage production systems
• Worst case performance for lot sizing heuristics
• The ellipsoid method and its consequences in combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• A capacity constrained singlefacility dynamic lot-size model
• Valid inequalities and facets of the capacitated plant location problem
• On certain polytopes associated with graphs
• Edmonds polytopes and a hierarchy of combinatorial problems
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Fixed-cost transportation problems
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• Approximation Methods for the Uncapacitated Dynamic Lot Size Problem
• Uncapacitated lot-sizing: The convex hull of solutions
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Facets of the linear ordering polytope
• Solving matching problems with linear programming
• Valid Linear Inequalities for Fixed Charge Problems
• On the facial structure of scheduling polyhedra
• The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations
• Strong Formulations for Multi-Item Capacitated Lot Sizing
• Approximation Formulations for the Single-Product Capacitated Lot Size Problem
• Note—Performance Bounds for Lot Sizing Heuristics
• LP extreme points and cuts for the fixed-charge network design problem
• Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Deterministic Production Planning: Algorithms and Complexity
• Some facets of the simple plant location polytope
• Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems
• An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
• Odd Minimum Cut-Sets and b-Matchings
• Computational Complexity of the Capacitated Lot Size Problem
• A Lower Bounding Structure for Lot-Size Scheduling Problems
• Multi-Item Lot Size Scheduling by Heuristic Part I: With Fixed Resources
• A Heuristic Adjacent Extreme Point Algorithm for the Fixed Charge Problem
• Bounded Production and Inventory Models with Piecewise Concave Costs
• Set Partitioning: A survey
• Covering, Packing and Knapsack Problems
• On Linear Characterizations of Combinatorial Optimization Problems
• Properties of vertex packing and independence system polyhedra
• A Decomposition Algorithm for Arborescence Inventory Systems
• Deterministic Production Planning with Concave Costs and Capacity Constraints
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices
• A Deterministic Multi-Period Production Scheduling Model with Backlogging
• An approximate solution method for the fixed charge problem
• Extensions of the Planning Horizon Theorem in the Dynamic Lot Size Model
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
• A Branch-and-Bound Algorithm for Multi-Level Fixed-Charge Problems
• The fixed charge problem
• Technical Note—Exact Solution of the Fixed-Charge Transportation Problem
• An Efficient Algorithm for Multi-Item Scheduling
• Solving the Fixed Charge Problem by Ranking the Extreme Points

This page was built for publication: Facets and algorithms for capacitated lot sizing