Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration

Andreas Hau Nørgaard; Morten Riiskjær Boysen; Rune Møller Jensen; Peter Tiedemann

Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration

Andreas Hau Nørgaard, Morten Riiskjær Boysen, Rune Møller Jensen, Peter Tiedemann

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

This paper demonstrates how to lower the average response time of search-based interactive configurators using over and under approximations of the configuration problem represented by binary decision diagrams (BDDs) on problems where fast configurators using monolithic BDDs are intractable. The paper introduces several ways to build the approximations and our experimental evaluation on industrial data shows that a search driven extension of the approximations substantially outperforms both purely search-based and purely BDDbased interactive configurators.

Original language	English
Title of host publication	Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration
Publisher	AAAI Press
Publication date	2009
Publication status	Published - 2009
Event	21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration - Pasadena, California, United States Duration: 11 Jul 2009 → 17 Jul 2009

Conference

Conference	21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration
Country/Territory	United States
City	Pasadena, California
Period	11/07/2009 → 17/07/2009

Keywords

Interactive Configurators
Binary Decision Diagrams
Search-Based Configuration
Response Time Optimization
Industrial Data Evaluation

Access to Document

NBJT09Submitted manuscript, 433 KB

Cite this

@inproceedings{57c779e0ab6911deb2ea000ea68e967b,

title = "Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration",

abstract = "This paper demonstrates how to lower the average response time of search-based interactive configurators using over and under approximations of the configuration problem represented by binary decision diagrams (BDDs) on problems where fast configurators using monolithic BDDs are intractable. The paper introduces several ways to build the approximations and our experimental evaluation on industrial data shows that a search driven extension of the approximations substantially outperforms both purely search-based and purely BDDbased interactive configurators.",

keywords = "Interactive Configurators, Binary Decision Diagrams, Search-Based Configuration, Response Time Optimization, Industrial Data Evaluation, Interactive Configurators, Binary Decision Diagrams, Search-Based Configuration, Response Time Optimization, Industrial Data Evaluation",

author = "N{\o}rgaard, {Andreas Hau} and Boysen, {Morten Riiskj{\ae}r} and Jensen, {Rune M{\o}ller} and Peter Tiedemann",

year = "2009",

language = "English",

booktitle = "Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration",

publisher = "AAAI Press",

address = "United States",

note = "21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration ; Conference date: 11-07-2009 Through 17-07-2009",

}

Nørgaard, AH, Boysen, MR, Jensen, RM & Tiedemann, P 2009, Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration. in Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration. AAAI Press, 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration, Pasadena, California, United States, 11/07/2009.

Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration. / Nørgaard, Andreas Hau; Boysen, Morten Riiskjær; Jensen, Rune Møller et al.
Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration. AAAI Press, 2009.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration

AU - Nørgaard, Andreas Hau

AU - Boysen, Morten Riiskjær

AU - Jensen, Rune Møller

AU - Tiedemann, Peter

PY - 2009

Y1 - 2009

N2 - This paper demonstrates how to lower the average response time of search-based interactive configurators using over and under approximations of the configuration problem represented by binary decision diagrams (BDDs) on problems where fast configurators using monolithic BDDs are intractable. The paper introduces several ways to build the approximations and our experimental evaluation on industrial data shows that a search driven extension of the approximations substantially outperforms both purely search-based and purely BDDbased interactive configurators.

AB - This paper demonstrates how to lower the average response time of search-based interactive configurators using over and under approximations of the configuration problem represented by binary decision diagrams (BDDs) on problems where fast configurators using monolithic BDDs are intractable. The paper introduces several ways to build the approximations and our experimental evaluation on industrial data shows that a search driven extension of the approximations substantially outperforms both purely search-based and purely BDDbased interactive configurators.

KW - Interactive Configurators

KW - Binary Decision Diagrams

KW - Search-Based Configuration

KW - Response Time Optimization

KW - Industrial Data Evaluation

KW - Interactive Configurators

KW - Binary Decision Diagrams

KW - Search-Based Configuration

KW - Response Time Optimization

KW - Industrial Data Evaluation

M3 - Article in proceedings

BT - Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration

PB - AAAI Press

T2 - 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration

Y2 - 11 July 2009 through 17 July 2009

ER -

Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this