De jury heeft de volgende inzendingen ontvangen.
Deelnemer: Edgar den Boef
Titel scriptie: A Branch-and-Bound Approach to the Multiple Container Loading Problem
In this report we address the problem of orthogonally packing a set of items into a set of containers such that the costs of the used containers are minimized. We present a branch-and-bound algorithm for this problem. Furthermore, we describe a single container loading heuristic that can be used in the branch-and-bound method. To reduce runtime we add several heuristic adjustments. One of them, called MultiFit, simultaneously places similar items in a container. These heuristic adjustments are tested and the results of these tests are presented. These results show that a heuristic version of the algorithm with MultiFit runs slightly faster with on average better solutions than a heuristic version without MultiFit. Furthermore, using only heuristics to place items in a single container instead of an exact algorithm leads to substantially lower runtimes with only a slight decrease in solution value.
Deelnemer: Harold Bol
Titel scriptie: METRIC in praktijk
Doel van het afstudeerproject was het uitvoeren van een verkenningsonderzoek naar de mogelijkheden van METRIC (Multi-Echelon Technique for Recoverable Item Control) in het bedrijfsleven. METRIC is een geavanceerde methode voor de voorraadbeheersing van spare parts, en is reeds bekend binnen defensie omgevingen. Het sterke punt van METRIC t.o.v. traditionele voorraadbeheersingsmethoden voor spare parts is dat METRIC zich direct richt op het maximaliseren van de fractie up-time van een technisch systeem.
Het onderzoek is uitgevoerd bij Honeywell Industrial Control. Voor de spare parts van het Honeywell Total Distributed Control Systeem is de METRIC methode vergeleken met zowel de huidige methode als een rechttoe-rechtaan methode die in vele bedrijven wordt gebruikt. Uit het onderzoek blijkt dat het verbeterpotentieel van METRIC groot is. Door METRIC te gebruiken kan men een zelfde systeembeschikbaarheid bereiken tegen 50 - 70 % lagere kosten. Daarnaast is op een rij gezet in hoeverre de METRIC theorie nog uitgebreid dient te worden alvorens deze echt kan worden toegepast in het bedrijfsleven.
Deelnemer: Ilja Bongers
Titel scriptie: Is het gedrag van kinderen werkelijk van hun zelf?
In dit scriptie onderzoek zijn de beoordeling door de ouders van het internaliserende en externaliserende probleemgedrag van hun kinderen bestudeerd. Dit is onderzocht bij 672 tweelingparen waarvan de ouders (moeders en vaders) de CBCL/4-18 ingevuld hebben. Deze steekproef is representatief voor de Nederlandse populatie wat betreft het werkniveau van de ouders en het voorkomen van gedragsproblemen bij de tweelingen. De univariate analyse van de gegevens van de moeder en de vader apart resulteerde in sekseverschillen voor de dimensie externaliseren. Voor de dimensie internaliseren werden er geen sekseverschillen gevonden. Door het simultaan analyseren van de beoordelingen door moeder en vader is onderzocht in hoeverre de ouders hetzelfde gedrag van de kinderen beoordelen (trait variantie). De ouders beoordelen voor het grootste gedeelte hetzelfde probleemgedrag (60% - 75%). En de ouders komen overeen in de mate waarin ze ander gedrag van de tweelingen beoordelen (unieke variantie). Voor het externaliserend probleemgedrag beoordelen de ouders de jongens en de meisjes verschillend. Bij het internaliserend probleemgedrag zijn er geen verschillen in de beoordelingen van de jongens en de meisjes. In de trait variantie was de bijdrage van de genetische invloed (49%) bij de dimensie internaliseren het grootst en bij de dimensie externaliseren leverde de gedeelde omgevingsinvloeden (57% - 61%) de grootste bijdrage aan de trait variantie. De aanwezigheid van reciproque interactie tussen de tweelingen kon in deze steekproef niet aangetoond worden.
Deelnemer: Lars Eijssen
Titel scriptie: Cluster Analysis of Mircoarray Gene Expression Data
Binnen de genetica gaan de ontwikkelingen razendsnel. Naast het in kaart brengen van de genetische code van de mens, komen ook nieuwe technieken beschikbaar om genexpressies te meten. Een daarvan is de "DNA microarray" techniek, die ons in staat stelt om expressiewaarden voor duizenden genen tegelijkertijd te verkrijgen. Dit betekent wel dat interpretatie van de meetwaarden door een arts onmogelijk wordt. Clustering technieken maken het mogelijk om deze gegevens automatisch met computerapparatuur te evalueren.
In deze thesis worden verschillende clustering methoden toegepast, zowel klassieke methoden als modernere technieken gebaseerd op neurale netwerken, "fuzzy logic" en graaftheorie. Deze algoritmen worden toegepast op data sets waarvan bekend is welk materiaal bekeken is. Ze worden gebruikt om zowel genen (functioneel gerelateerd) als monsters (dezelfde diagnose) te clusteren. Ook worden selectie van interessante genen en automatische selectie van het aantal clusters behandeld.
De klassiekere algoritmen bouwen een hiërarchische structuur op waarbinnen alle genen of monsters een plaats vinden. Het op neurale netwerken gebaseerde algoritme probeert een netwerk te vormen op grond van zijn invoer, in analogie aan processen in de hersenen. Het "fuzzy logic" algoritme kent alle punten aan groepen toe, zodanig dat een punt ook in meer dan een groep terecht kan komen. Het graaftheoretisch algoritme vormt het clustering probleem om naar een analoog graaf probleem en lost dat op met veel gebruikte methoden uit dat gebied en geheeltallig lineair programmeren.
Het merendeel van de functionaliteit is geïmplementeerd in de Matlab (C) omgeving. De expressiewaarden kunnen hierbij in gangbare "spreadsheet" formaten worden aangeleverd. Omdat vooral patronen en niet absolute waarden belangrijk zijn, moeten de gegevens genormaliseerd worden. Ook moeten uit de vele standaard gemeten genen eerst interessante genen geselecteerd worden. Als de monster "labels" (de diagnoses) bekend zijn, kan genselectie gedaan worden door de expressie van elk gen met een ideaal onderscheidend profiel te vergelijken. Als deze onbekend zijn, kunnen genen geselecteerd worden op grond van een hoge variatie in hun expressie. Nadat dit gedaan is, kunnen de beschreven clustering functies op de gegevens toegepast worden, waarbij het aantal clusters meestal moet worden aangegeven. Omdat het aantal clusters niet altijd bekend is, is het mogelijk om dit automatisch te laten vaststellen. Hiervoor zijn evaluatiefuncties geïmplementeerd.
Alle algoritmen zijn getest op verscheidene data sets. De resultaten van deze experimenten geven aan dat genclustering bijna perfect gedaan wordt nadat bruikbare genen geselecteerd zijn. Omdat monsters niet vooraf geselecteerd zijn, kan men verwachten dat clustering van monsters moeilijker is. Dat was inderdaad het geval. De resultaten van alle algoritmen waren toch redelijk goed. Alleen een paar van de klassieke methoden lijken het slechter te doen. Vooral het "fuzzy logic" algoritme en het graaftheoretisch algoritme lijken veelbelovend te zijn. Genselectie bleek wel erg belangrijk: bij het gebruik van een ideaal profiel waren de resultaten goed, in het andere geval waren ze slecht. Automatische selectie van het aantal clusters voorspelde meestal, doch niet altijd, het correcte aantal clusters. De gebruikte implementaties hiervoor kunnen wel nog verbeterd worden. Tot slot bleken sommige elementen consistent verkeerd geclassificeerd te worden: wellicht betreft dit oorspronkelijk verkeerd geclassificeerde of atypische elementen. Ook kunnen groepen onbekende subgroepen bevatten.
Uiteraard bevatten de gedane experimenten een beperkt aantal gegevensverzamelingen en moeten de resultaten voorzichtig geïnterpreteerd worden. Dit voor ogen houdend, kan de conclusie zijn dat de clustering technieken het over het algemeen goed deden in de experimenten en dat ze gebruikt kunnen worden als ondersteuning bij het identificeren van genetische activatieroutes en het maken van de juiste diagnostische beslissingen.
Deelnemer: Ivo Eman
Titel scriptie: Margins for international trade
De sector Internationale Handel van het Centraal Bureau voor de Statistiek (CBS) is verantwoordelijk voor de publicatie van cijfers over de nationale export en import. Iedere maand moeten hierover gedetailleerde cijfers worden gepubliceerd. Het samenstellen van deze cijfers is niet louter een kwestie van het tellen van binnengekomen douanegegevens. Veel informatie aangaande de internationale handel ontbreekt op het moment van publiceren. Een van de belangrijkste oorzaken is het wegvallen van de economische grenzen binnen de EU. Het komt erop neer dat deze gegevens moeten worden opgevraagd bij de bedrijven zelf. Deze wijze van gegevensverzameling voorkomt niet dat veel informatie nog steeds niet voor de publicatiedatum binnenkomt bij het CBS, of dat de informatie incompleet is.
De handel van niet-responderende bedrijven wordt geschat. Dit gebeurt op twee verschillende manieren. Enerzijds wordt er geschat op basis van het verleden; het betreft dan voornamelijk grote bedrijven. Anderzijds wordt gebruik gemaakt van BTW-gegevens; het betreft hier kleine bedrijven, waarbij het schatten gebeurt door een vergelijking te maken met soortgelijke respondenten.
Het doel van de scriptie was om erachter te komen hoe goed deze schattingen zijn. De kwantificering van de kwaliteit werd gedaan in de vorm van betrouwbaarheidsmarges. Allereerst moet dan gekeken worden of er een onzuiverheid in de schattingen zit en vervolgens moet een variantie worden bepaald om te komen tot een marge. Hierbij speelt dan ook de kansverdeling een rol.
Door de complexiteit van de schattingsmethode die wordt gebruikt om de internationale handel te schatten, was het berekenen van een juiste variantie niet eenvoudig. Allereerst moest een juist steekproefmodel worden opgesteld. Varianties moesten ook op verschillende niveaus worden berekend. Zo wil het CBS graag weten hoe goed bijvoorbeeld hun totale exportschattingen zijn, maar wil ze ook weten hoe goed bijvoorbeeld de export van bloemen naar Duitsland wordt geschat. Vervolgens was de stap van variantie naar marge ook niet triviaal. Veelal wordt de Normale verdeling als kansverdeling verondersteld. Dit bleek in dit geval niet altijd even correct te zijn. Gekeken is uiteindelijk naar een empirische verdeling. Die deed het beter, maar is niet altijd toepasbaar; bijvoorbeeld op hoog aggregatieniveau is er te weinig informatie om tot een empirische verdeling te komen. Tot slot is er nog gekeken naar de zuiverheid van de schatters. Verder onderzoek bleek nodig om de marges echt te kunnen uitrekenen. Deze scriptie is er een aanzet toe.
Deelnemer: Jan Willem van Hoeve
Titel scriptie: Towards the Integration of Constraint Logic Programming and Mathematical Programming
- Introduction -
Constraint logic programming essentially provides an environment in which one can describe and solve a mixture of algebraic and logical constraints. Nowadays, it is applied mostly to planning and scheduling constraints. These types of problems are also in the domain of mathematical programming, and a comparison between these two approaches is therefore meaningful.
From the point of view of solution times, the mathematical programming approach is in many cases still superior to the constraint logic programming approach, when both approaches are applicable. There are several problem instances, however, that strongly depend on logical statements, and a constraint logic programming approach has proven to be significantly faster.
From the point of view of expressiveness of the language, constraint logic programming offers much more syntactical constructs than common mathematical programming languages. A constraint logic programming platform is thus preferable to a mathematical programming platform, with respect to the user's comfort.
Recent developments have shown that using the two approaches together can be quite beneficial, both in terms of solution time and expressive power of the language. Such a cooperation can be realized in several ways. It is possible to incorporate (parts of) one technique inside the other, but it is also possible to design a whole new framework in which both techniques are combined.
The research has been carried out at Paragon Decision Technology, the developers of the algebraic modeling language Aimms. Currently, Aimms can be used to describe and solve mathematical programming problems. As we have indicated above, the combination of constraint logic programming and mathematical programming is quite promising. Therefore, the developers of Aimms are interested in the advantages that constraint logic programming offers, with respect to their product.
- The thesis -
This thesis concerns the integration of constraint logic programming and mathematical programming, in particular with respect to the algbraic modeling language Aimms. During the time the task was performed, some 6 months, only a selection of this broad field could be considered. The following subjects have been considered:
- Theoretical background -
There has been given a global overview of constraint logic programming. Further, several possible combinations of constraint logic programming and mathematical programming are considered. Finally, an example has been presented that illustrates some possible benefits of such a combination.
- Extensions to the current syntax of Aimms -
The current syntax of Aimms has been extended with constraint logic programming constructs. First, some general principles concerning the extension of an algebraic modeling language are presented. Then, the syntax of Aimms has been extended, based on these principles.
- Constraint propagation as solution technique -
Constraint propagation is a solution technique that is used particularly in constraint logic programming. It can be used to narrow the ranges of the variables, using interval analysis. A propagation engine has been designed and implemented, which evaluates linear equations and inequalities. The propagation engine can be used to narrow the ranges of the variables, or to detect an infeasibility. When no infeasibility has been detected, the system is called locally consistent.
- Handling the Alldifferent constraint -
In constraint logic programming special global constraints are allowed to occur. One of such global constraints has been considered, namely the Alldifferent constraint. To check the feasibility of the Alldifferent constraint, there has been designed and implemented a fast algorithm. First, a very quick simple heuristic tries to find a feasible solution. If this heuristic does not succeed, we refer to a more careful heuristic. Finally, we can resort to the algorithm of Hall that will provide a global answer. Test results show that the implemented algorithm is very fast.
- The design of a Branch, Infer and Bound framework -
The propagation engine and the Alldifferent feasibility check have been used inside a Branch, Infer and Bound framework. In this framework, the branching is done on the ranges of the variables. On every node, the changes in the variable ranges are propagated. The propagation engine is also used to check the local consistency at each node. Furthermore, the Alldifferent constraint will be verified on every node. This framework can therefore be considered as a solver for systems that consist of linear constraints and the Alldifferent constraint. Although the framework performs quite well for small problems, the implementation encounters difficulties for bigger problem instances.
- A proposal for a general framework -
The branch, Infer and Bound framework is only a small step towards the integration of constraint logic programming and mathematical programming. A general framework has been proposed that incorporates both constraint logic programming and mathematical programming techniques. In particular, every extension to the syntax of Aimms should be covered by this framework. Only the contours of such a framework have been sketched. A more detailed description and the actual implementation will probably take several years of labour.
Deelnemer: Jeroen Kustermans
Titel scriptie: Use of OLAP-based Systems as the Core Technology for an On-line Inquiry Application for Data Collected from Surveys
I have completed my internship abroad, namely in the Heart of Information Technology: "Silicon Valley". The company is called MarketTools and is specialized in providing services to market research companies, which help those companies extend their current way of research with a web-based variant. Their main application suite makes it possible to deploy surveys on the web. This process is divided into three steps: preparing a questionnaire, deploying the questionnaire, and creating reports with data derived from the completed questionnaires.
The main task of my internship only dealt with the first step. All data derived from the completed surveys is stored on an OLTP system. OLTP systems are not optimized for reporting purposes, whereas an OLAP database is. My main task consisted of three separate child tasks: creating a new database of the type OLAP, creating the component that fills the database with data derived from the existing OLTP system, and creating a client that is specialized in creating reports with data coming from an OLAP system.
My introductory studies were split into two categories: basic studies and insight studies. Basic studies were used for self-study. This made me familiar with standard tools and techniques. The introductory studies were used to come up with custom solutions for those areas where standard solutions were not available or not sufficient. The functional design of the products and milestones to be delivered includes long-term planning. All functionality is described in this section, such as design requirements, platform-related questions, choice of methodologies and techniques, software, hardware etc. All processes will be described by using data flow diagrams, which serve as a red line for the design of the programs to be delivered. Planning of the whole time frame is done using step-by-step methodology.
OLAP database design is based on the cube principle. Every side of the cube stands for a data element. During the development of the database model of the OLAP system, I discovered that only two data elements could be applied to the relevant business process: time, and survey-question. Because the minimum amount of data elements that are used to construct a cube is three, I came up with a third one: geography. To create this new data element, I developed a module that is able to convert the unique network number of a computer (the IP address) to a geographical location. This module makes use of computers for public access, which are widely spread over the Internet. All computers offer a service that's able to return the address of those that are responsible for a specific hostname. This service is called WhoIs. Only one hostname can be requested at a time. In accordance to that, a lot of questions (queries) are needed. To process all these queries in an efficient way, I arranged that the result of all queries will be cached locally, and that all queries are spread over the whole world. When this conversion is done, the geographical origin from anyone who has completed the survey can be pinpointed.
To make this technology available for a broader audience than originally intended (the advanced researcher), I created a fourth product: a web module with the same "look and feel" as the existing report module. This module displays the origin of all respondents by colored geographical maps. To start well, and to end well, I had to come through a couple of functional and technical obstacles.
The work as a whole is rounded off with a test phase, the right people have been briefed, and the necessary documentation is delivered. It is safe to say that myself as well as MarketTools both feel confident about the prototypes that have been delivered, and that this experience has made me see the world of IT in a totally different light.
Deelnemer: Rutger van Oest
Titel scriptie: Some integration methods for Bayesian inference
In the Bayesian approach to inference, the parameters of a statistical model are not regarded as unknown constants but as random variables. This means that the parameters have a probability distribution. Modern Bayesian inference makes use of families of distribution functions that are not member of a known class of functions. As a consequence one has to solve certain integration problems that can be high-dimensional. A particular proposal for an integration method using Monte Carlo techniques is the subject of this Master thesis.
Monte Carlo integration methods are very useful in case the dimension of the integration problem is very large. These methods translate the integration problem into an estimation problem. The integral of interest is seen as an expectation and it is estimated by a mean of some pseudo-random drawings that are generated using a computer procedure.
In Bayesian analysis it turns out that it is often not possible to draw from the so-called posterior distribution of the parameters in a direct way. One solution for this is that one draws from an "easy" distribution that approximates the posterior distribution. In order to correct for the approximation error, the obtained sample is weighted, that is, the mean becomes a weighted mean. This is importance sampling. Another solution is that one draws from a Markov chain that converges to the posterior distribution. This leads to Markov Chain Monte Carlo (MCMC) methods.
We pay special attention to the so-called Adaptive Polar Sampling (APS) algorithm and we introduce the Adaptive Polar Importance Sampling (APIS) algorithm. The former is an MCMC method, while the latter is based on importance sampling. These two methods have in common that they involve a (special) polar transformation and that they are adaptive. Both aspects lead to better results. We conclude with a comparison of methods. Although the APS algorithm and the APIS algorithm use a lot of computing time, the results seem to be promising.
Deelnemer: Erwin Stinstra
Titel scriptie: Ontwerp en implementatie van een openbaar vervoer route planner
Het plannen van een route middels het openbaar vervoer wordt steeds complexer doordat enerzijds de geplande routes steeds langer worden en anderzijds de eisen die aan een route gesteld worden steeds hoger worden. Om het vinden van een beste route te automatiseren moet er dan ook met steeds meer verschillende aspecten rekening gehouden worden.
In dit afstudeerverslag modelleren we het openbaar vervoer met behulp van een graaf. We beschrijven algoritmiek voor het berekenen van de route die aan de mogelijke eisen van een reiziger voldoet. Verder gaan we in op de gegevensstructuren die aan de planner ten grondslag liggen. Deze structuren worden zo gekozen dat we eenvoudige wijzigingen in de dienstregeling snel kunnen doorvoeren, waarbij natuurlijk ook rekening wordt gehouden met de efficiëntie waarmee een openbaar vervoer route gevonden kan worden.
We beschrijven tenslotte een implementatie die rekening houdt met de verschillende situaties waarin de route planner gebruikt kan worden.
Deelnemer: Sita Tan
Titel scriptie: Parameterschatting voor een microsimulatiemodel met behulp van de score functie methode
Bij het instituut voor Maatschappelijke Gezondheidszorg worden microsimulatiemodellen ontwikkeld en toegepast om de gevolgen van epidemiologische ontwikkelingen en interventies op de volksgezondheid te evalueren. Door middel van simulatie kunnen de parameters van zo'n model worden geschat op basis van data. Men is op zoek naar die parameterwaarden waarvoor de met het model gesimuleerde uitkomsten zo goed mogelijk lijken op de waargenomen waarden in de data. Een belangrijk nadeel van simulatie is dat de uitkomst stochastisch is, waardoor speciale optimalisatiemethoden gebruikt moeten worden om de parameters te schatten.
Met behulp van de Score Functie (SF) methode kunnen schatters voor functiewaarden èn afgeleiden berekend worden voor verschillende parameterwaarden, op basis van slechts één simulatierun voor vooraf gekozen parameterwaarden. Voor andere parameterwaarden zijn schatters voor functiewaarden en afgeleiden expliciet te schrijven als functie van de uitkomsten uit deze ene simulatierun, waardoor het schatten van de model parameters, gegeven deze simulatierun, een deterministisch probleem is geworden, dat met behulp van standaard optimalisatiemethoden kan worden opgelost.
We hebben de SF-methode getest door de parameters van een eenvoudig model voor het natuurlijk verloop van borstkanker te schatten, op basis van uitkomsten van een borstkankerscreening programma. De uitkomst hiervan bleek veel nauwkeuriger dan die van een eerder geteste optimalisatiemethode.
Deelnemers: Frans Schalekamp en Anke van Zuylen
Titel scriptie: Over het schudden van kaarten
Hoe vaak moet een pak kaarten geschud worden? Sinds een artikel uit 1992 van Bayer en Diaconis, wordt algemeen verondersteld dat 7 keer schudden "genoeg" is om een "willekeurig verdeeld" pak kaarten te verkrijgen.
In deze scriptie hebben we dit antwoord kritisch bestudeerd. Behalve dat er bij de gebruikte criteria en aannames kanttekeningen geplaatst kunnen worden, is het frappant dat het getal 7 in het geheel niet in dit artikel voorkomt.
Het spel New Age Solitaire van Peter Doyle legt precies de vinger op de zere plek van de onderzochte schudmethode, de riffle shuffle. We geven een bewijs van het, tot nu toe alleen door simulaties bekende, feit dat New Age Solitaire een winstkans heeft van 81% na 7 keer schudden, terwijl een echt willekeurig verdeeld pak een winstkans van 50% heeft. Ook de door ons gebruikte methode om de aannames van het schudmodel te onderzoeken is nieuw. En passant stuitten wij bij het ontwikkelen hiervan op een groepentheoretisch feitje dat niet algemeen bekend was.