Constraint Satisfaction and The Stable Marriage Problem
Chapter 1 Introduction
1.1 Reasons for choosing this project
Constraint Satisfaction is an area of operational research which particularly interests me. In my
second year at university, I studied computing modules based around constraint satisfaction. I spent
endless amounts of time solving constrained problems by hand. The thought of using a constraint
programming tool to solve these problems was sure to bring me great enjoyment! I also chose to
research constraint satisfaction techniques because I knew they would tie in well with the operational
research modules I am studying this year.
1.2 Aims and Objectives
The foremost aim of this project is to enhance knowledge of constraint satisfaction techniques. A
second aim of the project is to learn the mechanics behind constraint programming, and to learn the
constraint programming tool, iLOG Solver. The mid section of the project will focus on a particular
area of constraint satisfaction known as the Stable Marriage Problem. A small application will be
created which can be used to solve a ‘Stable Marriage Problem’.
In order to learn about the various constraint satisfaction techniques, a series of background reading
must take place. This will include browsing through textbooks and scouring the Internet. These
techniques can then be used on some trivial examples. The findings can then be reported and
Knowledge of iLOG Solver will be enhanced by working through examples in the user manual.
Original examples will then be created which will be used to compare various techniques of
The majority of the research on the Stable Marriage Problem will be gathered from the Internet. It is
a relatively new area of research so there is not a vast amount of literature available on the topic.
Therefore, the Internet is probably the best option..