Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems

DOI10.1016/J.EJOR.2021.11.050MaRDI QIDQ2140266zbMATH OpenOpenAlexFDO

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

Publication date 20 May 2022

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2021.11.050

zbMATH Keywords

machine learningbranch and boundbinary optimization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Recommendations

• Multivariable Branching: A 0-1 Knapsack Problem Case Study
• A polyhedral study on 0-1 knapsack problems with set packing constraints
• Packing-based approximation algorithm for the k-set cover problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Alternating control tree search for knapsack/covering problems
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Improved dynamic programming and approximation results for the knapsack problem with setups
• Reinforcement learning for the knapsack problem
• A set-covering-based heuristic approach for bin-packing problems
• Publication:4204000

Cites work

• scientific article; zbMATH DE number 7124428 (Why is no real title available?)
• A Computational Study of Search Strategies for Mixed Integer Programming
• A machine learning-based approximation of strong branching
• Backdoor branching
• Branch and Bound Methods for Mathematical Programming Systems
• Branching rules revisited
• Experiments in mixed-integer linear programming
• Experiments in mixed-integer linear programming using pseudo-costs
• Gene selection for cancer classification using support vector machines
• Machine learning for combinatorial optimization: a methodological tour d'horizon
• Mixed integer programming: analyzing 12 years of progress
• Multivariable Branching: A 0-1 Knapsack Problem Case Study
• On learning and branching: a survey
• Optimization problems for machine learning: a survey
• The voice of optimization

Cited in

(10)

• A machine learning-based approximation of strong branching
• A theoretical and computational analysis of full strong-branching
• \textsc{Ner4Opt}: named entity recognition for optimization modelling from natural language
• On learning and branching: a survey
• Last fifty years of integer linear programming: a focus on recent practical advances
• A machine learning approach to rank pricing problems in branch-and-price
• High generalization performance structured self-attention model for knapsack problem
• Last‐mile delivery with drone and lockers
• Learning for Spatial Branching: An Algorithm Selection Approach
• \textsc{Ner4Opt}: named entity recognition for optimization modelling from natural language

Describes a project that uses

Uses Software

• XGBoost
• CPLEX

This page was built for publication: Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems

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