What is Choco ?

Choco is a Free and Open-Source Software[1] dedicated to Constraint Programming[2]. It is a Java library written under BSD license. It aims at describing hard combinatorial problems in the form of Constraint Satisfaction Problems and solving them with Constraint Programming techniques. The user models its problem in a declarative way by stating the set of constraints that need to be satisfied in every solution. Then, Choco solves the problem by alternating constraint filtering algorithms with a search mechanism. Choco is used for:

  • teaching : easy to use
  • research : easy to extend
  • real-life applications : easy to integrate

Choco is among the fastest CP solvers on the market. In 2013, 2014 and 2015, Choco has been awarded many medals at the MiniZinc challenge that is the world-wide competition of constraint-programming solvers.

 

In addition to these performance results, Choco benefits from academic contributors, who provide long term improvements, and the consulting company COSLING, which provides services ranging from training, support to the development of interactive decision support web-services.

[1]: Choco is hosted on GitHub and distributed under BSD license (Copyright(c) 1999-2015, Ecole des Mines de Nantes).
[2]: Constraint programming is a technology at the crossroad between Artificial Intelligence and Operational Research, enabling to solve a wide range of complex problems arising in planning, scheduling, logistics, financial analysis, bioinformatics, etc. (read more on wikipedia).


Technical overview

Choco includes:

  • various type of variables (integer, boolean, set and real),
  • many global constraints (alldifferent, nvalues, circuit, cumulative, knapsack, bin packing, etc.),
  • state-of-the-art search strategies, from basic ones to most complex (activity-based search, large neighborhood search, etc.),
  • explanation-based engine, that enables conflict-based back jumping, dynamic backtracking and path repair,

But also facilities to interact with the solver, factories to help modeling, many samples, an interface to Ibex, etc. Choco also has many extensions, including a FlatZinc parser to solve minizinc instances and a graph variable module to better solve graph problems such as the TSP.


Main contributors

The first version of Choco dates from the early 2000s. A few years later, Choco v2 has encountered a great success in both the academic and the industrial world. For maintenance issue, Choco has been completely rewritten in 2011, leading to Choco v3. The first beta version of the Choco v3 solver has been released in 2012. In 2016, the API is revamped, leading to Choco v4.
Maintenance and development tools are provided by the members of both INRIA TASC team and COSLING, especially by Charles Prud'homme and Jean-Guillaume Fages.

Core developpers Charles Prud'homme (INRIA TASC), Jean-Guillaume Fages (COSLING).
Choco contributors Fabien Hermenier, Narendra Jussien, Jimmy Liang, Xavier Lorca.
Previous versions contributors Nicolas Beldiceanu, Hadrien Cambazard, Sophie Demassey, François Laburthe, Arnaud Malapert, Julien Menana, Guillaume Richaud, Guillaume Rochart, Thierry Petit, Julien Vion, Stéphane Zampelli.

A reference to Choco should be made like this:


@manual{choco,
  author        = {Charles Prud'homme and Jean-Guillaume Fages and Xavier Lorca},
  title         = {Choco Documentation},
  year          = {2015},
  organization  = {TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S.},
  timestamp     = {Thu, 11 May 2015},
  url           = {http://www.choco-solver.org },
}

Choco has been funded by the grant L'Europe s'engage en Pays de la Loire.
It is developed with Intellij IDEA and JProfiler.

Subscribe to choco-solver.org RSS