Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation

DOI10.1016/J.IPL.2016.01.008MaRDI QIDQ5964827zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alberto Caprara, Fabio Furini, Enrico Malaguti, Emiliano Traversi

Publication date 1 March 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2016.01.008

zbMATH Keywords

combinatorial problemsDantzig-Wolfe reformulationmixed integer programstemporal knapsack problem

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Recommendations

• An iterative dynamic programming approach for the temporal knapsack problem
• Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
• The Temporal Knapsack Problem and Its Solution
• Consistency cuts for Dantzig-Wolfe reformulations
• A branch-and-price algorithm for the temporal bin packing problem

Cites work

• A constant-factor approximation algorithm for unsplittable flow on paths
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• Column Generation
• Decomposition and reformulation of integer linear programming problems. (Summary)
• Dual nested decomposition of staircase linear programs
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• Nested Decomposition and Multi-Stage Linear Programs
• Nested decomposition for dynamic models
• Partial convexification of general mips by Dantzig-Wolfe reformulation
• Reformulation and decomposition of integer programs
• Scheduling jobs with fixed start and end times

Cited in

(18)

• Approximating the 3-period incremental knapsack problem
• An iterative dynamic programming approach for the temporal knapsack problem
• Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• A branch-and-price algorithm for the temporal bin packing problem
• Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
• On approximating the incremental knapsack problem
• Multi-objective temporal bin packing problem: an application in cloud computing
• Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
• Partial convexification of general mips by Dantzig-Wolfe reformulation
• Consistency cuts for Dantzig-Wolfe reformulations
• The Temporal Knapsack Problem and Its Solution
• A combinatorial flow-based formulation for temporal bin packing problems
• Nested column generation for split pickup vehicle routing problem with time windows and time-dependent demand
• Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem
• Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
• Nested branch-and-price for multi-mode nanosatellite task scheduling with interior-point regularization and GPU acceleration
• Mathematical models based on decision hypergraphs for designing a storage cabinet

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964827)