Daily life research: Logic and Football

The Lògica i Programació (LOGPROG) research group at LSI Department research helps in improving our daily life. Scientists like Roberto Nieuwenhuis, Mª Luis Bonet, Albert Rubio, or Javier Larrosa merge logic and computing into the daily life of many.

LOGPROG faces the typical "hard problems" that don't have standard algorithmic solutions, known as NP Complete Problems. Many real life problems are of this type. For example, the ones related to planning or the organization of shared resources: timetables, public transport scheduling, etc.

LOGPROG has developed the theoretical foundations that allow using Logic where formerly only numerical methods from, for example, Operations Research had been applied or failed. They have shown the convergence between methods originating in Logic, Operations Research and Constraint Satisfaction. This last area is where by Javier Larrosa works.

Roberto likes sports. He enjoys watching a good TV football match weekly as much as playing the occasional match with friends. However, he looks at this with a scientist eye. This has allowed him not only to watch good as well. At first view, hospitals seem to have little to do with football or with cutting fashion fabrics. At a deeper level, however, all of them face the same type of problems, NP problems to be more precise. A typical algorithmic solution will not do for them, or will perform suboptimally. This is where logic comes into play and performs better than typical and apparently more natural approaches.

For example, the Spanish Football League uses an apparently fair method to decide which teams will play against which others for all the football season. They do perform a lottery with the team names. However, when one inspects closely the results of this procedure, it is apparent that randomness is not as fair as it is supposed to be. In short, the resulting pairings of teams exhibit repetitive patterns. Usually the distribution of pairings is anything but homogeneous and typically "sequence effects" appear. That is, you have the same teams playing against each other once and again just after having played with the same major teams. This is what makes the Spanish League so uneven, i.e., some weeks are loaded with super heavyweight matches and other weeks have little activity or only involve minor teams. Besides that, some complementary and important aspects, like security, cannot be taken into account properly. For example, a "risk match" should not take place in late evenings or at night time but there is no provision for expressing this type of constraints. So, randomness not only could make a week boring but also more dangerous.

With logic, good software, and a 3x3 matrix (two dimensions for the teams and a third one for the information about the match). In this way you can express with the language of logic, thousands of restrictions. That is precisely how, since 2004, the Dutch League proceeds. They are using methods developed by LOGPROG. Roberto Nieuwenhuis, who was born in The Netherlands and loves soccer, is happy to know that the main organisers of the Dutch League trust his methods. Not only football spawns this reaction. Other members of the group who love basket, like Albert Rubio, can rejoice at thinking that as far back as 1992, Barcelona Olympics year, the UPC already help scheduling the matches of the ACB Basket League.

It's not just sports that get the benefits of this research. The St. Joan de Deu in Barcelona asked LOGPROG for their help in order to optimize the scheduling of their operation rooms. Also companies from the USA, like Intel and Microsoft are working with LOGPROG in the verification of chip design and of software, respectively. LOGPROG has developed along the years an important know how on translating customers specifications and constraints to logic.

On a different league, LOGPROG methods won the four categories of the SAT Modulo Theories Competition 2005 and now they are getting ready for the SAT Competition that will take place in may 2008.

The application of their methods is being applied in other areas of research as well. For example, Mª Lluïsa Bonet, works on its application to Biocomputing and Linguistics. Javier Larrosa worked on job shop scheduling.

Roberto is currently the recipient of a Spanish Science Ministry I3 Grant that allows him to devote himself solely to research, with no teaching obligations. He aims to use the three years of the grant to study solutions for both practical and theoretical problems an to improve LOGPROG current methods as well. There is also work to be done in the business front since the group is reconsidering the way that it relates to industrial contracts. Instead of selling just the solution of the problem as well as their consulting about it, they are thinking about selling their specific software. This may end up in a new business venture by the name of Barcelogic. Our best wishes to Barcelogic. We hope they will be able to solve many of our actual hard problems.

If you want to meet Roberto Nieuwenhuis or you are interested in getting extra information you can always attend:

• The 23rd Symposium of Logics and Computational Science IEEE (LICS 2008).
  
• The 14th Conference of Constraint Programming (CP 2008)
• The 19th International Conference about Rewriting Techniques and its Applications (RTA 2007)
• The 6th International Workshop about Satisfiability Modulo Theories (SMT 2008)

or browse his web page: http://www.lsi.upc.es/~roberto/