Solving binary cutting stock problems by column generation and branch- and-bound

DOI10.1007/BF01300970zbMath0801.90080OpenAlexW2005926129MaRDI QIDQ1326509

Ellis L. Johnson, Cynthia Barnhart, Pamela H. Vance, Nemhauser, George I.

Publication date: 18 May 1994

Published in: Computational Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

column generation branch-and-bound binary cutting stock problem

Mathematics Subject Classification ID

Integer programming (90C10) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Ranking lower bounds for the bin-packing problem, An introduction to stochastic bin packing-based server consolidation with conflicts, Bin packing and cutting stock problems: mathematical models and exact algorithms, An exact algorithm for IP column generation, An improved typology of cutting and packing problems, Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families, Determining the \(K\)-best solutions of knapsack problems, A branch-and-price algorithm for solving the cutting strips problem, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint, Compact integer linear programming formulations for the temporal bin packing problem with fire-ups, Single machine parallel-batch scheduling under time-of-use electricity prices: new formulations and optimisation approaches, A branch-and-price approach for operational aircraft maintenance routing, Theoretical treatment of target coverage in wireless sensor networks, Unnamed Item, A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching, Computational results with a primal-dual subproblem simplex method, A column generation approach to capacitated \(p\)-median problems, Bi-dynamic constraint aggregation and subproblem reduction, Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory, A new cross decomposition method for stochastic mixed-integer linear programming, A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function, Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation, The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP, A branch-and-price approach to \(p\)-median location problems, Lower bounds and algorithms for the 2-dimensional vector packing problem, A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes, Strategic capacity planning in supply chain design for a new market opportunity, Scenario-based approach for flexible resource loading under uncertainty, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Classification and literature review of integrated lot-sizing and cutting stock problems, A column generation approach for the maximal covering location problem, Solving bin packing problems using VRPSolver models, Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition, Dual Inequalities for Stabilized Column Generation Revisited, Integer programming approach to the printed circuit board grouping problem, The Fixed-Charge Shortest-Path Problem, Modified greedy heuristic for the one-dimensional cutting stock problem, Column-Generation in Integer Linear Programming, A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems, Cliques and clustering: A combinatorial approach, Properties of some ILP formulations of a class of partitioning problems, Solving robust bin-packing problems with a branch-and-price approach, Multi-commodity supply network planning in the forest supply chain, Locomotive assignment with heterogeneous consists at CN North America, One-dimensional relaxations and LP bounds for orthogonal packing, The asymmetric traveling salesman problem with replenishment arcs, The one-dimensional cutting stock problem with due dates, Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, LP models for bin packing and cutting stock problems, Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths, A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

Uses Software

MINTO

Cites Work