The CP summer Mercatto

After Philippe Gilbert (cycling) joining BMC Racing Team and Romelu Lukaku (soccer) joining Chelsea another great Belgian transfer happened during the summer mercato.
Leading computer scientist Pascal Van Hentenryck joins NICTA. This is a very good news for the field of CP that people like that will work together. More details in the press release.

RAII and backtracking

A conventional wisdom is that C++ is a powerful language but difficult to use and that could be unsafe. In fact, this is wrong. Only some languages like C++ may lead to safe applications.
Why? This is mainly due to RAII. RAII means Resource Acquisition Is Initialization. You can have a look at Wikipedia.

Here is the idea. Consider a mechanism that is mainly implemented thanks to two opposite actions. For instance, you want to manage a file: you need to open and to close it. You want to manage resources: you will need to acquire and to release the resources. You need to manage the memory: you need to allocate and to deallocate the memory.

Now, imagine that a problem can happen in your program and you would like to be able to manage it. In other words, you have a normal code and a problem occurs. You need to catch it and to continue the program in a safe way. The main issue is that you need to abandon some current process before applying the second action of your mechanism. For instance, you need to close the files or release the resource you take. The main difficulty is that the error may happen anywhere in the program, so it is not easy to know what are the open files, the required resources... and how to access to this data.

C++ offers a nice way to deal with such a problem:  you can easily respect the RAII principle which is  "the object which performs the first action also performs the second one". In addition, the first action is performed in the constructor and the second one in the destructor. If a problem occurs then an exception is triggered and the execution goes back until a catch is found. The advantage of C++ is that all the destructors of the objects that are no longer valid will be called. Therefore, the files that have been opened will be closed, the resources will be release and so on... In addition, this will automatically be performed, so you don't have to be worried about it.

You can't do that in Java, because there is no real equivalent to destructor. There is no guarantee that the finalize function will be called and there is no guarantee about the order along with they will be called.

This is a strong advantage for C++.

C# has been recently modified for this reason.

Ok, but what is the relation with CP?

In CP we have to manage the wipeout event (the failure), that is when an inconsistent state is met. This happens when a domain is emptied for instance. In this case, the current state is inconsistent and we need to stop it immediately. Thus, we are face to the problem I explained. This problem involves all the local objects that have been defined or also the memory management.

There are usually 3 ways to deal with this in your code:
- You use C++ and exceptions. Unfortunately, exception is a slow mechanism
- You use C++ and setjmp/longjmp. Setjmp is faster than exception. However, it is not C++ compliant because the destructors are not called. This method is used in a lot of Solvers (like Gecode or or-tools), mainly because it is fast. Unfortunately this does not respect the RAII principle. You will have to manage by hand some part of the code.
ILOG Solver did not recommend to use destructor and mentioned that destructor would not be called for object allocated on the solver heap. Maybe, this is the reason...
- You deal with a lot of test. So, you add a lot of "if" in your code to make sure that there is no failure that happens. Unfortunately, you do not respect the RAII principles...

Hence, it seems that there is no perfect solution.
In fact, there is a fourth solution, better than the previous ones and almost perfect, but I keep it for me :-)

List of accepted papers to CP2011 is out

This conference is the main international conference on the subject of constraint programming. The list of accepted papes is available here.

Answers to the LP/IP Quizz are online

You can find the slides of Martin Grötschel here.

Thank you to Martin Grötschel and the CPAIOR11 team for making them available.

The LP/IP History viewed by Martin Grötschel in 24 Questions

The LP/IP History viewed by Martin Grötschel in 24 Questions

The concluding talk of CPAIOR this year was given by Martin Grötschel who asked 24 interesting questions about the history of LP and IP.

1. The questions about LP were:
2. Who described the first linear equations solver?
3. Who had the first LP solver (without knowing it)?
4. Who formulated the first LP instance?
5. Who described the first LP solver?
6. Who described the first LP solver with impact in practice?
7. Who described the currently most frequently used LP solver?
8. Who implemented the first commercial LP code?
9. Who received a Nobel Prize for LP?
10. Who proved expected polyn. running time of the simplex method first?
11. Who described the first polynomial time linear equations solver?
12. Who had the first polynomial time LP solver (without knowing it)?
13. Who described the first polynomial time LP solver?
14. Who described the first polynomial time LP solver with practical impact?
15. Who described the currently most frequently used barrier LP solver?
16. What is the state of the art in LP solving?

and the questions about IP were:

1. Which is the most important paper on integer programming?
2. Which is the most important paper on combinatorial algorithms?
3. Who described the first cutting plane algorithm?
4. Who described the first branch&bound algorithm?
5. Who described the first branch&cut algorithm?
6. Who described the first column generation algorithm?
7. Who implemented the first commercial IP code?
8. Who described the first polynomial time IP solver?
9. What is the state of the art in MIP solving?

I wonder what the questions for CP could be ?? :

1. Who described the first CP solver?
2. Who had the first CP solver (without knowing it)?
3. Who formulated the first CP instance?
4. Who described the first CP solver with impact in practice?
5. Who described the currently most frequently used CP solver?
6. Who implemented the first commercial CP code?
7. Who received a Nobel Prize for CP? (I'm not sure we have one ;-) )
8. Who described the first backtracking search?
9. Who described the Branch and Bound for CP?
10. Who described the first global constraint and its filtering algorithm?
11. Who described/solved the first scheduling problem with CP?
12. ...

Any suggestion/remarks on what the questions/answers could be for CP are very welcome.

Probably some answers can be found in a talk given by Pascal Van Hentenryck at CPAIOR08: "30 Years of Constraint Programming". Maybe CP is simply too young and it doesn't really make sense yet... I like to think that the major discoveries for CP are still to come ;-)

Google or-tools new developments

Laurent Just sent an update on the or-tools mailing list:

- linear assignment (including dimacs challenge support): A. V. Goldberg and R. Kennedy, "An Efficient Cost Scaling Algorithm for the Assignment Problem." Mathematical Programming, Vol. 71, pages 153-178, December 1995.
- Min cost flow: R.K. Ahuja, A.V. Goldberg, J.B. Orlin, and R.E. Tarjan, "Finding minimum-cost flows by double scaling," Mathematical Programming, (1992) 53:243-266. http://www.springerlink.com/index/gu7404218u6kt166.pdf
- Max flow (many references, see graph/max_flow.h for details).
- SCIP support (see scip.zib.de). We will make a separate announcement on how to compile scip to be used in or-tools.
- Deviation constraint in the Constraint Programming solver : Pierre Schaus et. al., "Bound Consistent Deviation Constraint", CP07.
- Initial support for no good management in the CP search tree.
- 30-50% speedup on large sums in constraint programming.

My PhD thesis

Last week I attended the JFPC 2011. I was very happy to meet some people I haven't met for a long time ago (more than 15 years!). Philippe Vismare presented a nice study about common subgraphs identification.
Philippe and I were in the same office when we were phD students. I also studied the common subgraphs problem during my PhD. At JFPC, I also discussed with some people about some stuff that I wrote in my thesis and people complained because my thesis is no longer available. Thus, I decided to scan it and to put it online. You can find it one my webpage (be careful it is a 75MB pdf):
http://www.constraintprogramming.net/people/regin/papers/these.pdf

Unfortunately it is in french...

I hope that this document will be more cited now :-)