Constraint programming techniques for analyzing component satisfaction rules in a product configurator
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Date
2023-12-12
Department
Major/Subject
Mathematics
Mcode
SCI3054
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
36
Series
Abstract
With online stores becoming more and more popular so has the need for product customization grown. The customization can be handled with product configuration models. A product model is a set of all possible parts that any one of the model’s configurations could include and a set of rules and relations between them. Furthermore, a part of the product often has its configuration model making the overall model multi-leveled. For example, a model of a car could have few possibilities for the motor and each of these possibilities would then have a configuration model of their own. The exponentially growing size of these models when extra details and structures are added means that if the model or some of its parts are human-generated mistakes can easily happen and finding them can be complicated. These mistakes in the model could be that a certain part can never be included in the final configuration due to physical dimensions or some other error in the model’s logic. The model could also similarly try to include multiple different parts to a single position, think of a car with two different motors. Or it could also be that the whole model is not configurable with some subset of its parameters. Besides the sheer size of the model what also makes finding the anomalies hard is that each part of the model is connected to its child parts via assignments that give further restrictions to the parameters. It could be that a configuration error occurs due to two or more parts, that are located many levels apart or in different branches of the configuration tree, not being compatible even though as individual products they would be configured just fine. In this thesis, I provide a method for analyzing component satisfaction rules in a simple product in Variantum Oy’s product onfigurator. I analyze the product structure using methods of constraint programming such as backtracking and constraint propagation. The analysis is done using Choco-solver which is an open-source java library for constraint programming that excels especially in integer and other discrete constraint problems. The provided algorithm for analyzing the simplified product model ended up working well enough that the bottleneck became loading the model from the server rather than analyzing it. Furthermore, I provide a proof that the product configuration model used by Variantum can be perfectly mapped to be feature models that are generally used in product configuration literature and vice versa proving that both models contain the same amount of information. And hence besides algorithm speed both are as good at modelling product structures.Verkkokauppojen tullessa yhä suositummiksi, myös tuotteiden kustomointitarve on kasvanut. Kustomointi voidaan hoitaa tuotekonfiguraatiomalleilla. Konfiguraatiomalli on kaikkien mahdollisten osien joukko, jotka mikä tahansa tuotteen kokoonpano voi sisältää, sekä joukko sääntöjä ja relaatioita niiden välillä. Tuotteen osilla on myös usein omat konfiguraatiomallinsa, mikä tekee kokonaismallista monitasoisen. Esimerkiksi auton mallissa voisi olla muutamia vaihtoehtoja moottorille ja jokaisella näistä vaihtoehdoista olisi oma alikonfiguraatiomallinsa. Mallien eksponentiaalisesti kasvava koko yksityiskohtia ja rakenteita lisättäessä tarkoittaa, että mikäli malli on ihmisen tekemä, se voi helposti sisältää virheitä. Ja mallin suuren koon vuoksi, ne voivat olla vaikeitä paikallistaa. Virheitä ovat esimerkiksi, että tiettyä osaa ei koskaan voida sisällyttää lopulliseen kokoonpanoon fyysisten mittojen tai muun mallin logiikan virheen vuoksi. Tai malli voi yrittää sisällyttää useita eri osia yhteen paikkaan, esimerkiksi kaksi moottoria autoon. Tai voi myös olla, että koko mallia ei voi konfiguroida jollakin sen parametrien osajoukolla. Mallin suuren koon lisäksi poikkeavuuksien löytämistä vaikeuttaa myös se, että mallin jokainen osa on liitetty alaosiinsa arvojen sijoituksilla, jotka antavat lisärajoituksia parametreille. Saattaa olla, että konfigurointivirhe johtuu kahdesta tai useammasta osasta, jotka sijaitsevat monta tasoa erillään, tai konfigurointipuun eri haaroissa, eivätkä ole yhteensopivia, vaikka yksittäisinä tuotteina ne konfiguroituisivat ongelmitta. Tässä opinnäytetyössä esitän menetelmän komponenttien tyytyväisyyssääntöjen analysointiin yksinkertaisessa tuotteessa Variantum Oy:n tuotekonfiguraattorissa. Analysoin tuotteen rakennetta rajoiteohjelmoinnin menetelmillä. Analyysi tehdään Choco-solverilla, joka on avoimen lähdekoodin Java-kirjasto rajoiteohjelmointiin. Se soveltuu erityisesti diskreettien rajoitehohjelmointiongelmien ratkaisuun. Tarjottu algoritmi yksinkertaistetun tuotemallin analysointiin päätyi toimimaan niin hyvin, että pullonkaulaksi muodostui mallin lataaminen palvelimelta analysoinnin sijaan. Lisäksi todistan, että Variantumin käyttämä tuotekonfiguraatiomalli voidaan kuvata täydellisesti kirjallisuudessa yleisesti käytetyiksi malleiksi ja päinvastoin. Eli molemmat mallit sisältävät saman informaation, ja siksi niitä käsittelevien algoritmien nopeudet poislukien molemmat ovat yhtä hyviä mallintamaan tuoterakenteita.Description
Supervisor
Oliveira, FabricioThesis advisor
Peltonen, HannuKeywords
configuration model, anomaly, constraint programming, product structure, choco-solver