Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • Apr 09 13:32
  • Apr 09 13:13
    lgtm-com[bot] commented #787
  • Apr 09 12:55
    cprudhom synchronize #787
  • Apr 09 12:55

    cprudhom on sat-branch

    fix LGTM alert Update tests wrt to PropSat sid… (compare)

  • Apr 09 07:12
    cprudhom commented #783
  • Apr 09 06:53
    cprudhom milestoned #783
  • Apr 09 06:53
    cprudhom labeled #783
  • Apr 09 06:53
    cprudhom assigned #783
  • Apr 08 17:58
  • Apr 08 17:41
    lgtm-com[bot] commented #787
  • Apr 08 17:25
    cprudhom milestoned #787
  • Apr 08 17:24
    cprudhom opened #787
  • Apr 08 17:23

    cprudhom on sat-branch

    Fix issues #779 and #780 + add … Related to #780: rename some me… Fix isse #780 and 2 more (compare)

  • Apr 02 14:05
    cprudhom labeled #786
  • Apr 02 14:05
    cprudhom milestoned #786
  • Apr 02 14:05
    cprudhom assigned #786
  • Apr 02 14:05
    cprudhom opened #786
  • Mar 31 06:11
  • Mar 31 05:34
    dependabot[bot] labeled #785
  • Mar 31 05:34
    dependabot[bot] opened #785
brunesto
@brunesto
Hi I forgot to mention yesterday that I was forcing a given solution, in order to find out why my model can't find it by itself. In any case
I have documented my steps here: https://stackoverflow.com/questions/66760624/how-to-check-which-constraints-would-be-violated-by-a-presumed-solution
brunesto
@brunesto
What I was expecting is a way to somehow match the contradiction message with the actual variables in my code. (e.g. to match sum_exp_40 with my variables' name, something like sum(vehicleLoad[1],vehicleLoad[2],...))
Charles Prud'homme
@cprudhom
Indeed, the problem can be either reformulated or new variables and contraintes are added, wich makes the detection harder.
Your fix in stack overflow is good, you can also consider overriding the associates(Variable) method to detect variable creation
brunesto
@brunesto
Thanks, I updated the stack overflow post to also override associates()
Charles Prud'homme
@cprudhom
Great !
Rick
@Rick8998

Hello everyone, I'm new to this library (I've been using it for a few days) and I have a question (which could be trivial)
I would like to check if a variable is involved in a constraint, but I can't find the way to do it. I do not know neither the specific variable nor the specific constraint, in input I only receive a model object that will have, hopefully, variables and constraints associated with them. For the variable I want to check I assume it is the last of an array created as follows:

Variable [] varAry = inputModel.getVars()
I also get an array of constraints with Constraint [] aryCs = inputModel.getCstrs ()

Removing a variable is not a problem, unless it is involved in a constraint (because I cannot remove a variable if it is involved in a constraint). So I have to remove the constraint first (inputModel.unpost (Constraint cs)), and then I can remove the variable (inputModel.unassociates (Variable v)) However, to remove the correct constraint I have to check that the variable I want to remove is involved in it. Is there any way to do this?

Charles Prud'homme
@cprudhom
Hi, choco-solver was not originally designed to work in this way, so this kind of action is not straightforward. I invite you to look at the Model.unpost() method to see what it does, as well as Model.unassociates(). This may help you, but be aware that it is at your own risk
Rick
@Rick8998
Ok thanks a lot for your help. Is there any other possible way? For example, create a new Model and assign it the variables and constraints obtained from the inputModel, but removing some values? I'm just guessing
But even so I would have to check whether the variable belongs to a certain constraint, and as you said the library was not designed to do this type of work
I don't know, if you have any kind of suggestion, if there is any, I gladly listen to it
Thanks so much again
Charles Prud'homme
@cprudhom
You can’t share variables between models, a variable (a constraint) is attached to one single Model (because the model itself manage backtracking values)
Why in the firt place, you want to check the constraint of a variable?
Rick
@Rick8998

What I have to do is check if, given a problem P, the subproblem P-1 (ie the problem P to which I "delete" a variable) has a solution; and I have to do it recursively on each subproblem P-1 until I get to the problem containing only one variable.
Because, if the subproblem P-1 already has no solutions, it is useless to continue with the search. So I would like to eliminate a variable from P (or rather, create the sub-Model P-1, which represents the subproblem P-1, given as input the Model P, which represents the problem P); to do this, however, I noticed that, if the variable is involved in a constraint, I cannot remove it unless, of course, I also remove the constraint itself. So I need to search, among all the constraints of the input Model, those that involve the variable and eliminate them in order to then eliminate it (the variable) and create the sub-Model P-1.

Maybe there is a way to work directly on the P-1 sub-model? Maybe it is (or can be) represented directly in some way without making a copy of the Model P?

The ideal would be not to work on the original Model, but to create a local "copy" of it in order not to modify the starting problem and work recursively on this copy

Rick
@Rick8998
I know I can directly check if the Model P has solutions, but I am doing this because I am trying to implement an algorithm that avoids backtracking and the pseudocode requires this kind of work
Charles Prud'homme
@cprudhom

I am trying to implement an algorithm that avoids backtracking

well, I don’t think CP is fit for this usage

The ideal would be not to work on the original Model, but to create a local "copy" of it in order not to modify the starting problem and work recursively on this copy

Sadly, with choco you can’t work with copies

One way to achieve this is to reify each constraint and encode a search strategy that activate/deactivate constraint through their boolean variable
Well, I suppose you can recursively add/remove variables and constraints, but you shoud reset the search each time to avoid unexpected behavior
Hugo Duncan
@hugoduncan
It would be nice to be able to optionally name intVars returned by ArExpression.intVar
Rick
@Rick8998

The ideal would be not to work on the original Model, but to create a local "copy" of it in order not to modify the starting problem and work recursively on this copy

Sadly, with choco you can’t work with copies

Yes, I see

One way to achieve this is to reify each constraint and encode a search strategy that activate/deactivate constraint through their boolean variable

So, if I understand correctly, basically after having reified the constraint, start a search strategy that, given an input variable, looks for the constraints that contain that variable and "deactivates" them through their boolean variable, or at least this is l main objective of this research. But how do I check the correspondence between constraint and variable, that is, if that constraint contains that variable? Sorry, but I'm not 100% familiar with the library as I've only been working on it for a few days

Well, I suppose you can recursively add/remove variables and constraints, but you shoud reset the search each time to avoid unexpected behavior

Ok, thank you very much, I'll keep that in mind

Charles Prud'homme
@cprudhom

It would be nice to be able to optionally name intVars returned by ArExpression.intVar

Sure, would you mind opening an issue on GitHub?

@Rick8998

But how do I check the correspondence between constraint and variable, that is, if that constraint contains that variable?

This could be manage by yourself in pure Java.

Hugo Duncan
@hugoduncan
iiuc, a propagator with a monitor on an IntVar is going to be called when the IntVar bounds change, and the propagator uses forEachRemVal to trigger domain updates. forEachRemVal calls the passed procedure to propagate the change for each removed value. If 1000 values are removed, this will lead to 1000 calls of the propagator's procedure. If the propagator only cares about the new domain of the monitored IntVar, then only one of these calls is required. Is the propagator expected to optimise the other calls as no-ops, or is there a way to use the monitor to only trigger the procedure once?
Hugo Duncan
@hugoduncan
Um, I guess call forEachRemVal is actually optional. Question answered.
Charles Prud'homme
@cprudhom
forEachRemVal is a mothod of delta monitor. A delta monitor observes a variable for a given propagator and stores removed values from last call to this propagator. This can be very time consuming and should be used when the propagator is incremental. That is, when it is better to react on value removal than scanning the domain on each variable modification. Note that a delta monitor is consumend on the propagator’s propagate method, in which all new removed values are managed.
If you only want to react on a specific value removal, you should not declare delta monitor and only check the presence/absence of a value on propagate(i,e)
Hugo Duncan
@hugoduncan
makes sense, thank you
Hugo Duncan
@hugoduncan
Does choco have the equivalent of balance? https://sofdem.github.io/gccat/gccat/Cbalance.html#uid14962
Hugo Duncan
@hugoduncan
I am looking at implementing balance. To make the implementation incremental would require the propagator to maintain some state (counts of each value). It seems propagators are intended to be stateless. What is the rationale for this? I guess we could store that state in model variables (and maybe this could be made transparent to model?). Just trying to understand the intended pattern for implementing propagators.
Hugo Duncan
@hugoduncan
Also looking at PropSum, I see it seems to always do a coarse grained filtering, rather than fine grained updates. Is the overhead of a monitor greater than the cost of just using coarse grained filtering in the case?
Charles Prud'homme
@cprudhom
Did you have a look at the tutorial about constraint designing? https://choco-solver.org/tutos/constraints/
That should help to design a stateful propagator
You can also have a look at some other propagators in the library
About coarse/fine grained filtering, it really depends on what you can do incremental and the tradeoff. A common way to achieve this is to:
  1. define isEntailed() (that will be really helpful in following steps)
  2. define propagate(int) to make sure it is complete (no loss of solutions) and correct (no fake solutions)
  3. define propagate(int, int) only if you encounter some performance issue and/or there is simpler algo when only few variables have been modified
Charles Prud'homme
@cprudhom
well, it depends more on the constraints involved. Theoritically, Integer.MIN_VALUE + 1 and Integer.MAX_VALUE-1 but when such a variable is involved in scalar or times, there will be some underflow/overflow
But, I plan to introduce large domain variable/constraints
9 4
@bios8086_gitlab
@cprudhom Thank you very much for your reply. I worte a very simple CSP problem. int lb = Integer.MIN_VALUE+1; is problematic .
Model model = new Model("Good!");
int lb = Integer.MIN_VALUE+1; // this will cause a problem
int lb = Integer.MIN_VALUE+1250000000;
int ub = Integer.MAX_VALUE-1250000000;
IntVar a = model.intVar(lb, ub);
IntVar b = model.intVar(lb, ub);
Solver solver = model.getSolver();
while (solver.solve()) {
//System.out.format("a=%d, b=%d %n", a.getValue(), b.getValue());
}
solver.printStatistics();
Charles Prud'homme
@cprudhom
In order to prevent overflow/underflow, we add some assertion on big domain. You have an error because the domain is too big
Do you really need such a lower bound?
9 4
@bios8086_gitlab
@cprudhom Sometimes it might be useful to have such large domain. Because our model may need large domains with simple constraints.
Hugo Duncan
@hugoduncan
@cprudhom thanks - I somehow missed that the example there was stateful. Does choco already have the equivalent of the balance constraint?
Charles Prud'homme
@cprudhom
@hugoduncan no, but you can decomposite it with count, max and arithm
Hugo Duncan
@hugoduncan

We have a model that can find a solution (for some well formed input values, and using a custom value selector) without back-tracking, With 204 variables, 115 constraints and 81 nodes, it has a model build time of 6ms and finds a solution in 5ms. Scaling the same model by 16, with 3084 variables, 1555 constraints and 1,281 nodes, it builds the model in 135ms and finds a solution (again without backtracking) in 20s. For our use case we would need to scale this by another factor of 128 and solve within 1s

Profiling with yourkit shows 16s of the 20s in the StoredLong constructor. Are we missing some config that would improve this?

Hugo Duncan
@hugoduncan
Um, this all seems to be within PropCount_AC, in Set_Std_BitSet.add, in S64BitSet.set
Hugo Duncan
@hugoduncan
StoredLong gets call 16800 times, all via the path above
Charles Prud'homme
@cprudhom
That’s because PropCount_AC relies on backtrackable bitset to store possible values and mandatory ones. Such a bitset is an array of StoredLong. That’s becuase PropCount_AC is incremental, to avoid scanning all variables at each modification. If you think you will never backtrack, I suppose you should code this heuristic to avoid using all that stuff.
Hugo Duncan
@hugoduncan
We can avoid back tracking only for certain inputs, for which the solution is trivially found by inspection, and the full solver is needed in general. Is there some way to turn off fakeHistoryNeeded?
Charles Prud'homme
@cprudhom
Model model = new Model(new DefaultSettings().setEnvironmentHistorySimulationCondition(() -> false)); is what you need !
Hugo Duncan
@hugoduncan
Thank you.