Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Machine Learning for Constraint Programming
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

It is well established that designing good heuristics for solving Constraint Programming models requires years of domain experience and a huge amount of trial and error. In this thesis project, we conduct an empirical study of whether Machine Learning and Deep Learning techniques have the potential to help the design of constraint solving heuristics.Specifically, this thesis project examines the potential of Machine Learning and Deep Learning models for the regression task of predicting the makespan and solving time of a Job-Shop Scheduling Problem without actually solving the given Job-Shop Scheduling Problem instance. Several Machine Learning models are tested with manually designed features as input. Different Deep Learning architectures are explored with either just the Job-Shop Scheduling Problem instance as input or with an additional input of the previously designed features.××Results of the experiments justify the potential of several proposed models in predicting the makespan and solving time. For predicting the makespan (unit: machine time unit), the best Random Forest regression model achieves a Mean Squared Error of 0.78 on the test set. The best Deep Learning model achieves a Mean Squared Error of 0.74 on the test set. For predicting the solving time (unit: milliseconds) of a Job-Shop Scheduling Problem, the best Random Forest regression model achieves a Mean Squared Error of 2.12 107 on the test set. The best Deep Learning model achieves a Mean Squared Error of 5.19 107 on the test set.Discussions of the reason behind the difference of different Machine Learning and Deep Learning models are provided and future directions are proposed.

Abstract [sv]

Det är väl etablerat att det kräver många års erfarenhet av domänexpertis och mycket experimentell felsökning för att utforma en bra sökheuristik för villkorsprogrammeringsmodeller. I denna avhandling beskriver vi genomförandet av en empirisk studie med syftet att utreda potentialen av maskininlärningstekniker för att underlätta framtagandet av villkorsprogrammeringslösare.Mer specifikt undersöker vi maskininlärningsmodellers regressionsförmåga att förutse makespanöch lösningstid för "Job-Shop Scheduling Problem"utan att för den delen lösa den givna "Job-Shop Scheduling Problem"instansen. Flertalet maskininlärningsmodeller testas med manuellt framtagna särdrag som indata. Olika djupmaskininlärningsarkitekturer utforskas med antingen bara "Job-Shop Scheduling Problem-instanser som indata eller med ytterliggare indata i form av de manuellt framtagna särdragen.××Experimentresultaten motiverar användandet av flertalet av de föreslagna maskininlärningsmodellerna för att förutse makespanöch lösningstid. För förutsägandet av makespan"(enhet: maskintidsenhet) uppnår den bästa Random Forestregressionsmodellen ett medelkvadratfel på 0,78 på testdatamängden. Den bästa djupmaskininlärningsmodellen uppnår ett medelkvadratfel på 0,74 på testdatamängden. För förutsägandet av lösningstiden (enhet: millisekund) av "Job-Shop Scheduling Problem"uppnår den bästa Random Forestregressionsmodellen ett medelkvadratfel på 2.12 107 på testdatamängden. Den bästa djupmaskininlärningsmodellen uppnår ett medelkvadratfel på 5.19 107 på testdatamängden.Skillnadsorsakerna rörande de olika maskininlärningsmodellernas prestanda diskuteras i avhandlingen samt framtida forskningsinriktningar.

Place, publisher, year, edition, pages
2019. , p. 60
Series
TRITA-EECS-EX ; 2019:299
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-254660OAI: oai:DiVA.org:kth-254660DiVA, id: diva2:1334570
Supervisors
Examiners
Available from: 2019-07-03 Created: 2019-07-03 Last updated: 2019-07-03Bibliographically approved

Open Access in DiVA

fulltext(1783 kB)83 downloads
File information
File name FULLTEXT01.pdfFile size 1783 kBChecksum SHA-512
409d5cacf19f7f2e7f45895465bd514d1b0a8a39991b670ee5ea58ff753029bc7bfe4c4321938c6c9488c9e4d0d745151e10f8928024762035db250699d18e05
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 190 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf