An open-source Java library for Constraint Programming

Last update: Jan 3, 2023

Overview

Documentation, Support and Issues
Contributing
Download and installation

Choco-solver is an open-source Java library for Constraint Programming.

Current stable version is 4.10.6 (11 Dec 2020).

Choco-solver comes with:

various type of variables (integer, boolean, set, graph and real),
various state-of-the-art constraints (alldifferent, count, nvalues, etc.),
various search strategies, from basic ones (first_fail, smallest, etc.) to most complex (impact-based and activity-based search),
explanation-based engine, that enables conflict-based back jumping, dynamic backtracking and path repair,

But also, facilities to interact with the search loop, factories to help modelling, many samples, etc.

Contact: Choco-solver on Gitter

Overview

// 1. Create a Model
Model model = new Model("my first problem");
// 2. Create variables
IntVar x = model.intVar("X", 0, 5);
IntVar y = model.intVar("Y", 0, 5);
// 3. Create and post constraints thanks to the model
model.element(x, new int[]{5,0,4,1,3,2}, y).post();
// 3b. Or directly through variables
x.add(y).lt(5).post();
// 4. Get the solver
Solver solver = model.getSolver();
// 5. Define the search strategy
solver.setSearch(Search.inputOrderLBSearch(x, y));
// 6. Launch the resolution process
solver.solve();
// 7. Print search statistics
solver.printStatistics();

Documentation, Support and Issues

The latest release points to a tarball which contains the binary, the source code, the user guide (pdf) and the apidocs (zip).

You can get help on our google group. Most support requests are answered very fast.

Use the issue tracker here on GitHub to report issues. As far as possible, provide a Minimal Working Example.

Contributing

Anyone can contribute to the project, from the source code to the documentation. In order to ease the process, we established a contribution guide that should be reviewed before starting any contribution as it lists the requirements and good practices to ease the contribution process.

And thank you for giving back to choco-solver. Please meet our team of cho-coders :

@cprudhom (Charles Prud'homme)
@ArthurGodet (Arthur Godet)
@jgFages (Jean-Guillaume Fages)

Supporting Choco with financial aid favors long-term support and development. Our expenses are varied: fees (GitHub organization, Domain name, etc), funding PhD students or internships, conferences, hardware renewal, ...

Download and installation

Requirements:

JDK 8+
maven 3+

Choco-solver is available on Maven Central Repository, or directly from the latest release.

Snapshot releases are also available for curious.

In the following, we distinguish two usages of Choco:

as a standalone library: the jar file includes all required dependencies,
as a library: the jar file excludes all dependencies.

The name of the jar file terms the packaging:- choco-solver-4.10.4-jar-with-dependencies.jar or - choco-solver-4.10.4.jar.

choco-solver-4.10.4-jar-with-dependencies.jar or
choco-solver-4.10.4.jar.

A Changelog file is maintained for each release.

Inside a maven project

Choco is available on Maven Central Repository. So you only have to edit your pom.xml to declare the following library dependency:

<dependency>
   <groupId>org.choco-solver</groupId>
   <artifactId>choco-solver</artifactId>
   <version>4.10.6</version>
</dependency>

Note that if you want to test snapshot release, you should update your pom.xml with :

<repository>
    <id>sonatype</id>
    <url>https://oss.sonatype.org/content/repositories/snapshots/</url>
    <snapshots>
        <enabled>true</enabled>
    </snapshots>
</repository>

As a stand-alone library

The jar file contains all required dependencies. The next step is simply to add the jar file to your classpath of your application. Note that if your program depends on dependencies declared in the jar file, you should consider using choco as a library.

As a library

The jar file does not contains any dependencies, as of being used as a dependency of another application. The next step is to add the jar file to your classpath of your application and also add the required dependencies.

Dependencies

To declare continuous constraints, Ibex-2.8.7 needs to be installed (instructions are given on Ibex website).

Building from sources

The source of the released versions are directly available in the Tag section. You can also download them using github features. Once downloaded, move to the source directory then execute the following command to make the jar:

$ mvn clean package -DskipTests

If the build succeeded, the resulting jar will be automatically installed in your local maven repository and available in the target sub-folders.

Choco-solver dev team

Comments

QuickXplain in Choco

Hi,

I'm a beginner in using Choco so any help would be higly appreciated. I want to ask if QuickXplain algorithm is already implemented in Choco or not? If not, how to start with it, what to do, is there any functions that I can use that would make the implementation easier?

Thanks.
support

opened by swEngineer4ever 28

Performance Issue having [ 404 vars -- 211 cstrs ]

Hi there! Iterating thru all the solution, choco gets stuck at arround solution 330.000 - is that a limitation of choco solver or did I do something wrong with declaring the constraint? Here's my code:

            Model model;
	int[] solvingResult;
	IntVar[] intVariables;
	int[] cssCoeffs;
	IntVar grossMargin;
	int grossMargingResult = 0;

	model = new Model("KEO");
	solvingResult = new int[powerPlantDataList.size()];
	intVariables = new IntVar[powerPlantDataList.size()];
	cssCoeffs = new int[powerPlantDataList.size()];

	for (int i = 0; i < solvingResult.length; i++) {
		intVariables[i] = model.intVar("x" + i, 0, (int) powerPlantDataList
				.get(i).getPMax());
	}

	grossMargin = model.intVar("db", -1000000, 1000000);

	int j = 0;
	for (PowerPlantData ppd : powerPlantDataList) {
		cssCoeffs[j] = (int) ppd.getCssHigh();
		System.out.println(cssCoeffs[j]);
		j++;
	}

	model.scalar(intVariables, cssCoeffs, "=", grossMargin).post();

	for (int i = 0; i < powerPlantDataList.size() - 2; i += 2) {
		model.arithm(intVariables[i], "=", intVariables[i + 1]).post();
	}

	model.setObjective(Model.MAXIMIZE, grossMargin);
	System.out.printf("%s\n", model.toString());
	Solver solver = model.getSolver();

	int counter = 0;
	while (solver.solve()) {
		System.out.println(counter + ". Durchgang von solve()");
		counter++;
		for (int i = 0; i < intVariables.length; i++) {
			solvingResult[i] = intVariables[i].getValue();
			grossMargingResult = grossMargin.getValue();
		}
	}
	System.out.println("Deckungsbeitrag gesamt: " + grossMargingResult);

	int a = 0;
	for (PowerPlantData ppd : powerPlantDataList) {
		ppd.setScheduleHigh(solvingResult[a]);
		a++;
	}

support

opened by Andreeew91 26

Finding all optimal solutions

In general, a problem can have more than one solution where the objective is optimal. Currently the library only finds the first. Is it possible to add functionality to find all the optimal solutions?

For example:

public static void main(String[] args) {
    Solver solver = new Solver();
    BoolVar a = VF.bool("a", solver);
    BoolVar b = VF.bool("b", solver);

    solver.post(ICF.arithm(a, "+", b, ">=", 1));

    solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE, a);
    System.out.println(a + ":" + b);

    solver.findNextOptimalSolution();
    System.out.println(a + ":" + b);
}

would print

a=1:b=0
a=1:b=1

opened by JLiangWaterloo 24

How to get All optimal solutions?
Like the code below, I set a OBJ to minimize in my model, I do need to get the optimal OBJ, but I also want to get all optimal solutions. Furthermore, if I want to get all solutions corresponding to (OBJ + 1), how can I do this? I've already seen the Choco 4.0.0 documentation and Javadoc, but I still can't solve this two problems.

model.setObjective(Model.MINIMIZE, OBJ); Solver solver = model.getSolver(); int count = 1; while(solver.solve()){ System.out.println("count = " + count); System.out.print(OBJ + "\n"); count++; }
bug
opened by csy1234 21

Scalar Constraint leads to wrong results

Hi there! When using the scalar constraint like model.scalar(intVarArray, COEFFS, "=", db).post(); The result is leading into wrong values when I'm having the Arrays intVarArray and COEFFS with an amount of values greater than 10 values. Is anything known about this issue or can anybody help solving it? Many thanks in advance!

here's my code example:

final int AMOUNT = 20;

Model model = new Model("KEO");

int[] solving = new int[AMOUNT];

IntVar[] intVarArray = new IntVar[AMOUNT];

for (int i = 0; i < AMOUNT; i++) {
	intVarArray[i] = model.intVar("x" + i, 0, 440);
}

IntVar db = model.intVar("db", -100000, 100000);

// Entspraeche dem CSS
int[] COEFFS = new int[AMOUNT];

for (int i = 0; i < AMOUNT; i++) {
	COEFFS[i] = (int) (Math.random() * 100 * Math.pow(-1, i));
}

model.scalar(intVarArray, COEFFS, "=", db).post();

model.setObjective(Model.MAXIMIZE, db);

Solver solver = model.getSolver();

int counter = 0;
while (solver.solve()) {
	System.out.println(counter + ". Durchgang von solve()");
	counter++;
	for (int i = 0; i < AMOUNT; i++) {
		solving[i] = intVarArray[i].getValue();
	}
}

for (int i = 0; i < AMOUNT; i++) {
	System.out.println("Solving: " + solving[i] + " CSS: " + COEFFS[i]);
}
}

opened by Andreeew91 20

Refactor factories

There are many factories and finding the right element becomes difficult. To solve this issue, we propose to use the following factories:

Vars : to declare all variables (merges VF and VariableFactory) Cstrs : to declare all constraints (merges ICF, IntConstraintFactory, LCG, LogicalConstraintFactory, SCF, SetConstraintFactory) Search: to declare how to explore the search space (merges ISF, IntStrategyFactory, SSF, SetStrategyFactory, RSF, RealStrategyFactory, SearchMonitorFactory, SearchLoopFactory, LNSFactory)

opened by jgFages 19

Please publish the parent POM org.choco-solver:choco:4.10.3

Expected behavior

All choco dependencies can be resolved from Maven Central.

Actual behavior

Neither Gradle nor Maven are able to download org.choco-solver:choco-solver:4.10.3 because it Could not find artifact org.choco-solver:choco:pom:4.10.3 in central (https://repo.maven.apache.org/maven2). Gradle fails with:

> Could not resolve all files for configuration ':compileClasspath'.
   > Could not resolve org.choco-solver:choco-solver:4.10.3.
     Required by:
         project :
      > Could not resolve org.choco-solver:choco-solver:4.10.3.
         > Could not parse POM https://repo.maven.apache.org/maven2/org/choco-solver/choco-solver/4.10.3/choco-solver-4.10.3.pom
            > Could not find org.choco-solver:choco:4.10.3.
      > Could not resolve org.choco-solver:choco-solver:4.10.3.
         > Could not parse POM https://jcenter.bintray.com/org/choco-solver/choco-solver/4.10.3/choco-solver-4.10.3.pom
            > Could not find org.choco-solver:choco:4.10.3.

The POM of the 4.10.3 release contains an additional <parent> element which is not present in the 4.10.2 release:

POM 4.10.3: https://repo.maven.apache.org/maven2/org/choco-solver/choco-solver/4.10.3/choco-solver-4.10.3.pom
POM 4.10.2: https://repo.maven.apache.org/maven2/org/choco-solver/choco-solver/4.10.2/choco-solver-4.10.2.pom

Possible Solution

Steps to Reproduce (for bugs)

Maven:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>org.example</groupId>
    <artifactId>choco4-10-3-bug</artifactId>
    <version>1.0-SNAPSHOT</version>

    <dependencies>
        <dependency>
            <groupId>org.choco-solver</groupId>
            <artifactId>choco-solver</artifactId>
            <version>4.10.3</version>
        </dependency>
    </dependencies>
</project>

Perhaps you have to remove the choco files from your local .m2 to reproduce this issue.

Context

I've tried update from 4.10.2 to 4.10.3.

Environment

Choco-solver version: 4.10.3
Java version: 11.0.8

opened by thetric 18

Problem in resetting choco solver/model

Hi,

I am using choco solver 4. I am constructing a tree with choco model at each node. For some purpose I need to make multiple copies of the same tree having choco model. within nodes When I solve the first tree, by providing some constraints it gives me correct solution. However, for next tree, when I change the constraints, the solver does not provide the correct solution. How can I reset the solver as well as the complete model so that it can execute from the beginning?

I used solver.reset() but it does not work either.

opened by ritika2734 18

ICF.mod returns the wrong number of solutions

There still seems to be two issues with the current implementation in 3.3.1-SNAPSHOT develop branch. The following code will find many duplicate solutions.

public static void main(String[] args) {
    for (int i = 0; i < 1000; i++) {
        Solver s = new Solver();
        IntVar d = VF.enumerated("d", -4, 3, s);
        IntVar e = VF.enumerated("e", -1, 3, s);
        IntVar f = VF.enumerated("f", -1, 4, s);
        s.post(ICF.mod(d, e, f));
        s.set(ISF.random_value(s.retrieveIntVars(), System.currentTimeMillis()));
        Set<String> x = new HashSet<>();
        if (s.findSolution()) {
            do {
                String z = d.getValue() + " % " + e.getValue() + "  = " + f.getValue();
                if (!x.add(z)) {
                    System.out.println("Duplicate solution: " + z);
                }
            } while (s.nextSolution());
        }
    }
}

In the next example, the constraint is "(d % e = f) || (e = 0)". I expected at least one solution where "e = 0" but no solution is returned.

public static void main(String[] args) {
    Solver s = new Solver();
    IntVar d = VF.enumerated("d", new int[]{1, 2}, s);
    IntVar e = VF.enumerated("e", new int[]{0, 5}, s);
    IntVar f = VF.enumerated("f", new int[]{3, 4}, s);
    s.post(LCF.or(ICF.mod(d, e, f), ICF.arithm(e, "=", 0)));
    System.out.println(s.findSolution());
}

opened by JLiangWaterloo 17

[BUG] Set constraint `setLe` and `setLt` do not behave as expected

Describe the bug

The lexicographic ordering is applied to a boolean representation of the set, in the form: [b0, b1, b2, b3], where b0 is the lexicographically smallest possible number in the set (from UB) and b3 is the largest. For example, if we have a set variable s that takes its values in [ {}, {0, 1, 2, 3, 4} ], the value {1, 2} is represented as 01100.

The problem is that the lexical ordering of this representation is not equivalent to the lexicographic ordering of the sorted set elements. For example (with the same domain [ {}, {0, 1, 2, 3, 4} ]), if s1 = {4} and s2 = {3}, s1 > s2 according to the lexicographic ordering of the sorted set elements. But with the boolean representation we have: s1 = 00001 and s2 = 00010, thus s1 < s2.

Possible solution

One possible solution could be to reverse the boolean representation, with the previous example we would have:

s1 = {4} -> 10000 s2 = {3} -> 01000
bug

opened by dimitri-justeau 16
model.sum().post() not work

Model model = new Model("landing"); IntVar[][] y = model.intVarMatrix("runways", N, R, new int[]{0,1}); IntVar[] runways = ArrayUtils.flatten(y);

model.sum(y[i], "=", 1).post();

model.getSolver().solve();

then print y, all the value of y is 0, why?
support

opened by tao0708 14
Bump testng from 7.5 to 7.7.1
Bumps testng from 7.5 to 7.7.1.

Release notes

Sourced from testng's releases.

TestNG v7.7.1

What's Changed

Streamline overloaded assertion methods for Groovy by @krmahadevan in cbeust/testng#2858

Full Changelog: https://github.com/cbeust/testng/compare/7.7.0...7.7.1

TestNG v7.7.0

What's Changed

Replace FindBugs by SpotBugs by @gruenich in cbeust/testng#2781

Gradle: Drop forUseAtConfigurationTime() by @gruenich in cbeust/testng#2783

Added ability to provide custom message to assertThrows\expectThrows methods by @anatolyuzhakov in cbeust/testng#2793

Fix issue 2801 - Only resolve hostname once by @spkrka in cbeust/testng#2802

[SECURITY] Fix Zip Slip Vulnerability by @JLLeitschuh in cbeust/testng#2806

GITHUB-2807 - Failsafe buildStackTrace by @seregamorph in cbeust/testng#2808

Prevent overlogging of debug msgs in Graph impl by @krmahadevan in cbeust/testng#2813

Streamline dataprovider invoking in abstract classes by @krmahadevan in cbeust/testng#2814

Streamline TestResult due to expectedExceptions by @krmahadevan in cbeust/testng#2815

Unexpected test runs count with retry analyzer by @krmahadevan in cbeust/testng#2816

Make PackageUtils compliant with JPMS by @krmahadevan in cbeust/testng#2817

Ability to retry a data provider during failures by @krmahadevan in cbeust/testng#2820

Refactoring by @krmahadevan in cbeust/testng#2821

Fixing bug with DataProvider retry by @krmahadevan in cbeust/testng#2822

Add config key for callback discrepancy behavior by @krmahadevan in cbeust/testng#2823

Upgrading versions by @krmahadevan in cbeust/testng#2824

Fix #2770: FileAlreadyExistsException on copy by @melloware in cbeust/testng#2827

JarFileUtils.delete(File f) throw actual exception (instead of FileNotFound) when file cannot be deleted #2825 by @speedythesnail in cbeust/testng#2826

GITHUB-2830 - Failsafe parameter.toString by @seregamorph in cbeust/testng#2831

Changing assertion message of the osgitest by @krmahadevan in cbeust/testng#2832

hidden spotbugs in release #2829 by @bobshie in cbeust/testng#2833

Enhancing the Matrix by @krmahadevan in cbeust/testng#2834

Avoid Compilation errors on Semeru JDK flavour. by @krmahadevan in cbeust/testng#2835

Add addition yml extension by @speedythesnail in cbeust/testng#2837

Support getting dependencies info for a test by @krmahadevan in cbeust/testng#2839

Honour regex in dependsOnMethods by @krmahadevan in cbeust/testng#2838

Ensure All tests run all the time by @krmahadevan in cbeust/testng#2842

Deprecate support for running Spock Tests by @krmahadevan in cbeust/testng#2846

Streamline dependsOnMethods for configurations by @krmahadevan in cbeust/testng#2845

Ensure ITestContext available for JUnit4 tests by @krmahadevan in cbeust/testng#2848

Deprecate support for running JUnit tests by @krmahadevan in cbeust/testng#2849

New Contributors

@gruenich made their first contribution in cbeust/testng#2781

@anatolyuzhakov made their first contribution in cbeust/testng#2793

@spkrka made their first contribution in cbeust/testng#2802

@JLLeitschuh made their first contribution in cbeust/testng#2806

@seregamorph made their first contribution in cbeust/testng#2808

@melloware made their first contribution in cbeust/testng#2827

@speedythesnail made their first contribution in cbeust/testng#2826

... (truncated)

Changelog

Sourced from testng's changelog.

7.7.1 Fixed: GITHUB-2854: overloaded assertEquals methods do not work from Groovy (Krishnan Mahadevan)

7.7.0 Fixed: GITHUB-2852: [SECURITY] Fix Zip Slip Vulnerability (Jonathan Leitschuh) Fixed: GITHUB-2792: JUnitTestClass sets XmlTest as null when running JUnit 4 Tests using TestNG (Krishnan Mahadevan) Fixed: GITHUB-2847: Deprecate support for running JUnit tests (Krishnan Mahadevan) Fixed: GITHUB-2844: Deprecate support for running Spock Tests (Krishnan Mahadevan) Fixed: GITHUB-550: Weird @BeforeMethod and @AfterMethod behaviour with dependsOnMethods (Krishnan Mahadevan) Fixed: GITHUB-893: TestNG should provide an Api which allow to find all dependent of a specific test (Krishnan Mahadevan) New: Added .yml file extension for yaml suite files, previously only .yaml was allowed for yaml (Steven Jubb) Fixed: GITHUB-141: regular expression in "dependsOnMethods" does not work (Krishnan Mahadevan) Fixed: GITHUB-2770: FileAlreadyExistsException when report is generated (melloware) Fixed: GITHUB-2825: Programmatically Loading TestNG Suite from JAR File Fails to Delete Temporary Copy of Suite File (Steven Jubb) Fixed: GITHUB-2818: Add configuration key for callback discrepancy behavior (Krishnan Mahadevan) Fixed: GITHUB-2819: Ability to retry a data provider in case of failures (Krishnan Mahadevan) Fixed: GITHUB-2308: StringIndexOutOfBoundsException in findClassesInPackage - Surefire/Maven - JDK 11 fails (Krishnan Mahadevan) Fixed: GITHUB:2788: TestResult.isSuccess() is TRUE when test fails due to expectedExceptions (Krishnan Mahadevan) Fixed: GITHUB-2800: Running Test Classes with Inherited @Factory and @DataProvider Annotated Non-Static Methods Fail (Krishnan Mahadevan) New: Ability to provide custom error message for assertThrows\expectThrows methods (Anatolii Yuzhakov) Fixed: GITHUB-2780: Use SpotBugs instead of abandoned FindBugs Fixed: GITHUB-2801: JUnitReportReporter is too slow Fixed: GITHUB-2807: buildStackTrace should be fail-safe (Sergey Chernov) Fixed: GITHUB-2830: TestHTMLReporter parameter toString should be fail-safe (Sergey Chernov) Fixed: GITHUB-2798: Parallel executions coupled with retry analyzer results in duplicate retry analyzer instances being created (Krishnan Mahadevan)

7.6.1 Fixed: GITHUB-2761: Exception: ERROR java.nio.file.NoSuchFileException: /tmp/testngXmlPathInJar-15086412835569336174 (Krishnan Mahadevan) 7.6.0 Fixed: GITHUB-2741: Show fully qualified name of the test instead of just the function name for better readability of test output.(Krishnan Mahadevan) Fixed: GITHUB-2725: Honour custom attribute values in TestNG default reports (Krishnan Mahadevan) Fixed: GITHUB-2726: @AfterClass config method is executed for EACH @Test method when parallel == methods (Krishnan Mahadevan) Fixed: GITHUB-2752: TestListener is being lost when implenting both IClassListener and ITestListener (Krishnan Mahadevan) New: GITHUB-2724: DataProvider: possibility to unload dataprovider class, when done with it (Dzmitry Sankouski) Fixed: GITHUB-217: Configure TestNG to fail when there's a failure in data provider (Krishnan Mahadevan) Fixed: GITHUB-2743: SuiteRunner could not be initial by default Configuration (Nan Liang) Fixed: GITHUB-2729: beforeConfiguration() listener method should be invoked for skipped configurations as well(Nan Liang) Fixed: assertEqualsNoOrder for Collection and Iterators size check was missing (Adam Kaczmarek) Fixed: GITHUB-2709: Testnames not working together with suites in suite (Martin Aldrin) Fixed: GITHUB-2704: IHookable and IConfigurable callback discrepancy (Krishnan Mahadevan) Fixed: GITHUB-2637: Upgrade to JDK11 as the minimum JDK requirements (Krishnan Mahadevan) Fixed: GITHUB-2734: Keep the initial order of listeners (Andrei Solntsev) Fixed: GITHUB-2359: Testng @BeforeGroups is running in parallel with testcases in the group (Anton Velma) Fixed: Possible StringIndexOutOfBoundsException in XmlReporter (Anton Velma) Fixed: GITHUB-2754: @AfterGroups is executed for each "finished" group when it has multiple groups defined (Anton Velma)

Commits

b94395d Bump version to 7.7.1 for release

89dc584 Streamline overloaded assertion methods for Groovy

5ac0021 Adding release notes

c0e1e77 Adjust version reference in deprecation msgs.

011527d Bump version to 7.7.0 for release

7846c44 Deprecate support for running JUnit tests

8630a7e Ensure ITestContext available for JUnit4 tests

7070b02 Streamline dependsOnMethods for configurations

d7e0bb1 Deprecate support for running Spock Tests

ca7a3a2 Ensure All tests run all the time

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 0
Bump xchart from 3.8.2 to 3.8.3
Bumps xchart from 3.8.2 to 3.8.3.

Commits

ea7138f [maven-release-plugin] prepare release xchart-3.8.3

efacc0e prepare for 3.8.3 release

aa28b8c Merge branch 'develop' of github.com:timmolter/XChart into develop

3c9ef7e Merge pull request #705 from knowm/dependabot/maven/org.apache.maven.plugins-...

ea8afeb Bump maven-gpg-plugin from 1.6 to 3.0.1

759b4c3 junit ==> 5.9.1

1f31cce convert all unit tests to JUnit5, format code

826699f Merge branch 'develop' of github.com:timmolter/XChart into develop

dda1ba9 Merge pull request #711 from zhzzang/add-test

8a78d1c Merge branch 'develop' of github.com:timmolter/XChart into develop

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 0

Make possible to rewrite discrete expressions with rules

This pull request address makes it possible to define rewriting rules to transform an expression. One has to define one or more couples, each composed of a predicate (to detect a pattern) and a function (to transform the expression detected). Then a call to e.rewrite(...) transform in-place the expression.

I also (started to) define some pre-defined predicates and functions, like Rule.isOperator(...) and Rule.twoIdentical(...).

Basic example:

Model model = new Model("rewrite1");                                       
IntVar x = model.intVar("x", 0, 10);                                       
IntVar y = model.intVar("y", 0, 10);                                       
                                                                           
List<Rule<ArExpression>> rules = new ArrayList<>();                        
rules.add(new Rule<>(                                                      
        Rule.isOperator(ArExpression.Operator.ADD),                        
        Rule.twoIdentical(e -> e.mul(2))));                                
rules.add(new Rule<>(                                                      
        Rule.isOperator(ArExpression.Operator.SUB),                        
        Rule.twoIdentical(e -> model.intVar(0))));                         
                                                                           
ReExpression exp = x.add(x).eq(y.sub(y)).rewrite(rules);                                  
System.out.printf("%s\n", exp);

Related to: #979 #953 @arnaud-m if you want to play with the branch, you're welcome, this is a draft PR, waiting for feedbacks.

opened by cprudhom 0

[BUG] Incomplete bounding of expressions with products or powers
Describe the bug

The computation of bounds of the auxiliary variable is not accurate for mul or pow expressions. It raises an exception because it does not take into account the right member of the relation.

However, the constraint times does not meet the same issue.

To Reproduce

Define the model below.

Model m = new Model(); IntVar[] x = m.intVarArray("x", 3, 0, IntVar.MAX_INT_BOUND); model.times(x[0], x[1], x[2]).post(); // Valid and posted x[0].mul(x[1]).eq(x[2]).post(); // Valid, but raise an exception

The issue is also encountered with pow expression.

x[0].pow(x[1]).eq(x[2]).post(); // Valid, but raise an exception

Expected behavior No exception.
bug
opened by arnaud-m 1
Do not define unnecessary auxiliary variables
Is your feature request related to a problem? Please describe. Some auxiliary variables are introduced when building arithmetic and relational expressions. This are very useful allowing to easily define complex expressions. However, they are defined when not required.

Model m = new Model(); IntVar[] x = m.intVarArray("x", 3, 0, 1000); model.times(x[0], x[1], x[2]).post(); x[1].mul(x[1]).eq(x[2]).post(); // Introduce an unnecessary auxiliary variable. System.out.println(m);

Describe the solution you'd like Not creating the auxiliary variable mul_exp_1.

Describe alternatives you've considered The user can post a times constraint instead of defining an expression.
opened by arnaud-m 0
[BUG] Bounds are not checked on variable definition
Describe the bug The lower and upper bounds are not checked on variable definition.

To Reproduce Define a variable with invalid bounds.

m.intVar( 2 * IntVar.MIN_INT_BOUND, 2 * IntVar.MAX_INT_BOUND);

Expected behavior

I am unsure, but the behavior should depend on the nature of the variable : decision or auxiliary.

One can ask the user to bound decision variables.

However, auxiliary variables can be assigned large values even in a small search space. It is the case for a product or power constraints, or more generally arithmetic expressions.

For now, the practical issue is that the behavior is hard to predict. Some later checks can raise an exception, or not, when building a model with arithmetic expressions.
bug
opened by arnaud-m 6

Releases(v4.10.10)

v4.10.10(Oct 11, 2022)
4.10.10 - 11 Oct 2022

Major features:

Fix performance issue of ViewDeltaMonitor

Fix lack of filtering in STR2+ when domain is bounded

Fix issue relative to OR and AND in LogOp

Add missing checks in OneWordS32BitSet and OneWordS64BitSet + update constructors

Add new API to VariableUtils

Add CITATION.cff

Update paper.md

Other closed issues and pull requests:

See milestone 4.10.10

Contributors to this release:

Jean-Guillaume Fages (@jgFages)

Charles Prud'homme (@cprudhom)

Mehmet Hakan Satman (@jbytecode)

Full Changelog: https://github.com/chocoteam/choco-solver/compare/4.10.10...v4.10.10
Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.10-light.jar(5.62 MB)
choco-parsers-4.10.10-sources.jar(177.35 KB)
choco-parsers-4.10.10.jar(400.41 KB)
choco-solver-4.10.10-jar-with-dependencies.jar(10.32 MB)
choco-solver-4.10.10-sources.jar(1.27 MB)
choco-solver-4.10.10.jar(1.92 MB)
4.10.9(Aug 22, 2022)
4.10.9 - 22 Aug 2022

Major features:

It is now possible to declare hints to help the search finding a first solution. See solver.addHint(var, val).

Add Solver.tableSampling resolution policy which returns a stream of Solution randomly sampled.

Add increasing and decreasing constraints

Add costFlow constraint, which is composed of scalar products and a MinCostMaxFlow propagator

Revamp pow constraint

Add threshold for element with array of variables signature

Add a propagator for 0/1-knapsack (thanks to @PoltyPoltou)

Remove CPProfiler since the project is not active anymore.

Make possible to deal with large domains for some constraints (#894)

Add a LinearProgram class to deal with linear program (!) and a two-phase Simplex (not connected yet)

Fix bug related to delta in boolean views

Improvements relative to reified propagators

Change signature of AtLeastNValues

Record time to best in Measures(IMeasures measures) constructor

Change the way propagators are stored in variables to ease swapping (#889)

Each variable is in charge of scheduling its propagators. This impacts the way propagators are stored in a variable. Consequently, the getPropagators() and getPropagator(int) methods are deprecated, streamPropagators() replaces them. Unless otherwise stated, a propagator that can be entailed is automatically swapped in its variables' internal structure.

SetVar

Extend some black-box strategies to SetVar

Add union(SetVar unionSet, SetVar indices, SetVar[] sets) constraint

Add free strategy for SetVar (RegParser and ParallelPortfolio)

Fix SetVar#getDomainSize

Add SetDomainMax

Add 'setLe' and 'setLt' constraint (as a decomposition) in ISetConstraintFactory

Flatzinc, XCSP3 and MPS

Change default search of Flatzinc

Increase interval for Flatzinc unbounded intvar

Remove default ANSI in parsers

Update FZN grammar to deal with 'set of int'

Flatzinc: deal with warm_start

Add ignored search annotation warning in FGoal

Update XCSPParser + add model.amongDec

JAR Files

Since 4.10.9, a new jar file is available for download. This is a lighter version of the one with dependencies, namely choco-parsers-light-VERSION.jar. The following dependencies have been excluded from this archive:

org.apache.pdfbox:pdfbox

org.apache.fontbox:fontbox

com.ibm.icu:icu4j

This results in 82% smaller archive. Note that the non-alleged versions are still available for download.

Deprecated API (to be removed in next release):

IOutputFactory.outputSearchTreeToCPProfiler(boolean domain)

Other closed issues and pull requests:

See milestone 4.10.9

Contributors to this release:

Mathieu Vavrille (@MathieuVavrille)

Nicolas Pierre (@PoltyPoltou)

Charles Prud'homme (@cprudhom)

Jean-Guillaume Fages (@jgFages)

Arthur Godet (@ArthurGodet)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.9-jar-with-dependencies.jar(27.96 MB)
choco-parsers-4.10.9-light.jar(5.62 MB)
choco-parsers-4.10.9-sources.jar(177.35 KB)
choco-parsers-4.10.9.jar(392.24 KB)
choco-solver-4.10.9-jar-with-dependencies.jar(10.32 MB)
choco-solver-4.10.9-sources.jar(1.27 MB)
choco-solver-4.10.9.jar(1.92 MB)
4.10.8(Jan 10, 2022)
4.10.8 - 07 Jan 2022

Major features:

Propagation is now observable, solver.observePropagation(PropagationObserver). Consequently, it is now possible to profil the propagation by calling solver.profilePropagation(). See Javadoc for details and usages (#832).

Release 4.10.7 introduces a bug related to delta monitors, which is now fixed (#837).

Add new black-box strategy: failure based variable ordering heuristics (@lihb905)

Add model.streamVars() and model.streamCstrs()

Bounded domains checking for table constraints

Change complementary search in FlatZincParser

Bump XCSP3

Other closed issues and pull requests:

See milestone 4.10.8

Contributors to this release:

Jean-Guillaume Fages (@jgFages)

Fabien Hermenier (@fhermeni)

Hongbo Li (@lihb905)

Charles Prud'homme (@cprudhom)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.8-jar-with-dependencies.jar(28.48 MB)
choco-parsers-4.10.8-sources.jar(175.72 KB)
choco-parsers-4.10.8.jar(387.95 KB)
choco-solver-4.10.8-jar-with-dependencies.jar(10.85 MB)
choco-solver-4.10.8-sources.jar(1.23 MB)
choco-solver-4.10.8.jar(1.86 MB)
examples-4.10.8-src.tar.bz2(130.35 KB)
examples-4.10.8-src.tar.gz(139.05 KB)
examples-4.10.8-src.zip(185.12 KB)
4.10.7(Oct 11, 2021)
4.10.7 - 11 Oct 2021

Major features:

Simplify the way deltamonitors work. There is no need to freeze and unfreeze them before calling forEach... methods. But, a call to forEach... consumes all values stored.

Fix a bug related to incremental propagators, views and missing events.

STR2+ now deals with STAR tuples. Can be used when CT+ is not efficient (mainly due to very large domain size)

Resetting cutoff strategies now possible

Change restart behavior to reset cutoff on solutions (can be disabled though, calling solver.setRestarts(..) API).

Display occurrences of variable types and occurrences of propagator types

Now IntDomainBest offers API to break ties (see Search.ValH.BLAST for an example).

Add solver.defaultSolution() which creates lazily a solution recording everything, plugs it and returns it. This is helpful when a Solution object is required in many places.

Modification of the management of expressions in order to reduce the number of created variables (WIP).

Add IntVar.stream() that streams a variable's values (in increasing order)

Add Search.ValH.BMIN and Search.ValH.BLAST

Add DIMACS CNF parser (org.chocosolver.parser.mps.ChocoDIMACS)

Add Logger (solver.log()) to trace from Model/Solver.

Change some default settings

Revamp Settings, now is defined as a factory pattern + add Settings.dev() and Settings.prod() profiles.

Make half reification possible. Seed c.implies(b) or c.impliedBy(b) where c is a Constraint and b a BoolVar.

Update MiniZinc constraints definition + flatzinc files (for testing).

Update choco.msc (for MiniZinc IDE) + ./minizinc/README.md

Add Argmax and Argmin constraints

Add IfThenElse as a decomposed constraint

Improvement of solver.findParetoFront()

Deprecated API (to be removed in next release):

Other closed issues and pull requests:

See milestone 4.10.7

Contributors to this release:

Dimitri Justeau-Allaire (@dimitri-justeau)

Jean-Guillaume Fages (@jgFages)

Charles Prud'homme (@cprudhom)

Charles Vernerey (@chaver)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.7-jar-with-dependencies.jar(26.13 MB)
choco-parsers-4.10.7-sources.jar(173.69 KB)
choco-parsers-4.10.7.jar(382.03 KB)
choco-solver-4.10.7-jar-with-dependencies.jar(10.81 MB)
choco-solver-4.10.7-sources.jar(1.21 MB)
choco-solver-4.10.7.jar(1.81 MB)
examples-4.10.7-src.tar.bz2(129.91 KB)
examples-4.10.7-src.tar.gz(138.96 KB)
examples-4.10.7-src.zip(184.99 KB)
4.10.6(Dec 11, 2020)
4.10.6 - 11 Dec 2020

Major features:

Add new resolution helper in Solver, namely findOptimalSolutionWithBounds. See Javadoc for details and usages.

ParallelPortfolio now allows to add unreliable models, that is models whose resolution is deliberately made incomplete. These models should not stop the parallel resolution process when they no longer find a solution. Only complete models can inform the portfolio that they have proven the full exploration of the search space.

Add org.chocosolver.util.tools.PreProcessing class, and a first preprocessing rule: equalities detection

Upgrade ibex integration to support ibex-java v1.2.0. Fixes for issues #653 and #740.

Add QuickXPlain algorithm to find the Minimum Conflicting Set (see issue #509)

Update XCSP3 parser.

Fix InDomainMedian when domain size is even

Add new way to watch solving: solver.verboseSolving()

Deal with annotations for some Flatzinc constraints (allDifferent and inverse)

Add MultiArmedBandit strategy sequencer

Deprecated API (to be removed in next release):

Other closed issues and pull requests:

See milestone 4.10.6

Contributors to this release:

Charles Prud'homme (@cprudhom)

João Pedro Schmitt (@schmittjoaopedro)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.6-jar-with-dependencies.jar(25.58 MB)
choco-parsers-4.10.6-sources.jar(169.41 KB)
choco-parsers-4.10.6.jar(287.01 KB)
choco-solver-4.10.6-jar-with-dependencies.jar(10.43 MB)
choco-solver-4.10.6-sources.jar(1023.66 KB)
choco-solver-4.10.6.jar(1.47 MB)
examples-4.10.6-src.tar.bz2(124.95 KB)
examples-4.10.6-src.tar.gz(132.91 KB)
examples-4.10.6-src.zip(176.81 KB)
4.10.5(Oct 2, 2020)
4.10.5 - 02 Oct 2020

Major features:

add IN arithmetic int expression.

Deprecated API (to be removed in next release):

Settings.enableACOnTernarySum() removed

Settings.setEnableACOnTernarySum(boolean) removed

Other closed issues and pull requests:

See milestone 4.10.5

Contributors to this release:

Guillaume Le Louët (@glelouet)

Charles Prud'homme (@cprudhom)

João Pedro Schmitt (@schmittjoaopedro)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.5-jar-with-dependencies.jar(25.55 MB)
choco-parsers-4.10.5-sources.jar(169.24 KB)
choco-parsers-4.10.5.jar(285.98 KB)
choco-solver-4.10.5-jar-with-dependencies.jar(10.40 MB)
choco-solver-4.10.5-sources.jar(1003.37 KB)
choco-solver-4.10.5.jar(1.44 MB)
examples-4.10.5-src.tar.bz2(124.41 KB)
examples-4.10.5-src.tar.gz(132.78 KB)
examples-4.10.5-src.zip(176.81 KB)
4.10.4(Sep 9, 2020)
4.10.4 - 08 Sep 2020

Major features:

Change search strategies in ParallelPortfolio

Make "CT+" available to binary table constraint

Update Dockerfile, now automatically released in hub.docker.com

Migrate to ANTLR 4.8-1

Support nested seq_search in FlatZinc file

Add missing operations in model.unpost(c)

Add new constraint, named conditional, that posts constraints on condition

Merge cutoffseq in solver

Merge pf4cs in parsers

Remove geost from parsers

Deprecated API (to be removed in next release):

Other closed issues and pull requests:

#692, #698, #700, #702, #703, #704, #705

Contributors to this release

Dimitri Justeau-Allaire (dimitri-justeau)

João Pedro Schmitt (schmittjoaopedro)

Charles Prud'homme (cprudhom)

Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.4-jar-with-dependencies.jar(25.55 MB)
choco-parsers-4.10.4-sources.jar(168.62 KB)
choco-parsers-4.10.4.jar(284.09 KB)
choco-solver-4.10.4-jar-with-dependencies.jar(10.40 MB)
choco-solver-4.10.4-sources.jar(1000.58 KB)
choco-solver-4.10.4.jar(1.44 MB)
examples-4.10.4-src.tar.bz2(124.39 KB)
examples-4.10.4-src.tar.gz(132.76 KB)
examples-4.10.4-src.zip(176.79 KB)
4.10.3(Jul 3, 2020)
Multi-modules and JPMS-ready.

Major features:

Move cutoffseq, choco-sat, choco-solver, pf4cs, choco-parsers and samples projects into a (maven) multi-modules project

JPMS-ready

Choco-solver can now be run with either JDK 8 or JDK 9+.

Additions

Add Conflict History Search ("Conflict history based search for constraint satisfaction problem." Habetand Terrioux,SAC 19 (#676)

Add dom/wdeg with refinement ("Refining Constraint Weighting." Wattez et al. ICTAI 2019.)

Default AC algorithm for AllDifferent is now from IJCAI-18 "A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint", Zhang et al. (#644)

Add a pure java alternative to Ibex (#666)

LNS can now be defined with a solution as bootstrap.

Add simplify API for current Solver operations (#659)

Simplify code for the nValues constraint (using a watching/witnessing reasoning) (#674)

Replace former Bin Packing propagators by Paul Shaw propagator (#671)

Improving PropDiffN performance (#663)

Add nogood stealing for ParallelPortfolio (#669)

Adding of new constructors for Task objects (#662)

Removals

Remove JSON writer/parser (which was actually partially supported and not maintained) (#664)

Deprecated API (to be removed in next release):

Task(IntVar s, IntVar d, IntVar e, boolean declareMonitor)

AbstractProblem.readArgs(String... args)

Other closed issues and pull requests:

#617, #633, #637, #639, #645, #646, #647, #648, #658, #665, #667, #678, #682, #686, #689, #691
Source code(tar.gz)
Source code(zip)
choco-parsers-4.10.3-jar-with-dependencies.jar(25.71 MB)
choco-parsers-4.10.3.jar(283.60 KB)
choco-solver-4.10.3-jar-with-dependencies.jar(10.43 MB)
choco-solver-4.10.3-sources.jar(996.89 KB)
choco-solver-4.10.3.jar(1.44 MB)
examples-4.10.3-src.tar.bz2(124.48 KB)
examples-4.10.3-src.tar.gz(132.86 KB)
examples-4.10.3-src.zip(176.84 KB)
4.10.2(Oct 14, 2019)
Major features:

fix issues relative to propagation

change constraints' status checking

change stop conditions in ExplanationForSignedClause

add stable module name

Closed issues and pull requests:

#618
Source code(tar.gz)
Source code(zip)
choco-4.10.2.zip(17.65 MB)
4.10.1(Jun 26, 2019)
Major features:

LNS on other variables (e.g. SetVarLNS)

Continuous integration fixed

IntDomainMiddle now allows an external definition of what middle is, thanks to ToDoubleFunction<IntVar>

Add specific propagators for modulo

Add views of differences between solutions (see solver.printDistance(...) and solver.printDifferenceMatrix(...))

Deprecated API (to be removed in next release):

Closed issues and pull requests:

#538, #600, #611, #612, #613, #614, #615, #617, #619, #627, #630
Source code(tar.gz)
Source code(zip)
choco-4.10.1.zip(16.22 MB)
4.10.0(Dec 12, 2018)
This release comes with several major modifications. The most important one is related to explanations. The previous framework is replaced by a new one based on "A Proof-Producing CSP Solver", M.Vesler and O.Strichman, AAI'10.

See notebooks for an example of use.

Major features:

Update statistic dashboard (see solver.showDashboard())

Fix Settings.load on missing property

Fix issue in Cumulative simplified API

Add additional views model.intEqView(x,c), model.intNeView(x,c), model.intLeView(x,c) and model.intGeView(x,c)

Detect when the same views is created twice on the same pair <variable, value?>

Revamp the way LNS' neighbor is declared (simplication)

Add AbstractStrategy.remove() method to remove a declared strategy and its dependencies

Add new strategies to Search

Add new decomposition to IDecompositionFactory

Improve initialization of CT+ and CT*

Improve IntVar#isInstantiatedTo(int)

Deprecated API (to be removed in next release):

INeighbor interface is deprecated and replaced by Neighbor abstract class

INeighborFactory#explanationBased(IntVar...) is deprecated, no replacement.

ILearnFactory#setCBJLearning(boolean,boolean) and ILearnFactory#setDBTLearning(boolean,boolean) are deprecated, see ILearnFactory#setLearningSignedClauses() instead

Closed issues and pull requests:

#604, #605, #606
Source code(tar.gz)
Source code(zip)
choco-4.10.0.zip(17.54 MB)
4.0.9(Oct 30, 2018)
Minor release

Major features:

Offer possibility to store and load Settings from a property file.

Add API for cumulative when only starts are variable

Add decomposition of cumulative: model.cumulativeTimeDecomp(...)

Logical expression XOR manages more than 2 variables

Add new API to IOutputFactory (to Gephi and to Graphviz)

Add constraint network output (to gexf format), see solver.constraintNetworkToGephi(file)

add ParallelPortfolio.streamSolutions (#579)

Deprecated API (to be removed in next release):

Closed issues and pull requests:

#596, #600, #601, #602
Source code(tar.gz)
Source code(zip)
choco-4.0.9.zip(13.93 MB)
4.0.8(Jul 23, 2018)

Update DefaultSettings with right version
Source code(tar.gz)
Source code(zip)
choco-4.0.8.zip(13.14 MB)
4.0.7(Jul 19, 2018)
JAR file names have changed:

the suffix 'with-dependencies' disappears,

the suffix '-no-dep' (for no dependencies) appears.

This should intends to clarify the selection for new comers.

Add a PayPal button for donations.

Move to Ibex-2.6.5.

Major features:

Revamp Settings: no default method anymore, add setters. A concrete class DefaultSettings provides the default behavior.

IViewFactory.intScaleView now manages negative constants,

IViewFactory.intAffineView is now available

add new constraint for mixed linear equation (over real/int variables and double/int coefficients)

Dow/WDeg now manages variables in a bipartite set (instantiated variables are swaped)

Assert that a propagator that is passive is not allowed to filter anymore

An exception is thrown when a sum (or scalar) constraint is candidate for integer over/underflow (an alternative should be provided later)

BoolVar now handles modifications in different way (may impact performances)

Propagation engine has changed: no alternative to seven-queue one anymore + simplification of code (may impact performances)

add new relation expression ift(e1,e2)

Deprecated API (to be removed in next release):

Model.set(Settings) is deprecated. Now settings are declared in the Model constructor.

Settings.debugPropagation() is deprecated. There is no alternative.

Closed issues and pull requests:

#527, #564, #569, #576, #578, #581, #586
Source code(tar.gz)
Source code(zip)
choco-4.0.7.zip(13.14 MB)
4.0.6(Nov 23, 2017)
Move to Ibex-2.6.3.

Major features:

Ibex instance is no longer static, that offers better stability and reduce memory consumption when adding/removing functions. Reification no longer managed by Choco but delegated to Ibex.

Search.realVarSearch(...) offers possibility to define minimal range size, known as epsilon

Search.ibexSolving(model) let Ibex iterates over solutions once all integer variables are instantiated

add detection of min/max sub-cases

add simple dashboard in Swing to show resolution statistics, see solver.showDashboard()

Deprecated API (to be removed in next release):

IntEqRealConstraint will be removed in next release, Ibex managed this concept (int to real)

Model.getIbex() should not be used. A IbexHandler manages Ibex instances (one per model).

Closed issues and pull requests:

#558, #561, #565, #566, #568, #570
Source code(tar.gz)
Source code(zip)
choco-4.0.6.zip(12.84 MB)
4.0.5(Sep 28, 2017)
The current release was submitted to MiniZinc Challenge 2017 and at XCSP3 Competition 2017 and won medals.

choco-parsers provides utility to export a Model to JSON format and or import JSON data into a Model.

Major features:

Compact-Table now deals with short tuples (#531)

Checking if a created constraint is free (neither posted or reified) is now possible with Settings.checkDeclaredConstraints()

Improvements on BoolVarImpl and BoolNotView.

Remove code deprecated in last release.

Fix error in Views.

Add scalar detection in BiReExpression

fix errors in Impact-based Search

update Search.intVarSearch() + Search.defaultSearch(Model)

update ParallelPortfolio default strategies

Deprecated API (to be removed in next release):

Closed issues and pull requests:

fix bug in PropNogoods when dealing with negative values (impact solver..setNoGoodRecordingFromRestarts() and solver..setNoGoodRecordingFromSolutions(...))

fix bug in model.sum(...) and model.scalar(...) when dealing with arity greater than 100 and all operators except =

fix bug in model.table(...) with binary scope and universal value

fix bug related to Ibex and GC.

#531 ,#545, #546.
Source code(tar.gz)
Source code(zip)
choco-4.0.5.zip(12.50 MB)
4.0.4(Apr 28, 2017)
Major features:

add logical operator to expression (#520). Now it is possible, f-ex., to declare expression like: x.eq(y.add(1)).or(x.eq(y).and(x.eq(1)))

add new API to Solver to print features in a single line

enable ignoring passivate propagators when iterating over propagators of a modified variable (false by default; see Settings)

Deprecated API (to be removed in next release):

IPropagationEngine.fails(c,v,m) is replaced by Solver.throwsException(c,v,m) (#524)

IPropagationEngine.getContradictionException() is replaced by Solver.getContradictionException() (#524)

MathUtils.bounds(values) is replaced by a call to MathUtils.min(values) and MathUtils.max(values)

Remove dead code:

SparseSet

IFeatures, Features, IAttribute and Attribute

Closed issues and pull requests:

#516, #517, #518, #519, #520, #521, #524.
Source code(tar.gz)
Source code(zip)
choco-4.0.4.zip(12.47 MB)
4.0.3(Mar 31, 2017)
Major features:

arithm(IntVar,String,IntVar,String,int) and arithm(IntVar,String,IntVar,String,IntVar) manage '*' and '/'

add new APIs to ArrayUtils

fix error in PropBoolMin and PropBoolMax

Deprecated API:

Closed issues and pull requests:

#500, #502, #507, #510, #512, #514, #515.
Source code(tar.gz)
Source code(zip)
choco-4.0.3.zip(12.49 MB)
4.0.2(Jan 20, 2017)
4.0.2 - 20 Jan 2017

Major features:

restrict calls to Solver.setEngine(...) when propagation started. See javadoc for details.

remove global constructive disjunction, only local constructive disjunction is allowed.

add Solution.restore() to restore a solution (#354).

deep reset of Solver (#490, #491)

Deprecated API:

Solver.getState() (#485)

Measures.IN_SEC (related to #486)

Settings.outputWithANSIColors, IOutputFactory.ANSI_*

IMoveFactory.setLubyRestart(int, int, ICounter, int)

Closed issues and pull requests:

#468, #479, #480, #481, #484, #487, #488, #489, #492, #493, #494, #495, #496, #497, #499.
Source code(tar.gz)
Source code(zip)
choco-4.0.2.zip(12.23 MB)
choco-4.0.1(Dec 16, 2016)
This release is the continuation of 4.0.0.

upgrade CPProfiler monitor to communicate more information (see #458)

Fix issues:

#452 #455 #457 #458 #462 #463 #464 #465 #470 #471 #472 #473 #474 #476 #478
Source code(tar.gz)
Source code(zip)
choco-4.0.1.zip(12.79 MB)
choco-4.0.0(Sep 13, 2016)
This release is mainly dedicated to API migration. In the following, the major modifications are reported in order to ease code migration.

See also closed issues.

Even though we first wanted to provide an automatic script to help migration, we finally preferred to list the code modifications needed to move from 3 to 4. The documentation is up-to-date and may be a good starting point.

Note that most IDEs now provide helpful tools to help code migration.

At a glance

In order to distinguish resolution steps, Solver and SearchLoop now move to respectively Model and Solver.

Model aims at declaring a problem on the basis of variables and constraints, and replaces the dedicated factories.

Solver mainly focuses on the resolution of the declared problem, using less factories .

In details

Model

Variables

BoolVar

IntVar

SetVar

RealVar

Task

Views

Constraints

Refying

Clauses

Solver

Model

| v3.3.3 | v4.0.0 | | --- | --- | | Solver solver = new Solver("my problem"); | Model model = new Model("my problem"); |

BoolVar

Any BoolVar is now created thanks to model.boolVar(...) APIs.

| v3.3.3 | v4.0.0 | | --- | --- | | BoolVar x = VF.bool("X", solver); | BoolVar x = model.boolVar("X"); | | | BoolVar x = model.boolVar(); | | BoolVar[] xs = VF.boolArray("XS", 4, solver); | BoolVar[] xs = model.boolVar Array("XS", 4); | | BoolVar[] xs = VF.boolMatrix("XS", 3, 4, solver); | BoolVar[] xs = model.boolVar Matrix("XS", 3, 4); |

IntVar

Any IntVar is now created thanks to model.intVar(...) APIs.

integer

| v3.3.3 | v4.0.0 | | --- | --- | | IntVar x = VF.integer("X", 0, 10, solver); | IntVar x = model.intVar("X", 0, 10); | | | IntVar x = model.intVar(0, 10); | | IntVar[] xs = VF.integerArray("XS", 4, 0, 10, solver); | IntVar[] xs = model.intVarArray("XS", 4, 0, 10); | | IntVar[] xs = VF.integerMatrix("XS", 3, 4, 0, 10, solver); | IntVar[] xs = model.intVarMatrix("XS", 3, 4, 0, 10); |

When one wants to chose between bounded or enumerated, he/she has to set the bounded domain boolean.

bounded

| v3.3.3 | v4.0.0 | | --- | --- | | IntVar x = VF.bounded("X", 0, 10, solver); | IntVar x = model.intVar("X", 0, 10, true); | | | IntVar x = model.intVar(0, 10, true); | | IntVar[] xs = VF.boundedArray("XS", 4, 0, 10, solver); | IntVar[] xs = model.intVarArray("XS", 4, 0, 10, true); | | IntVar[] xs = VF.boundedMatrix("XS", 3, 4, 0, 10, solver); | IntVar[] xs = model.intVarMatrix("XS", 3, 4, 0, 10, true); |

enumerated

| v3.3.3 | v4.0.0 | | --- | --- | | IntVar x = VF.enumerated("X", 0, 10, solver); | IntVar x = model.intVar("X", 0, 10, false'); | | | IntVar x = model.intVar(0, 10, false'); | | IntVar x = VF.enumerated("X", new int[]{0,2,4}, solver); | IntVar x = model.intVar("X", new int[]{0,2,4}); | | | IntVar x = model.intVar(new int[]{0,2,4}); | | IntVar xs = VF.enumeratedArray("XS", 4, 0, 10, solver); | IntVar x = model.intVarArray("XS", 0, 10, false'); | | IntVar xs = VF.enumeratedArray("XS", 4, new int[]{0,2,4}, solver); | IntVar x = model.intVarArray("XS", new int[]{0,2,4}); | | IntVar xs = VF.enumeratedMatrix("XS", 3, 4, 0, 10, solver); | IntVar x = model.intVarMatrix("X", 3, 4, 0, 10, false'); | | IntVar xs = VF.enumeratedMatrix("XS", 3, 4, new int[]{0,2,4}, solver); | IntVar x = model.intVarMatrix("X", 3, 4, new int[]{0,2,4}); |

fixed

The way constants are declared does not depend on the type (fixed or variable) but on the kind (integer, set, ...).

| v3.3.3 | v4.0.0 | | --- | --- | | IntVar zero = VariableFactory.fixed(0, solver); | IntVar zero = model.intVar(0); | | IntVar zero = VariableFactory.fixed("0", 0, solver); | IntVar zero = model.intVar("0", 0); |

SetVar and RealVar

Similar modifications were applied to SetVar and RealVar declaration, e.g.:

| v3.3.3 | v4.0.0 | | --- | --- | | SetVar s = VariableFactory.set("S", new int[]{0,3}, new int[]{0, 1, 2, 3}, solver); | SetVar s = model.setVar("S", new int[]{0,3}, new int[]{0, 1, 2, 3}); | | RealVar r = VariableFactory.real("R", 0.1d, 2.2d, solver); | RealVar r = model.realVar("R", 0.1d, 2.2d); |

Task

A TaskVar now have to be created calling new Task(IntVar start, IntVar duration, IntVar end).

Views

Ways to create views evolved too, the signature are now :

model.intAbsView(IntVar),

model.intMinusView(IntVar),

model.intOffsetView(IntVar),

model.intScaleView(IntVar),

model.boolNotView(IntVar),

model.realIntView(IntVar)

Constraints

Constraints can be created thanks to a model. For example,

solver.post(IntConstraintFactory.alldifferent(xs));

now becomes:

model.post(model.allDifferent(xs));

or, in a more convenient way:

model.allDifferent(xs).post();

Most of the names and signatures remain the same between the two versions (but not all, see for instance alldifferent is now allDifferent).

Reifying

Nothing really change here, expect the way constraints are created:

BoolVar b = model.allDifferent(xs).reify();

Note that Model provides APIs like model.ifThenElse(Constraint, Constraint, Constraint).

Clauses

Model offers possibilities to directly add clauses to the clause-store, like model.addClauses***(...) where *** indicates the expression to turn into clauses.

Solver

SearchLoop now becomes Solver.

Solver solver = model.getSolver();

This class provides APIs to configure the search and the resolution process.

v3.3.3 APIs to solve problem, like solver.findSolution(). However, the returning value has changed, from boolean to Solution.

Solver now provides another API to solve a problem, named solve() which looks for a feasible solution. It can be called as long as it returns true. In that case, the resolution process stops on a solution state, which means that variables are instantiated and their domain can be read.

Printing solutions or resolution statistics is not done thanks to a factory anymore, but directly with the solver, e.g.: solver.showDecisions();

The same goes with measures, directly reachable from the solver, e.g: solver.getBackTrackCount();

Solver hasReachedLimit() moved to isStopCriterionMet() (since limit were renamed criterion so far, both method act similarly). Moreover, Solver.getState() which returns one of those states:

NEW: when the problem is established but the resolution has not been triggered yet ;

RUNNING: when the solver is searching for a solution ;

TERMINATED: the search ends normally, a solution is found or the entire search tree was explored without finding any solution ;

STOPPED : the search was stopped by a limit ;

KILLED : the resolution was killed from the outside (eg, thread interruption, JVM killed)

Solver's setters signatures have changed to be more accurate, e.g.: solver.set(mySearchStrategy) becomes solver.setSearch(mySearchStrategy)

IntSearchStrategy and similar were merged into Search, which provides widely used search strategies. Making dedicated combination of variable selector and value selector may imply to create object calling new instruction.

Closed issues

#427, #433, #438, #448, #450, #456
Source code(tar.gz)
Source code(zip)
choco-4.0.0.zip(13.01 MB)
4.0.0.a(Jun 13, 2016)

This is a pre-release of version 4.0.0. This version is about a deep refactoring of the API, on modeling part mainly, but not only.
Source code(tar.gz)
Source code(zip)
choco-4.0.0.a.zip(13.17 MB)
choco-3.3.3(Dec 22, 2015)
3.3.3 - 22 Dec 2015

All:

remove deprecated interfaces, classes and methods.

Solver:

add new APIs with an argument named restoreLastSolution which allow to indicate whether or not the last solution found, if any, should be restored on exit; Previous APIs (without the argument) restore the last solution by default (#354)

update javadoc (in particular: #347)

add default name to Solver + setter, modify measures printing to include the name.

SetVar toString implementation has changed

Explanations

refactor PropNogoods to deal with generalized no-goods

Bug fixes:

#346, #348, #349, #350, #351, #352, #353, #354, #355, #356, #357, #358, #359
Source code(tar.gz)
Source code(zip)
choco-3.3.3-j7.zip(14.35 MB)
choco-3.3.3.zip(14.28 MB)
choco-3.3.2(Nov 17, 2015)
3.3.2 - 17 Nov 2015

Solver:

ISolutionRecorder implementations do not restore automatically the last/best solution found on exit. This now has to be done calling either solver.restoreLastSolution() or solver.restoreSolution(Solution).

remove MasterSolver and SlaveSolver (#293)

Solver.duplicate(), Propagator.duplicate(Solver solver, THashMap<Object, Object> identitymap) and Variable.duplicate(Solver solver, THashMap<Object, Object> identitymap) has been removed. The expected way to duplicate a model is to create a method which creates a Solver, fills it with variables and contraints and returns it. Doing so, the models are sure to the same and reduces the risk of errors

add a search monitor helper for parallel resolution with Java8 lambda (#293)

lazy creation of ZERO, ONE, TRUE and FALSE through methods of Solver (#293)

refactor Solution (#306)

improve propagator iteration in propagation engine

revamp IMeasures to avoid declaring its concrete class as monitor

remove deprecated classes: GenerateAndTest, LastConflict_old

add new API to Solver to declare eagerly the objective variable(s) and the precision

enable printing decisions and solutions in ANSI colors (see Settings.outputWithANSIColors())

add connection to cp-profiler (#341)

Search:

Deeply revamp the search loop to offer more flexibility

SearchLoop.interrupt()is now forbidden

AbstractStrategy.init() cannot throw ContradictionException anymore but returns false instead

revamp decisions to enable IntMetaDecision

change Decision's API, getDecisionVariable() becomes getDecisionVariables()

move FastDecision to ../IntDecision

revamp IntDecision.toString()

set DecisionOperator as an interface (instead of an abstract class)

org.chocosolver.solver.search.limits.ICounter and its concrete class have been revisited, a Solver is now needed to create them.

Variables:

add IntVar.removeValues(IntIterableSet, ICause), IntVar.removeAllValuesBut(IntIterableSet, ICause) and IntVar.updateBounds(int, int, ICause) (#270)

improve IntVar.removeInterval(int, int, ICause) for enumerated domain integer variables

prevent the user from using ISF.random_value on bounded vars

Constraints:

add keysorting() constraint

add int_value_precede_chain() constraint

improve "DEFAULT" option for ICF.alldifferent()

revamp scalar and sum (#324)

fix lack of filtering in PropMin

simplify and improve basic element propagator (#325)

remove aCause from Propagator, should be replaced by this

simplify Propagation.contradiction(...)

add new setting to Settings to allow to not clone variables array input to Propagator's constructor

Propagator.getPropagationConditions() becomes public

Explanations:

deal with unary decision (when once is set to true)

add PoolManager for Rules and Propagators

explain PropCount_AC

fix lack of explanations in SatSolver

fix PropLessOrEqualXY_C to add the right rule

Bug fixes:

#152, #153, #164, #176, #296, #297, #298, #301, #303, #309, #311, #313, #314, #317, #320, #323, #326, #327, #331, #333, #334, #337, #338, #342
Source code(tar.gz)
Source code(zip)
choco-3.3.2-j7.zip(15.70 MB)
choco-3.3.2.zip(15.86 MB)
choco-3.3.1(May 11, 2015)
3.3.1 - 11 May 2015

Java 7 compliant jars are available in the choco-3.3.1-j7.zip file.

Change the default propagation engine (default is now SevenQueuesPropagatorEngine)

Add clause_channeling constraint

Remove IntVar.wipeOut(...)

Enable hot variable addition to propagator

Move nogood recording from solution and restart from constraint pkg to monitor +(revamp) + SMF API (#261)

Explanations are enabled on initial propagation (#247)

Improvement of the solution object (#254)

add DBT for explanations

Improve explanation engine

Add an additional "worldPush" instruction after initial propagation to be coherent with restarts (#55)

Remove restarts from ABS (#282)

one-shot decision are not reinitialized (#283)

Remove Propagation count (#284)

Change the default search strategy (#290)

Add possibility to complete the declared search strategy (#291)

Add new methods to Chatterbox (#292)

Bug fixes: #168, #221, #239, #259, #262, #264, #265, #267, #269, #271, #273, #275, #279, #281, #295
Source code(tar.gz)
Source code(zip)
choco-3.3.1-j7.zip(13.19 MB)
choco-3.3.1.zip(13.14 MB)
choco-3.3.0(Dec 4, 2014)
3.3.0 - 04 Dec 2014

Preparation to MCR (#248)

A script is available (move322to330.sh) to ease migration of your code.

Remove deprecated methods from Variable and SearchMonitorFactory.

Update User Guide (#226, #243, #245)

Add modifiable settings (#250)

Simplify search binder (#229)

All propagators of constraint factory allow duplication (#217)

Update license and header (#241)

Rollback to old release process (#246)

Change the default propagation engine (from SevenQueuesProapgatorEngine to TwoBucketPropagationEngine)

Bug fixes: #215, #252, #253, #255, #256, #258
Source code(tar.gz)
Source code(zip)
choco-3.3.0.zip(13.08 MB)
move322to330.sh(1.66 KB)
choco-3.2.2(Nov 17, 2014)
3.2.2 - 17 Nov 2014

Fix #240: add notmember(IntVar, SetVar) constraint (more efficient than not(member))

Fix #225: fix PropCostRegular, wrt to S.Demassey instructions.

Fix #229: create MasterSolver and SlaveSolver classes to deal with multi-thread resolution + add external configuration of the search strategy through a binder

Fix #227: deal with initial propagation

fix #230: update release script

fix #231: correct addTrue in SatFactory

fix #234: improve reification (presolve and less overheads). As a side effect, reification constraints are automatically posted and cannot be reified directly.

fix #233: remove java8 compliant code (temporary)

Add a MDD-based propagator (ICF.mddc).

fix #235: refactor logging fmwk. Add Chatterbox class as a unique entry point for messaging. Logging still relies on SLF4J.

fix #236: bug in SatSolver

Source code(tar.gz)
Source code(zip)
choco-3.2.2.zip(12.47 MB)
choco-3.2.1(Oct 13, 2014)
Graph vars externalized into choco-graph module (https://github.com/chocoteam/choco-graph)

Fix PropSymmetric (set vars)

Fix #206: fix lack of robustness in eucl_div

Better circuit constraint

incremental and coarse propagation of graph variable degrees

better samples for Hamiltonian cycle problems

NValue now split into atleast and atmost

fix LOGGER usage in parser (allows different levels of logging)

integer signature for the Lagrangian 1-tree relaxation constraint (good for solving the TSP)

Table constraint refactoring (STR2+) (seems to be not idempotent however)

Table reformulation of small scalar products

Minimum and Maximum over boolean arrays

Issue #215: Fix generation of relation based on tuples

Fix #214: Fix problems related to propagators dynamic addition and deletion

Add a GenerateAndTest search strategy which can be combined with others

Fix #218: return null when all variables are instantiated

Fix #219: fix range iterator of enumerated integer variable

Refactor IEventType (use interface and a concrete implementation for each variable type)

Fix bug in CoupleTable due to wrong range use

Issue #191: disable buildFakeHistory by default (add a condition to build fake history)

Space are not filtered anymore from Operator

Remove vars.clone() in Propagator constructor.

Remove DSLEngine and dependencies

Add a set constraint to get the set of values of an array of integer variables (SCF.int_values_union)

Source code(tar.gz)
Source code(zip)
choco-3.2.1.zip(8.41 MB)
choco-3.2.0(Aug 26, 2014)
Fix #148: update release script

Refactoring #149

Less Java Genericity:

Remove Delta type from Variable

Remove Propagator type from Constraints

Remove Variable type from views

StrategySequencer now created automatically

Strong constraints refactoring: A Constraint is defined as a set of propagators which can be reified

propagators must all be given to the super constructor

Remove IntConstraint

Remove many constraint classes

Remove isEntailed() from Constraint (isSatisfied does the job)

RealConstraint slightly changes

Move obsolete code to extra module

Associate variables with the solver in AbstractVariable super constructor

Unique ObjectiveManager (merge of IntObjectiveManager and RealObjectiveManager)

Default implementation of Propagator.getPropagationConditions(int vIdx) which reacts to all kinds of fine event.

Fix #146: a new propagation engine is now available which manages coarse propagations

Fix #159: avoid stackoverflow using GCC_fast

Fix #160: speed up count propagator

Fix #161: Propagator: fine_evt and default implementation of propagate(int,int)

Fix #162: update filtering algorithm of PropFivXYZ

Fix #163: Constraint#isSatisfied() handles stateless propagators

Fix #158 fix bug in PropMemberEnum

Fix #165: reset AbstractSearchLoop.decision on a call to reset()

Fix #152: manage dynamic (temporarily and permanently) addition of constraints

Fix #167: ObjectiveManager toString able to handle real values

new implementation of Among propagator

Fix #176: bug fixed in PropMin/PropMax

Fix #175: IMeasure objects can be cloned

Fix #182: Set propagators manage ISetDeltaMonitors

Fix #183: change release script

Fix #177-#179: add a ContradictionException to NoPropagatioEngine to handle with empty domain variables

Fix #173: modify default failure message in initial propagation

Fix #172: fix retriveXXXvars() + tests

Fix #171: define VF.MIN_INT_BOUND and VF.MAX_INT_BOUND

Fix #170: update dependencies

Fix #95-#186: simplify search strategies and enable tie breaking

Fix #187: patch Once

Fix #174: a default search strategy is now available, dealing with each type of variables present

Fix #189: Added methods to enumerate and store all optimal solutions

Fix #190: Entailment of PropBoolChannel

Fix #191: Enable dynamic addition of variables during the resolution (cf. Pareto)

Start documentation (see user_guide.pdf and http://chocoteam.github.io/choco3/)

NogoodFromRestart now trigger propagation fixpoint

Fix #192: NogoodFromSolution now available (only for integer variables)

Fix #193: VF.enumerated() now copies the input array of values

Strong refactoring of IntStrategyFactory (access to variable and value selectors, decision operators, and more simple to understand search names).

Stronger AtMostNValue constraint with automatic detection of disequalities

Fix #114: Enable to specify a time unit in time limits (ms, s, m or h)

Fix #195: fix bug while using IntViews over BoolVar

Fix #17: propagator annotations (PropAnn) have been removed

Fix #127: a specific view problem remains (new issue opened)

Fix #166: remove constants from default search strategy

Fix #196: fix view awakening problem

Views are now safe

Possibility to reformulate views with channeling constraints

Catch some particular cases of times in the factory

AC guaranteed for times(X,Y,Z) constraint when Y is a constant

Add path and subpath constraints, holding on integer variables

Add SORT constraint

Changes measure, times are now in second

Fix#199: some deltamonitors were desynchronized with delta

Source code(tar.gz)
Source code(zip)
choco-parser-3.2.0-jar-with-dependencies.jar(8.49 MB)
choco-samples-3.2.0-sources.jar(202.75 KB)
choco-solver-3.2.0-jar-with-dependencies.jar(4.97 MB)
user_guide-3.2.0.pdf(974.73 KB)