Multivariable Branching: A 0-1 Knapsack Problem Case Study

DOI10.1287/IJOC.2020.1052MaRDI QIDQ5084602zbMATH OpenOpenAlexFDO

Authors Yu Yang, Natashia Boland, Martin W. P. Savelsbergh

Publication date 28 June 2022

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.2020.1052

zbMATH Keywords

0-1 knapsack problembranch-and-boundbranching schememultivariable branching

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints
• Further results on an abstract model for branching and its application to mixed integer programming
• An abstract model for branching and its application to mixed integer programming
• Solving a class of multiplicative programs with 0-1 knapsack constraints
• Branch-and-bound solves random binary IPs in poly(n)-time

Cites work

• A Computational Study of Search Strategies for Mixed Integer Programming
• A machine learning-based approximation of strong branching
• An Automatic Method of Solving Discrete Programming Problems
• Benchmarking optimization software with performance profiles.
• Branch and Bound Methods for Mathematical Programming Systems
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• Branching rules revisited
• Cloud branching
• Column basis reduction and decomposable knapsack problems
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• DASH: dynamic approach for switching heuristics
• Experiments in mixed-integer linear programming
• Experiments in mixed-integer linear programming using pseudo-costs
• Hard Knapsack Problems
• scientific article; zbMATH DE number 7124428 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Non-standard approaches to integer programming
• On learning and branching: a survey
• Where are the hard knapsack problems?

Cited in

(10)

• Lower bound on size of branch-and-bound trees for solving lot-sizing problem
• Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• An abstract model for branch-and-cut
• The use of duality to determine the branching order of variables and to estimate the bounds in the solution of the knapsack problem
• A study of lattice reformulations for integer programming
• Compressing branch-and-bound trees
• An abstract model for branch and cut
• Compressing branch-and-bound trees
• Branching with a pre-specified finite list of k-sparse split sets for binary MIPs

Describes a project that uses

Uses Software

• SCIP

This page was built for publication: Multivariable Branching: A 0-1 Knapsack Problem Case Study

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