Code Monkey home page Code Monkey logo

jacop's Introduction

https://maven-badges.herokuapp.com/maven-central/org.jacop/jacop/badge.svg

[Maven Central] (https://maven-badges.herokuapp.com/maven-central/org.jacop/jacop/)

JaCoP

Java Constraint Programming (JaCoP) solver

JaCoP solver is Java-based open source solver developed and maintained mainly by two people

  • Krzysztof Kuchcinski, Dept. of Computer Science, Lund University, Sweden.
  • Radoslaw Szymanek - LeShop.ch, Switzerland.

Moreover a number of students have contributed to the solver by programming first versions of different global constraints and set constraints. The solver is being used in academia for research and teaching as well as in industry for commercial purposes. The most successful use of the solver is within Electronic Design Automation community, since both main authors come from that community.

JaCoP provides a significant number of constraints to facilitate modeling as well as modular design of search. This allows to tailor search to characteristics of the problem being addressed. It has currently more than 90,000 lines of code, not including examples and testing code. The examples which are the preferred way to document the abilities of JaCoP have more than 20.000 lines of code. The core developers have been working on JaCoP for past 10 years during their free time as a hobby activity. It has been refactored, transformed, and improved many times. Initial versions of JaCoP were even 3 orders of magnitude slower than the current version. JaCoP implementation has been influenced heavily by more than 20 research articles. Moreover, JaCoP was used as a tool to conduct experiments for CP publications. JaCoP supports finite domains of integers and sets of integers.

The major focus of JaCoP are its constraints. These constraints include rich set of primitive, logical, and conditional constraints as well as many global constraints. The most important global constraints are as follows.

  • diff2,
  • cumulative,
  • alldifferent,
  • gcc,
  • extensional support (with three different state-of-the-art approaches)and extensional conflict,
  • among,
  • element,
  • circuit,
  • knapsack,
  • regular,
  • netflow, and
  • geost.

JaCoP solver contains also front-end for FlatZinc language that makes it possible to execute MiniZinc models. It allows us to perform extensive testing with the help of other solvers as we can compare results from different solvers.

JaCoP is an ongoing activity. We are working on it in our free time. The most recent addition is Scala based DSL so it is easier to create your own constraint programs even in more intuitive manner.

JaCoP is also available from maven repository. For details, please check INSTALL file.

Contributions

We can only accept contributions (pull/merge requests) with signed Contributions License Agreement. Please read the document CLA_JaCoP in doc directory. Please use the checkstyle provided also in doc directory. Please make pull/merge requests only to develop branch. We do not accept other pull requests.

Installation Guide

The easiest way to make jar file for JaCoP is to use maven. First, install maven on your computer and then write

mvn install -DskipTests

The jar file will be generated into directory jacop/target.

Compilation of JaCoP can be easily done by issuing the following command

mvn compile

Generation of Java API documentation

mvn javadoc:javadoc

Generation of Scala formatted API documentation for Java and Scala

mvn scala:doc

Installation using Maven

To use JaCoP with maven you can just include it as a dependency in your pom.xml

<dependency>
    <groupId>org.jacop</groupId>
    <artifactId>jacop</artifactId>
    <version>4.7.0</version>
</dependency>

From the version 4.4.0, JaCoP is uploaded to Maven Central so the above is the only thing you need to do.

For older versions of JaCoP (4.3 and older) you also need to add the following information about CSLTH Maven repository to your pom.xml as well

<repositories>
	<repository>
		<id>CSLTH</id>
		<name>CS LTH maven repo</name>
		<releases>
			<enabled>true</enabled>
		</releases>
		<snapshots>
			<enabled>true</enabled>
			<updatePolicy>always</updatePolicy>
		</snapshots>
		<url>http://maven.cs.lth.se/content/repositories/public/</url>
	</repository>
</repositories>

Getting started

Probably the easiest way to start is to clone this repo. Afterwards, open the Maven project in IDE like Intelij IDEA and run examples available in directory $PATH_TO_GIT_REPO\src\main\java\org\jacop\examples.

Afterwards, you can copy parts of the provided examples into your own project add JaCoP maven dependency and start writing your own constraint programming examples.

LICENSE

It is provided in a separate file LICENSE.md. We can also provide JaCoP under different commercial license if open source license is not appropriate for your usage.

jacop's People

Contributors

cesarsotovalero avatar dagefoerde avatar dependabot[bot] avatar krzku avatar mariuszsw avatar radsz avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

jacop's Issues

AmongVar.impose() handles already grounded variables incorrectly

AmongVar.impose() initializes xGrounded to the number of X variables already grounded, but then calls super.impose(store), which itself calls AmongVar.queueVariable(), which again increments xGrounded for each singleton variable, resulting in each grounded variable being incorrectly counted twice.

Suggested bug fix: in AmongVar.impose(), initialize xGrounded to 0 (like is already done with yGrounded) instead of to the number of grounded variables.

Wrong solution

The following model finds one solution, A=B=C=10, but it is wrong.

include "globals.mzn";
var 6..6 union 10..10: A;
var 5..5 union 10..10: B;
var 7..7 union 10..10: C;
constraint
  minimum(8,[A,B,C]);

XneqY should not be consistent if X==Y

Consider the following minimal example:

x = new IntVar(store, 1, 100);
store.impose(new XneqY(x, x));

To the human reader, it is obvious that such a constraint cannot be satisfied. However, store.consistency() happily returns true, leaving x's domain intact. It might be sufficient to add a check for x != y to the consistency method in XneqY.

IntDomain question

Why the Integer domain is bounded to: ref Why specifically decided by 4?

[Integer.MIN_VALUE/4 + 2, Integer.MAX_VALUE/4 + 2]

And have you ever considered to use BigInteger type instead of normal integers?

NullPointerException in Knapsack.impose() on grounded variables that violate the knapsack capacity

The following code:

import org.jacop.constraints.knapsack.Knapsack;
import org.jacop.core.IntVar;
import org.jacop.core.Store;

public class JaCoPtest {

	public static void main(String[] args) {

		Store store = new Store ();
		
		IntVar v0 = new IntVar (store, "v0", 1, 1);
		IntVar v1 = new IntVar (store, "v1", 0, 0);
		IntVar v2 = new IntVar (store, "v2", 1, 1);
		IntVar v3 = new IntVar (store, "v3", 0, 0);
		IntVar v4 = new IntVar (store, "v4", 0, 0);
		
		Knapsack cons = new Knapsack (
				new int[] { 1, 2, 3 }, 
				new int[] { 1, 2, 3 }, 
				new IntVar[] {v1, v2, v3}, 
				v4, 
				v0);
		
		store.impose(cons);
	}

}

throws the following exception:

Exception in thread "main" java.lang.NullPointerException
	at org.jacop.constraints.knapsack.Knapsack.queueVariable(Knapsack.java:774)
	at org.jacop.constraints.Constraint.lambda$10(Constraint.java:190)
	at java.base/java.util.HashMap$KeySpliterator.forEachRemaining(HashMap.java:1605)
	at java.base/java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:658)
	at org.jacop.constraints.Constraint.impose(Constraint.java:190)
	at org.jacop.constraints.knapsack.Knapsack.impose(Knapsack.java:712)
	at org.jacop.core.Store.impose(Store.java:727)
	at JaCoPtest.main(JaCoPtest.java:52)

Incorrect set_le / set_lt implementation

We were made aware aware by a MiniZinc user that set_le and set_lt are working incorrectly within the JaCoP solver: MiniZinc/libminizinc#185

The following FlatZinc model returns incorrectly as unsatisfiable:

var set of 1..10: a ::output_var = {8};
var set of 1..10: b ::output_var = {7, 8, 9};

constraint set_le(a, b);

solve  satisfy;

Similarly for constraint set_lt(a, b);

MagicSeries, Among, two solutions?

When modeling the MagicSeries questions using Among JaCoP returns two solutions. However, it should only be one. Solution 2 seems to be wrong as the 1 appears twice.

Solution 1: 6 2 1 0 0 0 1 0 0 0 
Solution 2: 7 1 0 0 0 0 0 1 0 0 

Sample Code run with JaCoP 4.1 as well as 3.2

    int n = 9;
    Store store = new Store();
    IntVar[] vars = new IntVar[n+1];
    for (int i=0; i < vars.length; i++) {
        vars[i] = new IntVar(store, "H"+i, 0, n);
    }
    for (int i=0; i < vars.length; i++) {
        store.impose(new Among(vars, new IntervalDomain(i, i), vars[i]));
    }
    Search<IntVar> search = new DepthFirstSearch<IntVar>();
    search.setPrintInfo(false);
    SelectChoicePoint<IntVar> select =
        new InputOrderSelect<IntVar>(store, vars, 
                                     new IndomainMin<IntVar>());
    search.getSolutionListener().searchAll(true);
    search.getSolutionListener().recordSolutions(true);
    search.labeling(store, select);
    int numSolutions = search.getSolutionListener().solutionsNo();
    for (int i=1; i <= numSolutions; i++) { 
        System.out.print("Solution " + i + ": "); 
        for (int j=0; j<search.getSolution(i).length; j++) 
            System.out.print(search.getSolution(i)[j] + " "); 
        System.out.println(); 
    } 

Change request to signatures of Decreasing & Increasing constructors

Please change the signature of the Decreasing constructor from

public Decreasing(List<IntVar> x)

to

public Decreasing(List<? extends IntVar> x)

This would make it possible to use the Decreasing constraint with variables that are expressed as subclasses of IntVar.

The same applies to the following constructors:

public Decreasing(List<IntVar> x, boolean strict)
public Increasing(List<IntVar> x)
public Increasing(List<IntVar> x, boolean strict)

Flatzinc : maximize a function

Hi, for a project I need to simply maximize a function with boolean variable and i need only the better solution. Is there any way to print only the best solution on the standard output or modify the code in a precise place ti do that ?

I use the following example (in Minizinc) and I convert it to Flatzinc with the mzn2fzn program :

var bool : U2_1;
var bool : U2_2;
var int : obj_function;
constraint U2_2 + U2_1 <= 1;
constraint obj_function = 5 + 3 * U2_1 + 2 * U2_2 + 9;
solve maximize obj_function;
output [
"\nValue of objective function : ",show(obj_function)
,"\nU2_1 \t ", show(U2_1)
,"\nU2_2 \t ", show(U2_2)
];

SoftAllDifferent and SoftGCC incorrectly throw AssertionErrors on infeasible stores

The following code:

Store store = new Store ();
		
// Create the variables
IntVar cost = new IntVar (store, "cost", 0, 2);
IntVar[] vars = new IntVar [2];
vars[0] = new IntVar (store, "v_0", 0, 1);
vars[1] = new IntVar (store, "v_1", 0, 1);

// Ground the variables using In constraints, such that the store is infeasible
store.impose(new In (cost, new IntervalDomain (0, 0)));
store.impose(new In (vars[0], new IntervalDomain (0, 0)));
store.impose(new In (vars[1], new IntervalDomain (0, 0)));
		
// Impose a SoftAlldifferent constraint
store.imposeDecomposition(new SoftAlldifferent (vars, cost, ViolationMeasure.DECOMPOSITION_BASED));
		
System.out.println(store.consistency());

throws

Exception in thread "main" java.lang.AssertionError: non-optimal arcs:
[1->sink, flow=0/1  reduced=-1, index=2]
	at org.jacop.constraints.netflow.Assert.checkOptimality(Assert.java:269)
	at org.jacop.constraints.netflow.simplex.NetworkSimplex.networkSimplex(NetworkSimplex.java:368)
	at org.jacop.constraints.netflow.NetworkFlow.consistency(NetworkFlow.java:255)
	at org.jacop.core.Store.consistency(Store.java:547)

when asserts are enabled.

Installation problem

Hello,

I'm not a Java nor a Scala programmer and I don't understand the error messages.
All I want to do is to plug JaCoP into MiniZinc.
I followed the installation instruction, but no jar file was generated. Instead, I got the following.
On Ubuntu 22.04.2 LTS.

$ mvn install -DskipTests
[...]
[INFO] Compiling 30 source files to /home/matsc/jacop/target/classes at 1687265947919
[WARNING] /home/matsc/jacop/src/main/scala/org/jacop/scala/jacop.scala:125: warning: procedure syntax is deprecated for constructors: add `=`, as in method definition
[INFO]   def this(min: Int, max: Int) {
[INFO]                               ^
[WARNING] /home/matsc/jacop/src/main/scala/org/jacop/scala/jacop.scala:136: warning: procedure syntax is deprecated for constructors: add `=`, as in method definition
[INFO]   def this(el: Int) {
[INFO]                    ^
[WARNING] /home/matsc/jacop/src/main/scala/org/jacop/scala/jacop.scala:1520: warning: procedure syntax is deprecated for constructors: add `=`, as in method definition
[INFO]   def this(n: Int) {
[INFO]                   ^
[WARNING] 3 warnings
[INFO] prepare-compile in 0 s
[INFO] compile in 9 s
[INFO] 
[INFO] --- maven-jdeps-plugin:3.0.0:jdkinternals (default) @ jacop ---
[INFO] ------------------------------------------------------------------------
[INFO] BUILD FAILURE
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  27.958 s
[INFO] Finished at: 2023-06-20T14:59:17+02:00
[INFO] ------------------------------------------------------------------------
[ERROR] Failed to execute goal org.apache.maven.plugins:maven-jdeps-plugin:3.0.0:jdkinternals (default) on project jacop: Unable to find jdeps command: The environment variable JAVA_HOME is not correctly set. -> [Help 1]
[ERROR] 
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR] 
[ERROR] For more information about the errors and possible solutions, please read the following articles:
[ERROR] [Help 1] http://cwiki.apache.org/confluence/display/MAVEN/MojoFailureException

ArrayIndexOutOfBoundsException thrown by ExtensionalConflictVA.consistency() on grounded variables

The following code:

import org.jacop.constraints.ExtensionalConflictVA;
import org.jacop.core.IntVar;
import org.jacop.core.Store;

public class JaCoPtest {

	public static void main(String[] args) {
		
		Store store = new Store ();
		
		IntVar v1 = new IntVar (store, "v1", 0, 0);
		IntVar v2 = new IntVar (store, "v2", 1, 1);
				
		ExtensionalConflictVA cons = new ExtensionalConflictVA (
				new IntVar[] { v1, v2 }, 
				new int[][] {
					new int[] {0, 0},
					}
				);
		
		store.impose(cons);
		
		System.out.println(store);
		
		store.consistency();
	}
}

displays the following store:

*** Store
v1 = 0
v2 = 1

*** Constraints for evaluation:
{SimpleHashSet[ExtensionalConflictVA1(v1 = 0 v2 = 1)]
SimpleHashSet[]
SimpleHashSet[]
SimpleHashSet[]
SimpleHashSet[]
 }

and then throws the following exception:

Exception in thread main java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
	at org.jacop.constraints.ExtensionalConflictVA.findPosition(ExtensionalConflictVA.java:426)
	at org.jacop.constraints.ExtensionalConflictVA.seekSupportVA(ExtensionalConflictVA.java:161)
	at org.jacop.constraints.ExtensionalConflictVA.consistency(ExtensionalConflictVA.java:378)
	at org.jacop.core.Store.consistency(Store.java:525)
	at JaCoPtest.main(JaCoPtest.java:25)

Minimize Makespan

Hi I'd like to use jacop for a scheduling thesis project.
Until now I used Minizinc which unfortunately has a major performance weaknesses.

Is there any way to minimize the make span (maximum start day of a task + its duration) as minimizing the start days does not give the best solution?
I use a matrix of IntVars to represent the start days [task, floor], durations are stored in int matrix

Kind regards
Andreas Vieider

Performance degradation in JaCoP 4.5 vs 4.4

Hi,

I'm using JaCoP in my FRODO Distributed Constraint Optimization library, and when I run performance regression tests after upgrading the JaCoP dependency to Version 4.5.0, I notice that performance degraded from 4.4 to 4.5. I'm seeing a 250 to 500 ms overhead across the board.

Are you aware of performance inefficiencies that might have been introduced in Version 4.5? Do you maybe even have a workaround to recommend?

Thanks in advance for your insights.

Thomas

Infinite recursion in DepthFirstSearch

In some situations, I'm having the problem that DepthFirstSearch causes a StackOverflowError due to an infinite recursion:

Exception in thread "main" java.lang.StackOverflowError
    at org.jacop.search.DepthFirstSearch.label(DepthFirstSearch.java:559)
    at org.jacop.search.DepthFirstSearch.label(DepthFirstSearch.java:765)
    at org.jacop.search.DepthFirstSearch.label(DepthFirstSearch.java:765)
    at org.jacop.search.DepthFirstSearch.label(DepthFirstSearch.java:765)
    // and so on...

I'd like to debug this, to find out whether this is a problem with my own code or a bug in JaCoP, but I don't know what information is useful to you. If you could guide me with this, that'd be great!

Edit: This is on JaCoP 4.3.0, as provided in the Maven repository (see #12).

Or/Linear

Linear constraints are ignored when they appear under an Or. E.g: X = 0 / X = 1 is consistent with X = 2!

package bug;

import org.jacop.core.;
import org.jacop.constraints.
;
import org.jacop.search.*;

public class Jacop {
public static void main(String[] args) {
Store store = new Store();
IntVar X = new IntVar(store, "X", 0, 2);
IntVar[] list = {X};
int[] weight = {1};
PrimitiveConstraint Xeq0 = new Linear(store, list, weight, "=", 0);
PrimitiveConstraint Xeq1 = new Linear(store, list, weight, "=", 1);
PrimitiveConstraint Xeq2 = new Linear(store, list, weight, "=", 2);
/* // The following constraints are equivalent to the previous ones, and work correctly.
PrimitiveConstraint Xeq0 = new XeqC(X, 0);
PrimitiveConstraint Xeq1 = new XeqC(X, 1);
PrimitiveConstraint Xeq2 = new XeqC(X, 2);
*/
store.impose(new Or(Xeq0, Xeq1));
store.impose(Xeq2);
if (!store.consistency()) {
System.out.println("inconsistent => ok!");
System.exit(0);
}
DepthFirstSearch dfs = new DepthFirstSearch<>();
SelectChoicePoint select =
new InputOrderSelect<>(store, list, new IndomainMin());
if (!dfs.labeling(store, select)) {
System.out.println("search inconsistent => ok!");
System.exit(0);
}
System.out.println("inconsistency undiscovered => oops!");
System.exit(1);
}
}

Error instead of solution

This is a continuation of #58 , which apparently wasn't quite fixed.

The following model has two solutions, but an exception is thrown:

include "globals.mzn";
var 1..2: B1;
var 1..2: B2;
var 0..6: D;
constraint
    bin_packing_load([D,D],[B1,B2],[3,3]);

fzn-jacop, geost_smallest_bb, missing solutions

The following model has two solutions, A=4, E=2, A = E = 4, but JaCoP misses them.

include "globals.mzn";
var 2..2 union 4..4: A;
var 2..2 union 4..4: E;
constraint
    geost_smallest_bb(2,
                      [|3, 1, |2, 1, |3, 3, |3, 1, |],
                      [|3, 1, |0, 0, |0, 3, |3, 2, |],
                      [{1},{2},{3},{4}],
                      [|E, 2, |4, 4, |4, 4, |A, A, |],
                      [1,2,3,4],
                      [4,3],
                      [10,10]);

Element constraint sets incorrect `index` value.

Using JaCop 4.6.0 on Java.

The following code snippet showcases an example where jacop's element constraint yields an incorrect result. This issue might be related to #27, but I don't believe so. This is why I created this second issue for you to track.

Store cp = new Store();

IntVar   index = new IntVar(cp, -3, 3);
IntVar[]  vars = new IntVar[]{new IntVar(cp, 0, 0)};
IntVar   value = new IntVar(cp, -4, 2);

cp.setLevel(cp.level + 1);
cp.impose(Element.choose(index, vars, value));
if ( !cp.consistency() ) {
    System.err.println("Ahem, this is wrong !");
}

// This is what gets printed:
// index = _1 = 1
// vars  = [_2 = 0]
// value = _3 = 0
System.out.println("index = "+ index);
System.out.println("vars  = "+ Arrays.toString(vars));
System.out.println("value = "+ value);

// 1st assertion fails because index = {1}. Still vars[1] is not feasible : it is out of bounds
assert index.value()   == 0;
assert vars[0].value() == 0;
assert value.value()   == 0;

Empty list in search annotation raises error

An annotation like:

solve :: int_search([], occurrence, indomain_min, complete) satisfy;                                                           

raises an error. An empty list can easily arise as the result of a list comprehension that depends in instance data.

Maven repository

As far as I can see, there is not "official" maven repository of JaCoP, but this one:

<dependency>
    <groupId>de.sciss</groupId>
    <artifactId>jacop</artifactId>
    <version>3.4.0</version>
</dependency>

See http://mvnrepository.com/artifact/de.sciss/jacop.

Could you place your library into maven, please?

Thanks for your work ๐Ÿ‘

Wrong solution

The following model gives two solutions:

  • A=1, B=C=D=2
  • A=1, B=3, C=D=2

The second solution is wrong.

include "globals.mzn";
var 1..1 union 4..4: A;
var 2..3 union 5..5: B;
var 2..2 union 4..4 union 6..6: C;
var 2..2 union 4..4: D;
constraint
  maximum(B,[2,D,A,C]);
solve :: int_search([A,B,C,D], input_order, indomain_min, complete) satisfy;

Please make Arithmetic's fields protected instead of private

Hi,

Can you please make the following fields of the Arithmetic constraint protected instead of private? I would like to subclass this class but not having access to these fields makes it impossible.

    private List<int[]> eqns;
    private List<IntVar> vars;
    private Map<IntVar, Integer> map;

Thanks in advance!

Can't compile repo

Hi , when I try to compile the git hub repo, I get lots of errors like these:

  • ASTSolveItem cannot be resolved to a type Solve.java /jacop/src/main/java/org/jacop/fz line 126 Java Problem
  • JJTANNEXPR cannot be resolved to a variable SearchItem.java /jacop/src/main/java/org/jacop/fz line 119 Java Problem

These types seem indeed to be mssing in the repo.

There are other problems related to warning settings:

  • The field Diff2.xmlAttributes is hiding a field from type Diff Diff2.java /jacop/src/main/java/org/jacop/constraints line 67 Java Problem
  • override annotation missing

Although I could change my settings in eclipse to get rid of these, I wonder if it would not be better to fix these problems in the repo/source since they reflect recommended programming guidelines

Thanks for this great work !

Missing line return in AmongVar.toString()

There is a minor issue in AmongVar.toString(), which is missing a line return before printing the first X variable:

StringBuffer result = new StringBuffer(id());

should be replaced with

StringBuffer result = new StringBuffer(id()).append("\n");

Scala Wrapper Model parameter

I had modified the Scala wrappers from the last SF version which is at e4c5a6c - with a similar idea to what you did in f287128 , namely to allow for different models within one application run.

My approach is slightly different, instead of having a global mutable model field, I am using an implicit model parameter:

https://github.com/iem-projects/PointLib/blob/composer_ot/src/main/scala/de/sciss/jacop/jacop.scala

I think this is more elegant, but of course it's a matter of taste. Let me know if you are interested in that version, then I could fork jacop, make that change and start a pull request.

Update doc please.

Radoslaw Szymanek does not seams to work (for|at|with) Crossing-Tech, Switzerland any more.
Please update.

geost.ObstacleObjectFrame.timeOnlyCheck() should throw FailExceptions instead of using asserts

geost.ObstacleObjectFrame.timeOnlyCheck() contains two asserts:

                assert
                    obstacle.start.min() + obstacle.duration.min() <= obstacle.end.min() :
                    "time constraint not valid: " + obstacle.start + " + " + obstacle.duration + " <= " + obstacle.end;

and

                assert obstacle.start.min() + obstacle.duration.min() <= obstacle.end.min();

which should instead be replaced by:

                if (obstacle.start.min() + obstacle.duration.min() > obstacle.end.min()) 
                	throw Store.failException;

fzn-jacop, maximum_arg, wrong solution

The following model has three solutions,

[B,E] = [5, 1]
[B,E] = [6, 1]
[B,E] = [7, 1]

but JaCoP finds another, wrong, solution,

[B,E] = [6, 2]
include "globals.mzn";
var 5..7: B;
var 1..2: E;
constraint maximum_arg([B,B,5,1,1],E);
output ["[B,E] = \([B,E])\n"];

Floating point precision not always respected

Take the following example:

FloatDomain.setPrecision(1e-100);
Store store = new Store();

    FloatVar x = new FloatVar(store, "x", -100.00f, 100.00f);
    FloatVar[] vars = new FloatVar[]{x};
    store.impose(new PgtC(x, 1.00f));

    DepthFirstSearch<FloatVar> search = new DepthFirstSearch<FloatVar>();
    SplitSelectFloat<FloatVar> s = new SplitSelectFloat<FloatVar>(store, vars, null);
    search.setSolutionListener(new PrintOutListener<FloatVar>());
    search.getSolutionListener().searchAll(false);
    search.labeling(store, s);`

The output is:
x=1.0000000000000004000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Great. My simple constraint is being respected, although not in a very useful way.

When I try to reduce the precision:
FloatDomain.setPrecision(1e-5);

The output is now:
x=1.00000

This is clearly not respecting the constraint.

Am I doing something wrong?

4.6 :`RegularExpressionParser` is broken

Concerns : JaCoP 4.6 (Java 11).

I spotted a few issues in the code of the RegularExpressionParser class introduced in 4.6.

  • (this one is fixed in the enclosed patched file) the class is unusable since the result of lexer.nextToken() is never used. As a consequence of that, any call to parse yields 'null'.
  • The dot notation parsing is flaky. For instance, the following two examples relate toi the handling of epsilon expressions but are not orthogonal to one another.
// Prints "null.(32)*"
System.out.println(new PatchedRegexParser(new StringReader("(.32*)")).parse(false));

// Warns of a syntax error then prints "32.(null).*"
System.out.println(new PatchedRegexParser(new StringReader("(32.*)")).parse(false));
  • In some cases (ie when a dot is missing) the parser silently drops a whole portion of the text to parse. For example, consider the following example:
// Prints "(17)*.23" and nothing more.
System.out.println(new PatchedRegexParser(new StringReader("(32.14*)17*.23")).parse(false));

Btw, I wonder if reusing the . and + symbols for summation and concatenation was judicious. Indeed, these symbols have different meaning in POSIX-style regexes (and I assume most people would expect that meaning)

PatchedRegexParser.java.txt

Geost.groundedVars not emptied when Level 1 is removed

There is a bug in Geost.impose(), which initializes lastLevelLastVar to 0, but it should initialize it to -1 instead.

lastLevelLastVar.update(-1);

As a result of this bug, the list groundedVars is not correctly emptied when the first level at which a variable gets grounded is removed upon backtracking.

Error instead of solution

The following model should succeed with X = 1, but raises an error.

include "globals.mzn";
var 1..2: X;
constraint
    bin_packing_load([1, 0, 0],[X],[1]);

XneqC constraints are dropped silently

JaCoP 4.6.0

When an XneqC constraint is imposed on an IntVar with a BoundDomain, it can happen that the constraint is ignored and dropped, i.e. not considered in later consistency checks. This does not happen right away, but on the first consistency check.

Observed behaviour
Consider an IntVar x with a BoundDomain in {-500; 500}. Now impose XneqC(x, 0). The first check of consistency brings us here

@Override public void consistency(final Store store) {
x.domain.inComplement(store.level, x, c);

which delegates to

@Override public void inComplement(int storeLevel, Var var, int complement) {
if (this.max == this.min && this.max == complement)
throw failException;
// Can not be removed without changing the code below.
if (complement != this.min && complement != this.max)
return;

which disregards the complement and just leaves the domain unchanged; but to make things worse, the XneqC is also never considered on later changes to X. It seems that the constraint is dropped.

Expected behaviour
Modify the BoundDomain, or keep consulting the constraint when changes to the domain of X are made later. If all else fails, give a clear indication (runtime exception?) about the fact that this operation has failed.

Workaround
Use an IntervalDomain instead of the BoundDomain โ€“ this circumvents the described problem, but I am not sure about the effect on other operations...

Infeasible LinearInt constraints on singleton variables are not imposed

Hi,

If you create a new LinearInt constraint by passing it a list of singleton variables that do not add up to the right-hand-side constant, then the constraint is incorrectly not imposed, and the store incorrectly claims to be consistent.

The issue is in commonInitialization(), which collapses all singleton variables into the right-hand-side constant b, which can result in the list of variables x becoming empty, and then impose() returns without imposing the constraint, even though it is violated because b != 0.

Best,

Thomas

Git tags for releases

Could you please publish git tags for releases? They seem to be missing for all releases except 4.0.0.

This would be helpful for me since I use JaCoP to test and benchmark ExtendJ, and I'd like to test it on all released versions of JaCoP.

System.out.println instead of slf4j

Problem:
In several classes (DepthFirstSearch for instance), log is done through System.out.println instead of slf4j.
=> logging cannot be disabled nor controlled.

Solution:
Use slf4j (already in dependency) to log.
The usability would be greatly enhanced. Thanks !

Consistency of element constraint is sometimes incorrect.

Using JaCop 4.6.0 on Java.

The following code snippet illustrates a case where the element constraint gives an incorrect result:

// Step1: Create the store + variables
Store cp = new Store();

IntVar   index = new IntVar(cp, 0, 4);
IntVar[]  vars = new IntVar[]{new IntVar(cp, -4, 4)};
IntVar   value = new IntVar(cp, 0, 0);

// Step 2: punch some holes in the domains
cp.setLevel(cp.level + 1);
index.dom().subtractAdapt(-2, -1);
index.dom().subtractAdapt(1, 3);
if ( !cp.consistency() ) {
    // rest assured, this is never reached.
    System.err.println("WHAT ?!");
}

// Step3: Impose an element constraint on our variables
cp.setLevel(cp.level + 1);
cp.impose(Element.choose(index, vars, value));
if ( !cp.consistency() ) {
    // This time, it fails even though index = {0}, vars = [{0}], value = {0} is a solution.
    System.err.println("Ahem, this is wrong !");
}

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.