An iterative dynamic programming approach for the temporal knapsack problem

DOI10.1016/j.ejor.2020.12.036zbMath1487.90633OpenAlexW3022737676MaRDI QIDQ2030285

Yanyan Li

Publication date: 7 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.12.036

zbMATH Keywords

Lagrangian relaxationexact algorithmsuccessive sublimation dynamic programming methodtemporal knapsack

Mathematics Subject Classification ID

Mixed integer programming (90C11) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (5)

Consistency Cuts for Dantzig-Wolfe Reformulations ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Exact and heuristic methods for a workload allocation problem with chain precedence constraints ⋮ Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups

Cites Work

• Unnamed Item
• Scheduling jobs with fixed start and end times
• A dynamic programming method for single machine scheduling
• The volume algorithm: Producing primal solutions with a subgradient method
• An exact algorithm for single-machine scheduling without machine idle time
• Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
• An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• State-space relaxation procedures for the computation of bounds to routing problems
• The Temporal Knapsack Problem and Its Solution
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation

This page was built for publication: An iterative dynamic programming approach for the temporal knapsack problem