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

DOI10.1016/J.EJOR.2021.11.050zbMATH Open1506.90175OpenAlexW3216362854MaRDI QIDQ2140266FDOQ2140266

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

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

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

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)

Cites Work

• Gene selection for cancer classification using support vector machines
• A Computational Study of Search Strategies for Mixed Integer Programming
• Branching rules revisited
• Optimization problems for machine learning: a survey
• Mixed Integer Programming: Analyzing 12 Years of Progress
• Backdoor Branching
• Title not available (Why is that?)
• Experiments in mixed-integer linear programming
• Branch and Bound Methods for Mathematical Programming Systems
• Machine learning for combinatorial optimization: a methodological tour d'horizon
• Experiments in mixed-integer linear programming using pseudo-costs
• On learning and branching: a survey
• A Machine Learning-Based Approximation of Strong Branching
• The voice of optimization
• Multivariable Branching: A 0-1 Knapsack Problem Case Study

Cited In (3)

• High generalization performance structured self-attention model for knapsack problem
• Last‐mile delivery with drone and lockers
• \textsc{Ner4Opt}: named entity recognition for optimization modelling from natural language

Uses Software

• CPLEX
• XGBoost

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)