Crowdsourcing Backdoor Identification for Combinatorial Optimization

We will show how human computation insights can be key to identifying so-called backdoor variables in combinatorial optimization problems. Backdoor variables can be used to obtain dramatic speedups in combinatorial search. Our approach leverages the complementary strength of human input, based on a visual identification of problem structure, crowdsourcing, and the power of combinatorial solvers to exploit complex constraints. We describe our work in the context of the domain of materials discovery. The motivation for considering the materials discovery domain comes from the fact that new materials can provide solutions for key challenges in sustainability, e. g. , in energy, new catalysts for more efficient fuel cell technology.

Authors

• Ronan Le Bras
• Richard Bernstein
• Carla P. Gomes Department of Computer Science, Cornell University, USA
• Bart Selman
• R. Bruce van Dover Cornell University

Keywords

No keywords are indexed for this paper.