Find JSRs
Submit this Search


Ad Banner
 
 
 
 

Summary  |  Proposal  |  Detail (Summary & Proposal)
JSRs: Java Specification Requests
JSR 331: Constraint Programming API

Stage Access Start Finish
Maintenance Release Download page 16 Oct, 2012  
Maintenance Draft Review Download page 30 Aug, 2012 29 Sep, 2012
Final Release Download page 07 Mar, 2012  
Final Approval Ballot View results 07 Feb, 2012 20 Feb, 2012
Proposed Final Draft Download page 30 Sep, 2011  
Public Review Ballot View results 04 Jan, 2011 10 Jan, 2011
Public Review Download page 22 Nov, 2010 10 Jan, 2011
Early Draft Review Download page 30 Mar, 2010 28 Jun, 2010
Expert Group Formation   18 Aug, 2009 10 Nov, 2009
JSR Review Ballot View results 04 Aug, 2009 17 Aug, 2009
Status: Maintenance
JCP version in use: 2.7
Java Specification Participation Agreement version in use: 2.0


Description:
This specification defines a Java runtime API for constraint programming. The CP API prescribes a set of fundamental operations used to define and solve constraint satisfaction and optimization problems.

Please direct comments on this JSR to the Spec Lead(s)
Team

Specification Leads
  Jacob Feldman Feldman, Jacob
Expert Group
  Creative Arts & Technologies Feldman, Jacob Jussien, Narendra
  Samsung Electronics Corporation Simonis, Helmut Szymanek, Radoslaw
  Vergamini, Didier Viry, Patrick

Updates to the Original JSR

The following information has been updated from the original proposal.

2009.11.30:

2.8 Is there a proposed package name for the API Specification? (i.e., javapi.something, org.something, etc.)

javax.constraints

2.13 Please describe the anticipated schedule for the development of this specification.

  1. Early Draft Review: March 1, 2010
  2. Complete the Specification, Public Draft/Final Release: September 1, 2010
  3. Maintenance Review: December 15, 2010

2.16 Please describe how the RI and TCK will be delivered, i.e. as part of a profile or platform edition, or stand-alone, or both. Include version information for the profile or platform in your answer.

We expect that initial Reference Implementations (RI) will be developed based on popular open source constraint solvers written in Java such as:

- Choco, available under BSD open source license
- Constrainer, available under LGPL open source license.

We plan to use Java Compatibility Test Tools to develop a Technology Compatibility Kit (TCK). TCK will be available at no cost to non-profits and qualified individuals.

3.1 Please list any existing documents, specifications, or implementations that describe the technology. Please include links to the documents if they are publicly available.

The CP technology description is available from many web sites such as: [1] On-line Guide to Constraint Programming by Roman Bartak http://kti.ms.mff.cuni.cz/~bartak/constraints/
[2] ILOG CP,http://ilog.com/products/cp/
[3] The Choco Project, http://www.emn.fr/x-info/choco-solver/doku.php?id=introduction
[4] The Gecode Project, http://www.gecode.org/doc-latest/modeling.pdf
[5] The CP-Inside Project, http://4c110.ucc.ie/cpinside/files/CPInside_API_UserManual.pdf
[6] www.cpstandards.org
[7] The Comet Programming Language and System, www.comet-online.org
[8] The G12 Constraint Programming Platform, www.g12.csse.unimelb.edu.au

There are many books devoted to the CP Technology:

Constraint Processing, Rina Dechter, Morgan Kaufmann, 2003

Constraint Satisfaction in Logic Programming, Pascal van Hentenryck, MIT, 1989

Essentials of Constraint Programming, English Thom Fruehwirth and Slim Abdennadher, Springer, 2003

Foundations of Constraint Satisfaction, Edward Tsang, Academic, 1993

Principles of Constraint Programming, Krzysztof R. Apt, Cambridge University Press 0-521-82583-0


Original Java Specification Request (JSR)

Identification | Request | Contributions | Additional Information

Section 1. Identification

Submitting Member: Jacob Feldman

Name of Contact Person: Jacob Feldman

E-Mail Address: j.feldman@4c.ucc.ie

Telephone Number: +353 21 4205966

Fax Number: +1 732 662 5034


Specification Lead: Jacob Feldman

E-Mail Address: j.feldman@4c.ucc.ie

Telephone Number: +353 214255463

Fax Number: +353 214255424


Initial Expert Group Membership:

INSERT

Supporting this JSR:

CP tool vendors, leading research centers in CP and Optimization, Decision Support Software system and tool vendors including rule engines, well-known CP experts

The following companies and experts expressed their interest in CP standardization:

- ACP, Association for Constraint Programming, Barry O’Sullivan, President
- CP vendors:
o ILOG, now an IBM company, the leading CP vendor and a JCP member (Contacts: CP product manager Paul Show and director of standards Christian de Sainte)
o Gecode (Christian Schulte)
o Choco (Narendra Jussien)
o Comet (Laurent Michel and Pascal van Hentenryck)
o G12 MiniZinc(Peter Stucky and Mark Wallace)
o Koalog (Yan Georget)
o JaCoP (Radoslav Szymanek)
o Dash (Y. Colombani)
o Ateji (P. Viry)
o Facile (P. Brisset)
o Minion (I. Gent and C. Jefferson)
- OpenRules, an open source business rules management system (J.Feldman)
- TIBCO (Paul Vincent)

I expect that Prof. Narendra Jussien (Head of the CS department Ecole des Mines de Nantes, President of the AFPC) will be my co-lead for this JSR.



Section 2: Request

2.1 Please describe the proposed Specification:

This specification defines a Java runtime API for constraint programming. The standardized CP API aims to make CP technology more accessible for business software developers. It intends to create CP Standards that will define unified business interface(s) for modeling and solving real-world decision support problems as Constraint Satisfaction and Optimization Problems. Having unified interfaces will allow commercial application developers to model their problems in such a way that the same model can be tried with different CP Solvers. This will minimize vendor dependence without limiting vendor's innovation. At the same time the CP API will help to bring the latest research results to real-world business applications. The CP API prescribes a set of fundamental operations used to define and solve constraint satisfaction and optimization problems. The sets of operations will allow a user to express its decision support problem in terms of:
- Decision Variables defined as constrained integer, real, and set variables
- Constraints defined on these variables using the standardized unary, binary and global constraints.
Clearly separating the problem definition from problem resolution, the sets of operations will allow a user to apply standardized search strategies to find feasible and optimal solutions of the problem. The CP API will also allow a user to create custom constraints and search strategies in a unified way making them independent from a particular CP solver.

2.2 What is the target Java platform? (i.e., desktop, server, personal, embedded, card, etc.)

This specification target the Java Platform, Standard Edition (Java SE) allowing a user to develop and deploy CP-based Java decision engines on desktops and servers, as well as today's demanding Embedded and Real-Time environments.

2.3 The Executive Committees would like to ensure JSR submitters think about how their proposed technology relates to all of the Java platform editions. Please provide details here for which platform editions are being targeted by this JSR, and how this JSR has considered the relationship with the other platform editions.

To make sure that the proposed technology can be used with all of the Java platform editions, the standard CP interface will use only the standard Java constructions available for all JDKs starting with 1.4. However, concrete implementations of the proposed standardized interface will be able to take an advantage of the latest Java editions.

2.4 Should this JSR be voted on by both Executive Committees?

The CP API JSR will be voted by the SE/EE.

2.5 What need of the Java community will be addressed by the proposed specification?

This specification addresses the community need to reduce the cost associated with incorporating CP solvers within business applications. It will also address the community need to reduce the cost associated with implementing vendor- and platform-independent decision support optimization tools and services.

2.6 Why isn't this need met by existing specifications?

Today CP is a proven optimization technique and many CP solvers empower real-world business applications in such areas as scheduling, planning, configuration, resource allocation, and real-time decision support. However, the absence of standards still limits the acceptance of CP by the business world.

While dissimilar vendor-specific CP API specifications exist, their syntactic and semantic differences are significant enough to cause costly difficulties for application builders and platform vendors.

2.7 Please give a short description of the underlying technology or technologies:

The key underlying technology is the constraint solver such as Choco?, Gecode?, or ILOG CP? to name a few. A constraint solver usually comes with its own API to define constraint satisfaction and optimization problems using generic constrained variables and predefined constraints. A constraint solver supports different types of constrained variables (integer, boolean, real, sets) with different implementations of their domains. A constraint solver provides a set of predefined unary, binary and global constraints and it allows a user to introduce its own constraints. A constraint solver also provides different search algorithms with ability for a user to customize them or define new, problem specific ones. These algorithms can be used to find a feasible solution, all solutions or the optimal solution. Constraint solvers usually include sophisticated constraint propagation, goal execution, and backtracking mechanisms.

2.8 Is there a proposed package name for the API Specification? (i.e., javapi.something, org.something, etc.)

javax.cp

NOTE that this section has been updated from this original proposal.

2.9 Does the proposed specification have any dependencies on specific operating systems, CPUs, or I/O devices that you know of?

No

2.10 Are there any security issues that cannot be addressed by the current security model?

No

2.11 Are there any internationalization or localization issues?

No

2.12 Are there any existing specifications that might be rendered obsolete, deprecated, or in need of revision as a result of this work?

No

2.13 Please describe the anticipated schedule for the development of this specification.

Please note that this information has been updated from this original proposal.

1. Early Draft Review: November 20, 2009

2. Complete the Specification, Public Draft/Final Release: April 15, 2010

3. Maintenance Review: June 30, 2010

2.14 Please describe the anticipated working model for the Expert Group working on developing this specification.

The JSR Specification Lead has already contacted major CP vendors and well-known CP experts and involved them in a preliminary discussion at www.cpstandards.org. We will invite them to join the Expert Group right after the initial JSR Review and acceptance. We plan to have an kick-off meeting during the oncoming major CP conference CP-2009 that will take place at Portugal on 20-24 September 2009. A preliminary Java CP API that will become a basis for the JSR is being discussed by CP experts at the Discussion Forum at www.cpstandards.org. During the first 3 months we plan to finalize the Expert Group that will include the most active contributors to the Early Draft.

2.15 Provide detailed answers to the transparency checklist, making sure to include URLs as appropriate.

? The public can read who is on the Expert Group: YES

? The Expert Group business is regularly reported on a publicly readable alias: YES

? The schedule for the JSR is publicly available, it's current, and I update it regularly: YES

? The public can read/write to a discussion forum or wiki for my JSR: YES, a preliminary Java CP API that is considered to become a basis for the JSR is being discussed by CP experts at the Discussion Forum at www.cpstandards.org.

? The public can write to an alias with feedback and comments on my JSR: YES

? There is an issue-tracker for my JSR that the public can read: YES, the issue-tracker will be added to www.cpstandards.org

? I have spoken at conferences and events about my JSR recently: YES, at OMG meeting on Dec-2008 in Santa Clara, CA. "A Unified Business Interface for Modeling and Solving Constraint Satisfaction Problems" (http://openrules.com/presentations/OMG.Dec08.2008.JacobFeldman.v2.pdf) and at the Sixth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CP-AI-OR May-2009 in Pittsburgh, PA (http://wpweb2.tepper.cmu.edu/rlang/CPAIOR09/program.html)

? I am using open-source processes for the development of the RI and/or TCK. YES, our reference implementation is oriented to open source CP solvers

? The Community Update page for my JSR has links to and information about all public communication mechanisms and sites for the development of my JSR: YES, see www.cpstandards.org

2.16 Please describe how the RI and TCK will be delivered, i.e. as part of a profile or platform edition, or stand-alone, or both. Include version information for the profile or platform in your answer.

Please note that this information has been updated from this original proposal.

We expect that a Reference Implementation (RI) will be developed based on one of two popular open source constraint solvers written in Java:

- Choco, available under BSD open source license
- Constrainer, available under LGPL open source license.

We plan to use Java Compatibility Test Tools to develop a Technology Compatibility Kit (TCK). TCK will be available at no cost to non-profits and qualified individuals.

2.17 Please state the rationale if previous versions are available stand-alone and you are now proposing in 2.13 to only deliver RI and TCK as part of a profile or platform edition (See sections 1.1.5 and 1.1.6 of the JCP 2 document).

No previous versions are available

2.18 Please provide the full text of the licenses that will apply to your Final Release Specification, Reference Implementation and Technology Compatibility Kit, or provide links to the same.

We plan to use the following licenses:

1. Final Specification: http://jcp.org/aboutJava/communityprocess/speclead/final-license.txt
2. Final Reference Implementation: The Common Public License (CPL), http://www.ibm.com/developerworks/library/os-cpl.html
3. Final Technology Compatibility Kit – The Common Public License (CPL), http://www.ibm.com/developerworks/library/os-cpl.html





Section 3: Contributions

3.1 Please list any existing documents, specifications, or implementations that describe the technology. Please include links to the documents if they are publicly available.

Please note that this information has been updated from this original proposal.

The CP technology description is available from many web sites such as: [1] On-line Guide to Constraint Programming by Roman Bartak http://kti.ms.mff.cuni.cz/~bartak/constraints/
[2] ILOG CP,http://ilog.com/products/cp/
[3] The Choco Project, http://www.emn.fr/x-info/choco-solver/doku.php?id=introduction
[4] The Gecode Project, http://www.gecode.org/doc-latest/modeling.pdf
[5] The CP-Inside Project, http://4c110.ucc.ie/cpinside/files/CPInside_API_UserManual.pdf
[6] www.cpstandards.org

There are many books devoted to the CP Technology:

Constraint Processing, Rina Dechter, Morgan Kaufmann, 2003

Constraint Satisfaction in Logic Programming, Pascal van Hentenryck, MIT, 1989

Essentials of Constraint Programming, English Thom Fruehwirth and Slim Abdennadher, Springer, 2003

Foundations of Constraint Satisfaction, Edward Tsang, Academic, 1993

Principles of Constraint Programming, Krzysztof R. Apt, Cambridge University Press 0-521-82583-0

3.2 Explanation of how these items might be used as a starting point for the work.

The starting point for the JSR is defined at www.cpstandards.org - see http://4c110.ucc.ie/cpstandards/javadoc/index.html

The user manuals for concrete solvers and well-known CP books will be used to define the standardized naming convention and common concepts



Section 4: Additional Information (Optional)

4.1 This section contains any additional information that the submitting Member wishes to include in the JSR.

This specification assumes the existence of parallel efforts to specify a CP modeling language and a unified XML schema for Constraint Satisfaction Problems. Java CP API is considered as a Java specific representation of generic CP concepts ? see more at http://4c110.ucc.ie/cpstandards/index.php/en/standards