Backdoors to Combinatorial Optimization: Feasibility and Optimality

DOI10.1007/978-3-642-01929-6_6MaRDI QIDQ3630152zbMATH OpenOpenAlexFDO

Authors Bistra Dilkina, Yuri Malitsky, Ashish Sabharwal, Meinolf Sellmann, Carla P. Gomes

Publication date 3 June 2009

Published in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-01929-6_6

zbMATH Keywords

backdoor setssearchvariable selection

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Tradeoffs in the Complexity of Backdoor Detection
• Backdoors in the Context of Learning
• Backdoors to satisfaction
• A note on backbones in optimization and approximation

Cited in

(8)

• How important are branching decisions: fooling MIP solvers
• Learning pseudo-backdoors for mixed integer programs
• Backdoor branching
• Backdoors in the Context of Learning
• Branching on nonchimerical fractionalities
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Multi-task representation learning for mixed integer linear programming
• Machine learning augmented branch and bound for mixed integer linear programming

Describes a project that uses

Uses Software

• MIPLIB
• MIPLIB2003

This page was built for publication: Backdoors to Combinatorial Optimization: Feasibility and Optimality

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