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 :-)

The Java/Scala choice to implement CP Solvers

I recently started to implement a solver in Java during my free time. I choosed Java for several reasons:

- it is still by far the most popular language

- integration and deployment facility of a Java project + portability

- most of my colleagues at n-Side know Java and they are less familiar with C++

- the development tools (eclipse/InteliJ) are wonderful

- good tradeoff between speed and ease of modeling

Of course the price to pay is this factor 3. I like a lot the point of view of Nate Brixius (developer of Solver Foundation) about that. Here are few extracts about his blog post:

"I did standard critical path scheduling in both C# and C++ and found that the C# version was only 10-15% slower. We went with C# and in the course of development we were able to find algorithmic improvements that resulted in a faster implementation that the original C++ codebase. "

"Many programmers (myself included) are much more productive writing C# code. This gives me more time to investigate possible algorithmic improvements, write good unit tests, etc. There are opportunity costs!"

This is also true for CP solvers, what really makes a difference to solve a problem with CP is the functionalities available in your solver: the modeling facility, the global constraints available, how easy it is to write a custom search, to do a LNS, restarts, make parallelisation ...

I'm certainly not the first one to have chosen Java to develop a CP solver. Two popular open source CP solvers are implemented in Java: Choco and Jacop. There is also a standardization project for solvers in Java.

One of my colleague (Gilles) at n-Side is a real "Scala Enthutiast" and made me discover this wonderful language called Scala.

Since that time, I don't think anymore that writing a model in Java is very convenient...

The really good thing about Scala is that its syntax is so flexible that you can use it to write DSL (If find Scala much better than Python to do that)

But the other cool thing about Scala is that it is at least as efficient as Java.

A comparison between C++, Java, Scala and Go made by Google was published at the Scala Days a few days ago on an algorithmic benchmark:

Scala was about 3 times slower and Java 5 times slower than an optimized C++ code.

Of course I didn't throw away all my Java implem but I started a Scala wrapper on top of it for fun (integration between Scala and Java is perfect in both direction). I choosed to make a syntax quite close to OPL/Comet because I'm used to it and I find it very clear. Here is how the Queen problem looks like in my Scala wrapper:

object Queens  extends Model {
   def main(args: Array[String]) {
  
      val cp = new CPSolver()
      
      val n = 6 //number of queens
      val Queens = 0 until n
      //variables
      val queens = for(i <- Queens) yield CPVarInt(cp,1 to n)
      
      var nbsol = 0
      cp.onSolution {
       nbsol += 1
      }
      
      cp.solveAll subjectTo {
       cp.add(alldifferent(queens))
       cp.add(alldifferent(for(i <- Queens) yield queens(i) + i))
       cp.add(alldifferent(for(i <- Queens) yield queens(i) - i))
      } exploring {
       //exploration of the search tree
       new Binary(queens)
      }

      //print some statistics
      println("#sol",nbsol)
      cp.printStats()
    }
}

Again, it seems that I'm not the only one to have taken that decision. The Jacop team also adopted the same approach and started to make a wrapper for their solver. Here is the Queen model in Jacop/Scala:

object Queen extends Application with jacop {

  val n = 50

  val q: List[IntVar] = for (i <- List.range(0, n)) yield new IntVar("q"+i, 0, n)

  def noattack(i: Int, j: Int, qi: IntVar, qj: IntVar) = {
 qi     != qj 
 qi + i != qj + j 
 qi - i != qj - j 
  }

  for (i <- 0 until n; j <- i+1 until n) noattack(i, j, q(i), q(j))

  val result = satisfy( search(q, first_fail, indomain_middle) )

  if (result) 
    q.foreach(qi => {
      for( i <- 0 until n) 
  if (qi.value() == i) print(" # ") else print(" . ")
      println

    })
  else println("No solution")
}

I think we may see even more Scala wrapper for CP solvers in the near future...

Cloud and iCloud

I am currently more and more involved in cloud computing management. Mainly because I am member of the Aeolus ANR project (see http://www.aeolus-project.org). The university for which I work, has also just hired Fabien Hermenier who comes from Ecole des Mines de Nantes and who was one of the developer of the Entropy system. Fabien has some very interesting problems of cloud management and he modeled some of them by using CP.  I hope to show that CP is a really efficient technique for solving these problems, mainly because it can easily integrate new additional constraints.

At the same time, Steve Jobs presented iCloud. I think this is really a revolution in cloud computing or maybe a revolution in marketing. Here is his idea: if you have musics on your computer that you bought from iTunes, now you will be able to access to this music from the iTunes music store! Great you still have the right to use what you paid for. But the true revolution of iCloud is the following: if you have some musics on your computer that you didn't buy from itunes (for instance you ripped a CD) then you will be able to access to this music from the iTunes music store for only $25 a year! They call this iCloud and as you can see on this slide

you have no longer to wait for the long upload like with Google or Amazon! In fact, they just need to upload the MP3 Tag! That's a new way to see cloud computing. Apple need just to know your MP3 Tags and upload them : how many lines of code for doing that ? 100 ? That's a revolution.
At the same they avoid a lot of problem like memory consumption, time transfer and so on... Note that they still need minutes for your MP3 tag.

In addition you buy one more time your music...

For sure, iCloud is different...

Blind reviewing

Here is a review I just received:
"The paper should be resubmitted with more references to the existing work about the All-Different constraint"

Open Source and Originality

Last week, a lot of people (including Pierre, Thierry and myself) attended the CP-AI-OR Conference in Berlin.

We had some discussions about a paper implementing Goal programming in an open source solver. I wondered what was the scientific contribution and I asked the question. In fact, the authors were not really able to answer to my question. It was a presentation associated with an abstract, thus I think that it is not really important. 

I am more interested in one argument that has been answered: "there is a scientific contribution because this is new for open-source". We discussed about this point. Here are some remarks. I am curious to know if you have some others:

First, it means that all existing "proprietary" stuff has absolutely no value because it is not open-source! This is a strange conception of the originality. I also wonder why the open-source has several licences which forbid to reproduce the open source concept or code (because rewritten is not equivalent to originality)... 

Then, some people suggested that the minimum of honesty  should be to present the ideas in that way:

"Hello all, I am going to present an implementation in my open source solver of some works that has been carried out in several non open source solvers. In addition, you need to know that these ideas was clearly documented in the other products. Therefore, our job was mainly to  integrate these works in our open source product"

I think it is an interesting point of view. However, I guess that it will be more complex to have a paper accepted with such an introduction.

At last, note that it is not mandatory to publish papers...