Activity for kris
-
kris posted a comment on discussion Help
In the current version of JaCoP, I think, you can use the following solution written in peudo-code. IntVar[] z = new IntVar[n]; make domains for each z[i].domain = x[i].domain union {0} forall i store.impose(new IfThenElse(c[i], new XeqY(z[i], x[i]), new XeqC(z[i], 0) result = sum(z) For sum you can use either Sum constraint (avoids recomputations of already ground variables) or SumInt constraint (recomputs everything). Depending on cache efficiency one of constraints can be mnore efficient. If you...
-
There is, in fact another posibility to solve your problem. This formulation dies not use set variables. It basically creates a vector of values that are not in y (for othe values a constant outside the domain is added) and the finds a m inimal value. The program looks like that. int n = 5; Store store = new Store(); IntVar[] x = new IntVar[n]; for (int i = 0; i < n; i++) { x[i] = new IntVar(store, "x["+i+"]", 1, n); } IntVar[] y = new IntVar[n]; for (int i = 0; i < n; i++) { y[i] = new IntVar(store,...
-
I do not see any simple solution. The solution I propose is based on set variables. In minizinc it can be programmed as follows. include "globals.mzn"; int: n = 5; array[1..n] of var 1..n: x; array[1..n] of var 1..n: y; var 1..n: m; var set of 1..n: xs; constraint xs = array2set(x) diff array2set(y) /\ m = min(xs); solve satisfy; output["x = (x)\ny = (y)\nmin = (m)\nxs = (xs)"] It basically creates set variable xs that contains all elements of x that are not in y and then it finds minimum value in...
-
I do not know :( The constraints should be in store... /Kris
-
Hi! No, if you print the store you will see the constraint. In your first question it was constraint XplusYeqZ46, that is the foolowing constraint. *** Constraint: XplusYeqZ46 : XplusYeqZ(U1-2-R1-1:(1)-li = 110, U1-2-R1-1:(1)-w2::{1..362}, U1-2-R1-1:(1)-i::{111..472} ) Best, /Kris
-
Hi Peter, Yes, XplusYeqZ21 is an particular instance of XplusYeqZ. Similar for XplusYeqZ19. You can see all the constraints when you print the store in Java. However, you will not see waht was the store state when constraint failed :( Best, /Kris
-
Hi! The informartion is that 182 times constraints of type XplusYeqZ failed during search and more specifically 182 times fails constraint XplusYeqZ46. I hope it helps to understand the output of statistics. Best, /Kris
-
Hi Peter, You can take a look at my slides at https://fileadmin.cs.lth.se/cs/Education/EDAN01/presentations/lecture6.pdf. First 18 slides discuss depth-fist-search in general and slides 14-15 present a simpliied Java method for search in JaCoP. In this method variable selection uses input order and value selection starts from minimal value. Alternatively, you can try to find similar discussions on internet. Best, /Kris
-
Hi Peter, Explanation of search in constraint programmin requires several presentations :( Therefore, I send you a link to get more information how it is defined in JaCoP, for more details see http://jacopguide.osolpro.com/guideJaCoP.html#x1-570006 and http://jacopguide.osolpro.com/guideJaCoP.html#x1-87000B. I do not know your problem but, in general, you should probably group variables using SimpleMatrixSelect or search first on x and then on y variables. The important is also to use rgiht variable...
-
Hi Peter, It is difficult to answer your question without looking at your code but I think this is caused by your search. It seems that the search goes very deeply (recursive calls) and there is a stack overflow. It is probably different stack size in Eclipse and gradle. You can try to use your model from command line using java command with option -Xss100M, for example (it makes stack size of 100M). In general depth-first-search is very important and you should make a more "intelligent" search....
-
Hi, Diffn constraint assures that all defined rectangles does not overlap. It does not generate any combination of the defined rectangles but uses several pruning method, such as sweep line algorithm. To have a spacing between rectangles you can use larger retangles, that is define additional space around them. Use your geometrical knowledge. /Kris
-
Hi! To impose a non-overlapping constraint on rectangels use org.jacop.constraints.diffn.Diffn.java constraint. It can handle better many recatngles than combination of primitive constraints. The number of constraints is not a problem. The problem is search. You can look at your search definition, for example a variable selection method. God luck, /Kris
-
Hi! No, it is not possible to export constraints from the store to flatzinc file. /Kris
-
Hi Simon, OK, I understad. This is basically the search on IntVar but cost variable is FloatVar. Am I right? I this case, when the solver finds a solution it tries to find better, that is at least of "value = current value - ulp" (unit at the last position). It might help to define a biger optiomization step by using FloatDomain.setStep(0.1);, for example. You may try also jacop.floats.search.Optimize but I am ot sure if this will work in your case. BTW, how many solutions you get? Best, /Kris
-
Hi! I do ot kow your problem but, i general, to make CP model efficient you need to make two things. First, you need to use global costraints since they are more efficient than primitive. For schedulig one ususally uses Cumulative and Diffn costraits. Possibly, depennding on the problem other constraints may be usefull. Second, good search heuristic that tekes into account the problem structure. Of course, it might be that your complex cost function is the problem for the solver. Best regards, /...
-
Hi! I do ot kow your problem but, i general, to make CP model efficient you need to make two things. First, you need to use global costraints since they are more efficient than primitive. For schedulig one ususally uses Cumulative and Diffn costraits. Possibly, depennding on the problem other constraints may be usefull. Second, good search heuristic that tekes into account the problem structure. Of course, it might be that your complex cost function is the problem for the solver. Best regards, /...
-
Hi Yurii, Unfortunately we do not have any manual that describes clearly how to build new constraints or search but we can help you if you will have questions. Below there is a very short guide on this. The constraints always extend either PrimitiveConstraint or Constraint. You probably will extend Constraint since it does not need to implement methods for negated versions of the constraint (notConsistency and norSatisfied). Bascially you need to create a constructor that builds all needed data structures...
-
Hi! As I wrote in the previous mail, you need to do search. It is not enough to do consistency. The solver does not "see" that the index is the same in both ElementFloat constraints when pruning domains. Possible search can look as follows. DepthFirstSearch<FloatVar> label = new DepthFirstSearch<FloatVar>(); SplitSelectFloat<FloatVar> s = new SplitSelectFloat<FloatVar>(store, new FloatVar[] {var1, var2, mult}, null); label.setSolutionListener(new PrintOutListener<FloatVar>()); label.getSolutionListener().searchAll(true);...
-
Hi! I am not sure if I understand your question but if you need the arrays indexes to change together you simply use the same index for both Element constraints. In such case you will get the answer you ask for. The main point is that you need to define your search to search for all solutions and JaCoP will find 18.0 then 32.0 and finally 15.0. Bset, /Kris
-
Hi! I am not sure if I understand your question but if you need the arrays indexes to change together you simply use the same index for both Element constraints. In such case you will get the answer you ask for. The main point is that you need to define your search to search for all solutions and JaCoP will find 18.0 then 32.0 and finally 15.0. Bset, /Kris
-
1) Yes, because IndomainMin starts from minimal values of varibales. You may try IndomainMiddle. It starts from middle values, zero in your case. 2) No. /Kris
-
1) The order of expressions (constraints more precisly) is irrelevent. Important is order in search of variables and values. 2) Yes, but it will try many possible assignments. In worst case 201^(number of variables) in your example. It might take ages... :( 3) If your expressions are linear (example attached to your question) you may try linear programming. Linear solvers are better for such cases. /Kris
-
BTW, in the new release later this year there will be new variable selection methods that are based on activity or fault count of variables. It seems that they work well for such cases as yours. Next comment. IndomainRandom is not very reliable method for the solver. /Kris
-
There is no such thing as infinite loop! The solver tries values and do not come to a solution in a reasonable time. Heuristics MostConstrain and MinDomainOverDegree seems to make a good job since you start with variables that are present in most constraints. Best, /Kris
-
Hi Erik, The solver uses depth-first-search for solving constraints. It means that it selects first a variable and then a value from its domain and makes a decision var = value. If this decision fails it backtracks and make decisions var != value. This is why it is important in what order you select variables and values for assignment. Method MinDomainOverDegree selects a variable with the minimal value of doamain size divided by number of active constraints for this variable. This is a good method...
-
This is classical linear programming problem and CP ca be used but is not as good as linear programming. Some variable selection methods are better than other. You may experiment with them a little bit. Best, /Kris
-
Hi! I do not see your whole program but I can try to answer. The reason for stack overflow or "infinite loop" is that you try to assign values that do not have solutions and depth-first-search fails all the time and might exhaust the stack. To avoid this , if you use IntVar, you should define a better variable selection method. Currently you are using InputOrderSelect. Try SimpleSelect and SmallestDomain variable selection method, for example. If this will not help you may try SplitSelect. Regards,...
-
Hi! Solution process involves depth-first-search and varibales are basically selected one by one and a value is assgined to a varibale from its domain. Comparators define the order of selecting variables. The simplest is input order, but you may select for example a variable assigned to most constraints (e.g., MostConstrainedDynamic) or with smallest domain (SmallestDomain). Depending on the problem different orders, sometimes called heuristics, help to find solution(s) faster. Best, /Kris
-
Hi! JaCoP uses depth-first search (DFS) algorithm for finding a solution and bound-and-bound algorithm for optimization. Definition of DFS indicates in what order we select varibales and how we give values yo the selected variable. In your case, you select first a, then b and so on. You also give a random value from the domain of the varibale to be assigned to this variable. Every time a value is assigned the propagation engine propagates the decision to other constraints and removes inconsistent...
-
No, DepthFirstSearch class searches for a solution and can stop after finding the first one. You control whether it finds all solutions or only the first one by the followoing instruction. search.getSolutionListener().searchAll(true); and seting the value to true or false. Morover search selects variables and values assigned to these variables using choice point selection (a class implementing interface SelectChoicePoint). In the classes implementing this interface one defines in what order variables...
-
Hi! To be able to answer your question in details I need to see your code or at least a larger chunk of the code. You can send it to me directly, if you do not want to show it here. In general, the search has expnential complexity and the order of variables to be used for assigning their values in search matters very much. You use InputOrder, try to use SimpleSelect with SmallestDomain variable selection method, for example. Best regards, /Kris
-
Hi! There is several problems in the model but most important is search. You need to specify right search and it is an "art". Several comments You do not need to include varable suma in the labeling list; it will get value by propagation from SumInt constraints. Constraint Alldifferent is correct but does not remove all incolnsistent values from domains of valriables; use Alldiff (complexity O(n*logn) and bound consistency) or Alldistinct (complexity O(N^(5/2) and complete consistency) Search using...
-
Yes, there might be two reasons for that. First, convergence might be very slow. Second, and more important. When we compute floating point operations on intervals we need to do, so called, outward rounding. Min value needs to be rounded down and max value rounded up. This is basically to assure that no value is lost in computations. This rounding is not possible in Java and therefore we subtract ulp (unit at the last position) from min value and add ulp to max value. Note, that ulp value differes...
-
Hi Artur, Floating point SplitSelect splits domains of variables and checks if the problems is still consistent. The search stops when all variables are considered ground (have a single value). In case of IntVar it is very clear but for FloatVar we use precision that defines this. Basically, when max-min <= precision we consider a FloatVar to be ground and the search stops updating this variable. Precision is set by FloatDomain.setPrecision(double p) method and can be checked by FloatDomain.precision()...
-
Hi! If a variable does not get a value through propagation it must be included in the search. You may add this variable to a search or, even better, make a sequence of searches and the last one contains this variable. For more details please check http://jacopguide.osolpro.com/guideJaCoP.html#x1-580005. Best, /Kris
-
Hi! The solver cannot be "instructed" to extend the domains but you can write a program that builds your model with variable ranges (-100, 100) and calls search. If thissearch fails you build the model again but, in this case, with broader ranges and again calls the search. You can do it untill a solution is found. /Kris
-
This is not possible in general. All posaed constraints are considered by the solver. The only possible solution is to pose first all constraints that do not have c as a prameter and find solutions ( or one solution) and then add other constraints and find solutions. Please note that you need to inform the solver to not assign a solution using DepthFirstSearch method setAssignSolution(false). /Kris
-
This why I provided you with my cpviz.zip file that has compiled class files. Fetch it from the address specified in previous mail. /Kris
-
Try the followiong command (with right path to cpviz, of course). java -cp batik-1.9/batik-squiggle-1.9.jar:jhall.jar:/viztool/src components.InternalFrame viz.out/aaa.idx I assume you use batik-1.9. /Kris
-
Hi! I have uploaded jar files some time ago and use them since then. I can send you compiled cpviz but I have checked cpviz at sourceforge a moment ago and file InternalFrame.java still exists. You can download my compiled version at http://fileadmin.cs.lth.se/jacop/cpviz.zip. Best, /Kris
-
Hi! You model is (probably) logically correct but inefficient. As I have indicated in my previous mail you should use global constraints. In case of your model, you can, for example, use CumulativeUnary constraint for all tasks in each floor. This will replace all Or constraints. Alternatively you may use Diff2 or Diffn for all tasks on all floors. These constraints model task as an rectangle and ensure that rectangles do not overlap. Hope this helps. /Kris
-
Hi! First, do you use global constraints for scheduling, such as cumulative and/or diff2/diffn? The model is more efficinet with these constraints. Second, search. I have no idea how your start matrix looks like. I would use [[start_1, floor_1], [start_2, floor_2],...] and select tuples [start, floor] based on variable start. Alternatively, you can try to use sequential search (http://jacopguide.osolpro.com/guideJaCoP.html#x1-580005) with first searhcing on start variables and then floor. Try also...
-
The typical way to model CP problems is to define all constraints and find a slution or solutions. The definition of restart search does not change the model, it only constraints the cost. /Kris
-
First of all adding constraints incrementally is not typical way to model CP propblems ;) Saying that I can add that it is possible to add constraints before and under search. The method you refer to addresses the first case. You add new constraint and all the added constraints are considered by the solver. The second method, adding constraints, under search, is more complicated. Basically in each decision point you can add constraints. They will be valid on higher search levels and will disappear...
-
The impact depends on the problem but Alldistinct requires more computations and the complexity of the involved algorithms is higher. Alldistinct has complexity O(n^2.5) since it involves bipartite graph matching and Alldiff compxity of our impelemntation is O(n^2). Of course, there are some constants involved that for small lists of variables plays a significant role ;) /Kris
-
Two more comments. You may also check SimpleMatrixSelect where you can specify an array of variables (vector of vectors) and select the whole sub-vector for labeling. Your problem conatin symmetries that you may eliminate to get faster proof of optimality. There is several methods to do that. A simple one fixes, for example, one rectangle, into left top "quarter" of the ålacement space. /Kris
-
Hi! I just realized that you have two "types" of variables. Variables a_i and b_i. It might be good to use in such case sequence of searches. First on varibales a and then on variables b. For example, the search can be defined as below. Search<IntVar> slave = new DepthFirstSearch<IntVar>(); SelectChoicePoint<IntVar> selectSlave = new SimpleSelect<IntVar>(varsB, new SmallestMin<IntVar>(), new SmallestDomain<IntVar>(), new IndomainMin<IntVar>()); slave.setSelectChoicePoint(selectSlave); Search<IntVar>...
-
Yes, the order matters, specially if you use InputOrder variable selection heuristic. Try other heuristics, such as SmallestDomain or MostConstrainedStatic. Since the variable are selected based on specific criteria during search they are less dependent by the orde rof variables. /Kris
-
Thanks for your comment. We have introduced this boolean variable to limit number of the solutions, specially for sequence of searches. It is not really reflected in the Guide. Thanks. /Kris
-
Right! The performance overhead will not be so high if all FDVs in the "additional" search are ground (got a value by propagation). In this case we basically check them and skip them in search. Good luck with your problem, /Kris
-
Hi Peter, In this paragraph I talk on possible situation that might happen for not very careful programmers. Regarding your example, it depends what you will include in vector s. If you only, for example, include only part of decision variables it might happen that other decision variables do not get a single value (by propagation) and even worse, the other variables might not have in their domains possible correct values. Best, /Kris
-
In general, the search will take longer time since we need to label more variables. This "overhead" is problem specific and it might be very small or very large. Note, however, that in special situations, when the solution found by labeling variables specified by the programmer is not part of the correct solution, the additional search might be long to find this situation and return to the original search. /Kris
-
Formally, you csan only be sure that the result is correct if all FDVs get a single value but ... in many pratcial cases intermediate variables get values by propagation. This is probably the case for your exasmple. If you give a value to a then a * a will propagate. I think a good idea is to print the store when you get a solution and check if all variables get a value. Alternatively you can add a slave search that gives values to all intermediate variables. Best, /Kris
-
One possible example is at https://github.com/hakank/hakank/blob/master/minizinc/graph_partition.mzn /Kris
-
If all weights are 1 then you can skip multiplication by w[i]. /Kris
-
I would do the following. I define variable p[i] for each node i and then define the partitioning cost, for example, as number of edges that go between partitions. This can be definef as cost = sum (i in 1..n, j in i+1..n) ( (x[i] != x[j]) * w[i]); where w[i] defines the "weight" of the edge or numbe rof edges going between two nodes. Then we can minimize the cost of partitioning. /Kris
-
You are using a set and sets do not have multiplple emenets and therefore it is not possible. Sorry! /Kris
-
You can do it by constracring IntervalDomain to values you want. For example SetVar v = new SetVar(store, "v", new BoundSetDomain( new IntervalDomain(1, 2), new IntervalDomain(1, 10))); will create v::{{1..2}..{1..10}}[card={2..10}] If you want glb = {1,3} you need to create IntervalDomain constaining 1 and then add 3. For example d = new IntervalDomain(1, 1); d.unionAdapt(3,3); This should give you d :: {{1,3}..{1..3}}[card=2..3}] You may also use addElement method from IntervalDomain. I hope it...
-
Hi again, Yes, please use AndBoolVector. AndBoolSimple is only in the solver to define 2-input parameter constraints and to be a little bit more efficient than general n-input parameter AndBoolVector. In most cases it does not matter very much. AndBool is a wrapper that generates either AndBoolSimple or AndBoolVector In the forthcomming release of version 4.5 we define AndBool as a decomposed constraint and therefore it cannot be used as parameter to other constraints (it must be primitive constraint)....
-
Hi! You are right. it is a bug in version 4.4. It works with AndBoolSimple but not with AndBool that makes conversion to AndBoolSimple or AndBooVector. However, it should work with AndBoolVector. Thanks for pointing this problem. It is already fixed for the new release. Best, /Kris
-
Hi Alicia, I have tried your constraint example and it is satisifed. I used the following code. void ex() { store = new Store(); IntVar L0 = new IntVar(store, "L0", 1, 100); IntVar TA0 = new IntVar(store, "TA0", 0, 0); IntVar N0001_0_FS = new IntVar(store, "N0001_0_FS", 0, 0); IntVar N0002_0_FS = new IntVar(store, "N0002_0_FS", 0, 1); IntVar N0000_0_FS = new IntVar(store, "N0000_0_FS", 0, 0); store.impose(new IfThen( new XgtY(L0, TA0), new AndBoolSimple(N0001_0_FS, N0002_0_FS, N0000_0_FS))); boolean...
-
Your search in the included code searches for the first leagal solution and this...
-
Hi! Your question basically addresses the problem of a solution iterator. No, it...
-
You are right. The comments are incorrect. The first comment that states that it...
-
I just checked the code and you can try to do the following. sat.debug = true; This...
-
Hi! No, there is no way currently to print-out generated clauses to SAT solver. The...
-
No, it is not a bug. If you comment 'store.consistency();' JaCoP prints "No solution...
-
Hi Juha! I see you are doing rather complex and non-standrad things. This requires...
-
Hi! You can decompose the constraint as follows. store.impose(new XmodYeqZ(X, Y,...
-
It is difficult to answer if I do not know your problem but I propose to make the...
-
Hi! It might be that your problem is too difficult for JaCoP ;( Regarding floating-poiny...
-
Hi! The best approach for SumFloat is to use LinearFloat. If you have the following...
-
The algorithm for labeling is DFS (Depth First Search). If you use cost function...
-
The algorithm follows the idea of the Algorithm 1 presented in @article{DBLP:journals/tcad/AbderrahmanCK99,...
-
Hi! Basically you should decmopose the equations into simpler constraints using additional...
-
Yes, you are right. There is a bug in method toString in And class (constraint)....
-
Yes. /Kris
-
XdivY(X, Y, temp) IfThenElse(Y > 0, Z = temp, Z = 0) /Kris
-
Use temporary variable temp and do the following XdivYeqZ(X, Y, temp) and then you...
-
My suggestion si to use IntVar only. Instead of FloatVar use "scaled" IntVar (by...
-
One way to avoid FloatVar is to use IntVar by scaling FloatVar by factor 10, for...
-
Add search.getSolutionListener().recordSolutions(true); before startting search,...
-
Hi! Unfortunatley, I do not have time to look more carefully at your example but...
-
First, I encode v1^v2 = v3 in JaCoP minzinc compiler as FloatVar tmp1 = new FloatVar(store,...
-
Hi! You should not receive solutions with different value of m variable but you may...
-
Hi! I mean that it can be coded as x = log_a(y). Since log with base a does not exist...
-
Hi Motitz! There exist several ways of representing this constraint. One way is to...
-
Hi! Yes, that is true. We do not have PpowQeqR. You can make simple transofrmations...
-
Hi Jochen! Here is a simple search that generates all solutions to your constraints....
-
This is JaCoP bug. Basically, it is a bug in comapre method for java.util.Arrays.sort....
-
Please, check the attached file that models and solves (cannot prove optimality however...
-
You have something wrong with your constraints. I have run you model with the search...
-
To make sum you use LinearFloat. You creaye a vector of all x[i] and sum, and use...
-
I would suggest to use x and y as IntVar and then define FloatVar x_float and y_float....
-
I did not check your model and constraints carefully but you do not define any search...
-
Hi! I have checked the dfference between version 4.4 and my development version 4.5,...
-
Hi! I have checked your exampel and got the following print-out Solution : [x=1.0000000000000004]...
-
No, there is no simple way to do it but you may adjust domains of your variables...
-
Hi Mike! To solve the problem (or trying to solve it) you need to search for a solution....
-
Great! I would propose the same solution. /Kris
1 >