Unbounded knapsack problem: Dynamic programming revisited

DOI10.1016/S0377-2217(99)00265-9zbMath0961.90123DBLPjournals/eor/AndonovPR00OpenAlexW2087203776WikidataQ56050293 ScholiaQ56050293MaRDI QIDQ1569945

Vincent Poirriez, Sanjay V. Rajopadhye, Rumen Andonov

Publication date: 20 September 2000

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00265-9

zbMATH Keywords

integer programmingdynamic programmingperiodicitycombinatorial optimizationdominances

Mathematics Subject Classification ID

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

Related Items (31)

Multiperiod capacity expansion of a telecommunications connection with uncertain demand ⋮ A Theory of Auto-Scaling for Resource Reservation in Cloud Services ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ Fuzzy approach to multilevel knapsack problems ⋮ An exact algorithm for generating homogeneous T-shape cutting patterns ⋮ Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints ⋮ Integrated bin packing and lot-sizing problem considering the configuration-dependent bin packing process ⋮ Determining the \(K\)-best solutions of knapsack problems ⋮ Simplest optimal cutting patterns for equal rectangles ⋮ Lower bounds on circuit depth of the quantum approximate optimization algorithm ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Tight bounds for periodicity theorems on the unbounded knapsack problem ⋮ The Unbounded Knapsack Problem ⋮ Piece selection algorithms for layered video streaming in P2P networks ⋮ Average performance of greedy heuristics for the integer knapsack problem. ⋮ Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0-1 knapsack problems ⋮ A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem ⋮ An empirical analysis of exact algorithms for the unbounded knapsack problem ⋮ Bridging game theory and the knapsack problem: a theoretical formulation ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ On the exact separation of mixed integer knapsack cuts ⋮ A cutting stock problem and its solution in the manufacturing industry of large electric generators ⋮ Dynamic programming algorithms for the optimal cutting of equal rectangles ⋮ Dynamic programming algorithms for generating optimal strip layouts ⋮ Using modifications to Grover's search algorithm for quantum global optimization ⋮ A hybrid algorithm for the unbounded knapsack problem ⋮ Unbounded knapsack problem: Dynamic programming revisited ⋮ Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors ⋮ Generating optimal two-section cutting patterns for rectangular blanks ⋮ Approximation schemes for multiperiod binary knapsack problems ⋮ A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

Cites Work

• An LP-based approach to a two-stage cutting stock problem
• A note on dominance relation in unbounded knapsack problems
• Reducing the number of variables in integer and linear programming problems
• On dominated terms in the general knapsack problem
• Unbounded knapsack problem: Dynamic programming revisited
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The Multiple-Choice Knapsack Problem
• A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• The Theory and Computation of Knapsack Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Unbounded knapsack problem: Dynamic programming revisited