Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm

DOI10.1080/23311835.2016.1162372zbMath1426.90254OpenAlexW2315144778MaRDI QIDQ4966750

Elias Munapo, Santosh Kumar

Publication date: 27 June 2019

Published in: Cogent Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/23311835.2016.1162372

zbMATH Keywords

computational complexitybranch and boundreformulationknapsack integer problem

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Uses Software

• SYMPHONY

Cites Work

• Partitioning procedures for solving mixed-variables programming problems
• A branch-and-cut algorithm for the equicut problem
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• An Automatic Method of Solving Discrete Programming Problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Branch and Bound Methods for Mathematical Programming Systems
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A tree-search algorithm for mixed integer programming problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm