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

DOI10.1016/0167-6377(84)90028-2MaRDI QIDQ800229zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

combinatorial optimizationknapsack problemsequivalent problem transformationconstrained shortest path problemsequality constrained

Mathematics Subject Classification ID

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

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

Cites work

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

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)