Engineering combinatorial optimization algorithms to improve the lifetime of OLED displays

Abstract

In this thesis, we consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. To this end, we model this problem as an integer linear program. Subsequently, we refine this formulation by exploiting the combinatorial structure of the problem. We establish a general approximation framework based on network flow techniques. We apply an algorithm engineering approach to improve our heuristics by interacting experimental evaluations and theoretical investigations. For example on the theoretical side, we present a fully combinatorial linear-time algorithm for the MAXFLOW problem on graphs with bounded bandwidth and accordingly numbered nodes. With respect to our application, we implement a custom-made version of this algorithm to solve an important subproblem. Finally, we develop fully combinatorial approximation algorithms well suited for being implemented in the hardware of a control device that drives an OLED display. Moreover, our algorithms achieve near optimal solutions in practice yielding significantly longer lifetimes of passive matrix OLED displays.

In dieser Arbeit betrachten wir ein Optimierungsproblem, das im Zusammenhang mit der Entwicklung von Steuergeräten für OLED Bildschirme auftritt. Unser Ziel ist es, die Amplitude der Stromstärke, die einen direkten Einfluss auf die Lebensdauer eines solchen Bildschirms hat, zu minimieren. Dazu modellieren wir das Problem als ein ganzzahliges lineares Programm. Danach verfeinern wir diese Formulierung, indem wir die kombinatorische Struktur des Problems ausnutzen. Wir erstellen ein allgemeines Approximationssystem basierend auf Netzwerkflusstechniken. Wir wenden einen algorithm engineering Ansatz an, um unsere Heuristiken durch wechselwirkende experimentelle Auswertungen und theoretische Untersuchungen zu verbessern. Zum Beispiel zeigen wir auf der theoretischen Seite einen vollkombinatorischen Linearzeitalgorithmus für das MAXFLOW Problem auf Graphen mit beschränkter Bandbreite und entsprechend nummerierten Knoten. In Bezug auf unsere Anwendung implementieren wir eine maßgeschneiderte Version dieses Algorithmus, um ein wichtiges Teilproblem zu lösen. Letztendlich haben wir einen vollkombinatorischen Approximationsalgorithmus entwickelt, der gut geeignet ist, um als Schaltkreis in ein Steuergerät für einen OLED Bildschirm integriert zu werden. Darüber hinaus erreichen unsere Algorithmen nahezu optimale Lösungen in der Praxis, was zu einer deutlich längeren Lebensdauer eines OLED Bildschirms mit passiver Matrix führt.