Watched Literals and Learning for Constraint Programming

The following text is rated 67 on the Flesch reading-ease scale, with 60-70 the target for a general audience.Constraints allow us to express many facts in every day life and in puzzles. Think about the recent craze for the Sudoku puzzle. We have to put a number from 1 to 9 in each square of a 9x9 grid. The constraints are that the numbers in each row, column, and 3x3 square must all be different. Researchers in Constraint Programming study how to solve problems like this using computer programs, so that people do not have to solve them themselves. For Sudoku, that might take the fun out of it, but it is less fun scheduling aircraft to arrive at the right gate in a safe and economic way, and the consequences are more serious if you get it wrong. There are many other important problems which Constraint Programming can help with. In this research we will address a number of the most important questions underlying constraint programming. We hope to come up with new answers to old questions, as well as asking new questions which perhaps should have been asked a long time ago. The first question we will look at is how to deduce new facts from old. In constraint programming this is called propagation . In Sudoku, what should you do if you work out that a certain square cannot have a 9 in it? If you can work out any new facts from this, you want to do this as quickly and easily as possible. On the other hand, if there are no new facts to work out, what you'd like to do is nothing! We have recently developed a new way of doing propagation, to give us more chance of doing nothing when there is no chance of working out new facts. The technique is called watched literals . It is obviously better to do nothing instead of something, and so watched literals can make constraint programs run a lot faster. To show the real value of watched literals, we need to do a lot of work on showing how more and more different kinds of constraints can be made to work with them. We also need to understand the general properties of watched literals, to make it easier for us and others to develop new ways to propagate using them. The result should be better constraint programs.The second question we will look at is how to do some of the most basic operations in constraint programming. Some of the tasks we are looking at may take only fractions of a microsecond to do on a modern computer, but we still want to make those fractions as small as possible. To do this, we have to understand in excruciating detail what goes on every time a constraint program does something like checking to see if a number is still allowed to be put in a certain square on the Sudoku grid. Then we have to work out a lot of different ways of doing a simple task like this, build different constraint programs using each way, and perform experiments to see how each one performs. Then we are in a position to tell researchers in constraint programming how the most basic tasks should be done. This kind of work sounds basic, but it is basic in the sense of fundamental. This kind of fundamental research will let us, and everyone else in constraint programming, do their future work better. The third and final question we will look at is how to make constraint programs learn from their own mistakes. Any constraint program makes a lot of mistakes, maybe even billions, before finding the right answer. By learning from the early mistakes, we can get the constraint program to avoid making a lot of the later ones. This idea is very well understood, but has not yet made its way into the fastest constraint programs. The idea of watched literals that we mentioned earlier should marry very well with learning, so we will research how to do this. We think this is the ideal task for a PhD student to work on, building on the research of others while doing their own first piece of world-class research.