Binary quadratic optimization

Abstract

Optimering är ett viktigt verktyg vid beslutsfattande och speciellt då man undersöker och förbättrar produktionen i en fabrik. Matematiskt inbegriper lösningen av ett optimeringsproblem att hitta den bästa lösningen av alla tillåtna lösningar till problemställningen. Ett optimeringsproblem består av en objektsfunktion, variabler och bivillkor. Objektsfunktionen är ett matematiskt uttryck vilket man vanligen vill minimera eller maximera. Till exempel inom en fabrik vill man maximera vinsten eller minimera produktionskostnader. Variablerna beskriver till exempel hur mycket av en viss sorts resurs som behövs eller hur mycket tid som går åt i olika produktionssteg. Binära variabler kan vara beslutsvariabler som till exempel bestämmer ifall en fabrik skall placeras på en ort eller inte. Bivillkorena är funktioner som begränsar de tillåtna värdena för variablerna, till exempel att mängden använda resurser inte kan överstiga mängden tillgängliga resurser. Denna doktorsavhandling är baserad på de fem artiklar som finns bifogade i slutet av avhandlingen. Avhandlingens huvudtema är binärkvadratisk optimering. Det vill säga att objektfunktionen innehåller kvadratiska och bilinjära delar samt linjära delar. Huvudproblemet som granskats är Coulombglas-problemet. Coulombglas är en modell för en lätt dopad halvledare vid mycket låga temperaturer (några K) där elektronerna är belägna på vissa orenheter och elektronerna växelverkar kraftigt med varandra. Optimeringsproblemet är att placera ut elektronerna för att minimera totalenergin för systemet och då hitta grundtillståndet för materialet. En uppsättning testproblem med koppling till digital färganalys som jag även undersökt är de så kallade taixxxc problemen. Dessa så kallade gråskalaproblem är problemställningar där man har ett rutmönster och skall fylla en del av rutorna med svart färg och en del med vit färg, målet är att den gråa färg som ögat uppfattar skall vara så jämn som möjligt.