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

DOI10.1016/0167-6377(84)90028-2zbMath0549.90073OpenAlexW2073471848MaRDI QIDQ800229

Michel Minoux, Celso Carneiro 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)

Related Items

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

Cites Work

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