A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems

DOI10.1016/0167-6377(84)90028-2zbMATH Open0549.90073OpenAlexW2073471848MaRDI QIDQ800229FDOQ800229

Authors: Michel Minoux, Celso C. Ribeiro 

Publication date: 1984

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90028-2

Recommendations

• A solution method for a knapsack problem and its variant
• scientific article; zbMATH DE number 3961370
• scientific article; zbMATH DE number 1302173
• The zero-one knapsack problem with equality constraint
• On equivalent knapsack problems

zbMATH Keywords

combinatorial optimizationknapsack problemsequivalent problem transformationconstrained shortest path problemsequality constrained

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Cites Work

• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Hard Knapsack Problems
• An algorithm for the solution of the 0-1 knapsack problem
• Technical Note—Solving Integer Programming Problems by Aggregating Constraints
• Transformation of integer programs to knapsack problems
• Polynomial-Time Aggregation of Integer Programming Problems
• A Convergent Duality Theory for Integer Programming
• Efficient group cuts for integer programs
• A Simple Algorithm for Integer Programs Using Group Constraints

Cited In (4)

• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• An homage to Joseph-Louis Lagrange and Pierre Huard
• A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
• A heuristic approach to hard constrained shortest path problems

This page was built for publication: A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems

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