I am supervising a student project that uses JaCoP, and I believe that we have been using it successfully for a time, but we have come across a problem that I have been unable to solve. Our goal is to specify that while more than one value in a variable's domain is acceptable, we have preferences about which one should be chosen.
For example, suppose that there is a variable named whose domain is {0, 1, 3, 4}. And suppose that I have preferences about which value is chosen: 4 is my first choice, then 1, then 3, then 0.
My thought about how to model this was with a series of SoftGCC constraints about the values 1, 3, and 0 with increasing costs. Each would specify a soft upper bound and soft lower bound of 0, so that if the variable is assigned any of those values it would violate the soft constraint and thus incur the cost. And since the cost escalates as you move down the preference order, I would expect the system to assign the least costly / most preferred possible choice.
However, that does not seem to be the case. If I have one option that has no SoftGCC constraint at all that is viable, it is chosen. But if every viable option has some cost associated with it, then they appear to be chosen without regard to the magnitude of the costs. Thus, I am assuming that we are misunderstanding something about the way that SoftGCC works or how to use it.
Below is a minimal non-working example that demonstrates the problem:
// In this problem we have a single variable whose domain is {0, 1, 3, 4}.
// A hard constraint prevents 4 from being chosen.
// I have a preference list of <4, 1, 3, 0>.
// So I am trying to force the system to assign the value 1 to my variable, but it instead assigns 0.
Store store = new Store();
int countedValues = 1;
IntVar variable = new IntVar(store, "variable", 0, 1);
variable.addDom(new IntervalDomain(3, 4));
IntVar[] xVars = new IntVar[1];
xVars[0] = variable;
// Assigning variable=1 incurs a cost of 1.
int cost = 1;
IntVar costVar1 = new IntVar(store, "cost_variable_" + cost, cost, cost);
IntVar[] hardCounters = new IntVar[countedValues];
IntVar hardCounter1 = new IntVar(store, "HardCounter_" + 1, 0, 1);
hardCounters[0] = hardCounter1;
int[] countedValue = new int[]{1};
int[] softLowerBound = new int[]{0};
int[] softUpperBound = new int[]{0};
SoftGCC softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar1, ViolationMeasure.VALUE_BASED);
store.imposeDecomposition(softConstraint);
// Assigning variable=3 incurs a cost of 2.
cost = 2;
IntVar costVar3 = new IntVar(store, "cost_variable_" + cost, cost, cost);
hardCounters = new IntVar[countedValues];
IntVar hardCounter3 = new IntVar(store, "HardCounter_" + 3, 0, 1);
hardCounters[0] = hardCounter3;
countedValue = new int[]{3};
softLowerBound = new int[]{0};
softUpperBound = new int[]{0};
softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar3, ViolationMeasure.VALUE_BASED);
store.imposeDecomposition(softConstraint);
// Assigning variable=0 incurs a cost of 3.
cost = 3;
IntVar costVar0 = new IntVar(store, "cost_variable_" + cost, cost, cost);
hardCounters = new IntVar[countedValues];
IntVar hardCounter0 = new IntVar(store, "HardCounter_" + 0, 0, 1);
hardCounters[0] = hardCounter0;
countedValue = new int[]{0};
softLowerBound = new int[]{0};
softUpperBound = new int[]{0};
softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar0, ViolationMeasure.VALUE_BASED);
store.imposeDecomposition(softConstraint);
// The assignment variable=4 is not possible.
store.impose(new XneqC(variable, 4));
HashSet<IntVar> allVariables = new HashSet<>();
allVariables.add(variable);
allVariables.add(costVar0);
allVariables.add(costVar1);
allVariables.add(costVar3);
allVariables.add(hardCounter0);
allVariables.add(hardCounter1);
allVariables.add(hardCounter3);
IntVar[] allVariablesArray = allVariables.toArray(new IntVar[allVariables.size()]);
Search<IntVar> label = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> select = new InputOrderSelect<IntVar>(store, allVariablesArray, new IndomainMin<IntVar>());
label.labeling(store, select);
I suppose I have three questions:
1) Is expressing preferences about which values are assigned to a variable a reasonable thing to do want to do with JaCoP?
2) If so, is there a better way to accomplish this than my idea?
3) If not, what am we doing wrong when setting up our SoftGCC constraints?
Thank you,
Chad Hogg
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Before posting I searched this forum for every term I could think of that might be relevant to my question: "preferences", "soft constraints", "softGCC", "ranking", etc. But I didn't browse until after posting my question, which means I didn't find https://sourceforge.net/p/jacop-solver/discussion/1220992/thread/1ac13678/. It looks to me like using a InDomainHierarchical containing an InDomainList per variable as suggested here would be a good way to solve my problem.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hello,
I am supervising a student project that uses JaCoP, and I believe that we have been using it successfully for a time, but we have come across a problem that I have been unable to solve. Our goal is to specify that while more than one value in a variable's domain is acceptable, we have preferences about which one should be chosen.
For example, suppose that there is a variable named whose domain is {0, 1, 3, 4}. And suppose that I have preferences about which value is chosen: 4 is my first choice, then 1, then 3, then 0.
My thought about how to model this was with a series of SoftGCC constraints about the values 1, 3, and 0 with increasing costs. Each would specify a soft upper bound and soft lower bound of 0, so that if the variable is assigned any of those values it would violate the soft constraint and thus incur the cost. And since the cost escalates as you move down the preference order, I would expect the system to assign the least costly / most preferred possible choice.
However, that does not seem to be the case. If I have one option that has no SoftGCC constraint at all that is viable, it is chosen. But if every viable option has some cost associated with it, then they appear to be chosen without regard to the magnitude of the costs. Thus, I am assuming that we are misunderstanding something about the way that SoftGCC works or how to use it.
Below is a minimal non-working example that demonstrates the problem:
// In this problem we have a single variable whose domain is {0, 1, 3, 4}. // A hard constraint prevents 4 from being chosen. // I have a preference list of <4, 1, 3, 0>. // So I am trying to force the system to assign the value 1 to my variable, but it instead assigns 0. Store store = new Store(); int countedValues = 1; IntVar variable = new IntVar(store, "variable", 0, 1); variable.addDom(new IntervalDomain(3, 4)); IntVar[] xVars = new IntVar[1]; xVars[0] = variable; // Assigning variable=1 incurs a cost of 1. int cost = 1; IntVar costVar1 = new IntVar(store, "cost_variable_" + cost, cost, cost); IntVar[] hardCounters = new IntVar[countedValues]; IntVar hardCounter1 = new IntVar(store, "HardCounter_" + 1, 0, 1); hardCounters[0] = hardCounter1; int[] countedValue = new int[]{1}; int[] softLowerBound = new int[]{0}; int[] softUpperBound = new int[]{0}; SoftGCC softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar1, ViolationMeasure.VALUE_BASED); store.imposeDecomposition(softConstraint); // Assigning variable=3 incurs a cost of 2. cost = 2; IntVar costVar3 = new IntVar(store, "cost_variable_" + cost, cost, cost); hardCounters = new IntVar[countedValues]; IntVar hardCounter3 = new IntVar(store, "HardCounter_" + 3, 0, 1); hardCounters[0] = hardCounter3; countedValue = new int[]{3}; softLowerBound = new int[]{0}; softUpperBound = new int[]{0}; softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar3, ViolationMeasure.VALUE_BASED); store.imposeDecomposition(softConstraint); // Assigning variable=0 incurs a cost of 3. cost = 3; IntVar costVar0 = new IntVar(store, "cost_variable_" + cost, cost, cost); hardCounters = new IntVar[countedValues]; IntVar hardCounter0 = new IntVar(store, "HardCounter_" + 0, 0, 1); hardCounters[0] = hardCounter0; countedValue = new int[]{0}; softLowerBound = new int[]{0}; softUpperBound = new int[]{0}; softConstraint = new SoftGCC(xVars, hardCounters, countedValue, softLowerBound, softUpperBound, costVar0, ViolationMeasure.VALUE_BASED); store.imposeDecomposition(softConstraint); // The assignment variable=4 is not possible. store.impose(new XneqC(variable, 4)); HashSet<IntVar> allVariables = new HashSet<>(); allVariables.add(variable); allVariables.add(costVar0); allVariables.add(costVar1); allVariables.add(costVar3); allVariables.add(hardCounter0); allVariables.add(hardCounter1); allVariables.add(hardCounter3); IntVar[] allVariablesArray = allVariables.toArray(new IntVar[allVariables.size()]); Search<IntVar> label = new DepthFirstSearch<IntVar>(); SelectChoicePoint<IntVar> select = new InputOrderSelect<IntVar>(store, allVariablesArray, new IndomainMin<IntVar>()); label.labeling(store, select);I suppose I have three questions:
1) Is expressing preferences about which values are assigned to a variable a reasonable thing to do want to do with JaCoP?
2) If so, is there a better way to accomplish this than my idea?
3) If not, what am we doing wrong when setting up our SoftGCC constraints?
Thank you,
Chad Hogg
Before posting I searched this forum for every term I could think of that might be relevant to my question: "preferences", "soft constraints", "softGCC", "ranking", etc. But I didn't browse until after posting my question, which means I didn't find https://sourceforge.net/p/jacop-solver/discussion/1220992/thread/1ac13678/. It looks to me like using a InDomainHierarchical containing an InDomainList per variable as suggested here would be a good way to solve my problem.
Great! I would propose the same solution.
/Kris