Road to CP Standardization

Yesterday, when I started this blog, the very first picture offered by wordpress.com was the road (see above). In spite of Helmut’s kind suggestions of his own nice images, I’ve decided to stick to this one: a lot of similar looking but still unique trees and a man walking on a road without end – I like such coincidences. When I stepped on the CP “Standardization Road” almost a year ago I knew it was not going to be a quick trip with an easily reachable destination in spite of the fact that many CP experts were and still are on this road. We are all busy with many more important priorities and from time to time have to step aside or take a stop. Those are the normal real life constraints and it is my hope that the CP community will continue to build and improve on this road.
We started with the http://www.cpstandards.org/ site that clearly specified objectives and invited all CP experts to participate in a discussion forum. The challenge was (and still is) how to give real-word application developers access (via a unified interface) to the power of already existing, great CP solvers while not limiting innovation for CP vendors and researchers. The basic CP concepts (CSP, constrained variables, constraints, solver with search strategies, etc) are de-facto standardized in spite of the different names given those CP products. Another challenge we enforced on us by ourselves: “The same application code should continue to work when a user switches from one underlying implementation to another without changing a word”. Along with simplicity and openness I thought this requirement to be crucial for real-word acceptance in an environment where CP is still considered the prerogative of gurus.

I have actively used CP as a consultant for major US corporations since 1993, was a developer of a Java-based CP solver, and work with a major CP research centre without representing any CP vendor. In my (from the trenches) view some of the key milestones on the road to CP standardization are as follows:

1. Initial CP Standard Core Interface that covers all features commonly used by many CP practitioners in real-world business applications
a. Define an extensible architecture that supports the development of pluggable CP-based decision engines
b. Start with constrained integer and boolean variables only but keep in mind similar interfaces for real and set variables making sure that they could be added as we go
c. Define a common way for constraint posting but limit the core to the most popular global constraints only
d. Enforce any standard implementation solver to provide at least one search strategy but specify a way to add more strategies and their combinations as we go.
e. The core should respect the variety of different CP implementation approaches instead of committing to one approach
2. Initial CP Standard Implementations
a. Develop ASAP several (at least two) good standard implementations openly available to everybody who wants to use the standard
b. Start with main-stream programming languages while keeping in mind already existing specialized CP languages and new dynamic languages
c. Even initial standard interface and its implementations should not just play with toy problems but show their power on real-world challenging tasks
3. Add real and set variables with related constraints
4. Add vertical packages built on top of the CP core:
a. Scheduling and Resource Allocation
b. Configuration
c. Routing
d. Other verticals
5. Integration with LP and MIP tools
6. Multiple Implementations in main-stream dynamic languages
a. Java and JVM-oriented languages (Grovy, Scala, Clojure, Jython, …)
b. C++ and .NET oriented languages (C#, Python, Boo,…)
7. Other milestones (e.g. CP XML, CP DSL, …)

The first official CP Standardization Discussion was held in September-2009 at the CP Conference in Lisbon. Almost one year later we are coming closer to the first two milestones. I will talk about JSR-331 and consider different standardization issues in oncoming posts. For now I just want to express my appreciation to many CP experts (being standardization supporters or not) who have already provided a very constructive critique and valuable suggestions. The milestones 3-7 are not sequential and do not have strict dates to be reached: they will be adjusted and more milestones will be added as we go, but an important fact is that as a CP community we are on this road.
A friend of mine always ends his emails with the same motto that is appropriate to end my first post:
Keep the light,
Jacob

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Road to CP Standardization

  1. CVictor says:

    I would rewrite the no. 6 as follows:
    6. Multiple Implementations in main-stream dynamic languages
    a. C++ (as it is a standard)
    b. Python, Java and JVM-oriented languages (Grovy, Scala, Clojure, Jython, …) (as Python isn’t originally a .NET language)
    c. .NET oriented languages (C#, Boo,…)

  2. jacobfeldman says:

    Probably you are right calling C++ a standard. Many very good CP solvers (like ILOG and Gecode) are implemented in C++, and now Google “or-tools” also has its core in C++. If these tools provide Java interfaces they usually are not first class citizens of these environments. Is not this one of the reasons why such a great technology as CP still lives within its own world and does not really penetrate the world of business applications dominated by Java?

  3. Pingback: Six New JSR-331 Implementations with Linear Solvers | Constraint Programming Standardization Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s