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

Computer Science

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration
Forlag	AAAI Press
Publikationsdato	2009
Status	Udgivet - 2009
Begivenhed	21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration - Pasadena, California, USA Varighed: 11 jul. 2009 → 17 jul. 2009

Konference

Konference	21st International Joint Conferences on Artificial Intelligence (IJCAI-09) Workshop on Configuration
Land/Område	USA
By	Pasadena, California
Periode	11/07/2009 → 17/07/2009

Emneord

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

Adgang til dokumentet

NBJT09Indsendt manuskript, 433 KB

Citationsformater

@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. i 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, USA, 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.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater