Unexpected behavior using AddAbsEquality in CP-SAT (.NET) #2017
Description
Hi,
We are using OR Tools' CP-SAT solver to find the optimal mix of materials that have certain properties (full detail with explanation in code sample below).
This means our optimization function is minimizing the difference between the properties of the material mix and the target properties we are aiming for.
To be able to minimize this difference, we are using the CpModel.AddAbsEquality() method.
The problem is we get behavior I cannot explain (bug?).
In certain cases (see example below), adding the AddAbsEquality() constraints make the solution infeasible, even though we are only adding a constraint in the form of:
A* = Math.Abs(A)
Given that the model is feasible without the above constraint, I don't see how adding this constraint can make it infeasible if this is the only constraint mentioning variable A*.
It seems like there should always be a possible value for A* that can be chosen by the model as A* is not constrained by any other constraint.
Below you can find the sample code that demonstrates the issue.
You can also find it here (full C# project)
The code as shown below works, and is feasible (even optimal).
However when commenting out the constraint below the !!!! ISSUE !!!!! line, the model becomes infeasible for no apparent reason. See comments in code for more explanation.
Are we missing something? Or is this a bug?
Full C# project in attachment as well (.zip).
Note: The model in the sample below is working with variables with percentages. As the CP-SAT can only work with integers, all percentage values have been multiplied by a factor to make them integers, preserving 2 decimal place accuracy (e.g. 36,74%).
// We are looking for the optimal mix of two materials that have different properties.
// Each material is made up of particles of different sizes, think two types of gravel
// that have different size rocks in them.
// We measure the properties of the material by measuring the volume of material that
// can pass through two different sieves:
// Sieve 1, for example, has 10mm holes in it.
// Sieve 2, for example, has 2mm holes in it.
// For each material we measure the volume (in %) of the material that can pass through each sieve.
// Material 1:
// - 70% passes through sieve 1
// - 30% also passes through sieve 2
// So that means:
// - 30% of the volume of material 1 are particles > 10 mm
// - 40% of the volume of material 1 are particles <= 10 mm and > 2 mm
// - 30% of the volume of material 1 are particles < 2 mm
// Material 2 has different properties:
// - 90% passes through sieve 1
// - 75% also passes through sieve 2
// Our goal is to find a mix of both materials that comes as close as possible to
// our target particle distribution.
// For this example, let's say we want:
// Target mix:
// - 80% passes through sieve 1
// - 50% also passes through sieve 2
// Se would like to find out how to mix both materials (what % of each in the mix) so that
// the mix has the desired properties?
// Creating the model.
// [START model]
CpModel model = new CpModel();
// [END model]
// [START variables]
// These are the variables we are actually interested in.
// The volume percentages of each material in the mix. How much (in %) of each material should we put in the mix?
IntVar volPctMaterial1 = model.NewIntVar(0, 10000, "v%1");
IntVar volPctMaterial2 = model.NewIntVar(0, 10000, "v%2");
// The rest of the variables are intermediate variables.
// First we have the percentages of the mix that pass through both sieves.
// These should be as close as possible to our target (80/50 in our example).
IntVar sieve1PassPctForMix = model.NewIntVar(0, 100000000, "Y1");
IntVar sieve2PassPctForMix = model.NewIntVar(0, 100000000, "Y2");
// These variables will contain the difference between the actual and target pass percentages for the mix.
// For example: if the target is 80% through sieve 1, but our solution finds a mix where 75% passes through sieve 1,
// then the passPctDeltaForSieve1 is 5% (80% - 75%).
IntVar passPctDeltaSieve1 = model.NewIntVar(-100000000, 100000000, "passPctDeltaSieve1");
IntVar passPctDeltaSieve2 = model.NewIntVar(-100000000, 100000000, "passPctDeltaSieve2");
// These variables are the ABS() (positive) values of our delta variables.
// We will optimize for the lowest sum of these ABS() delta variables, so that our mix comes as close as
// possible to our desired pass percentages.
IntVar passPctDeltaAbsSieve1 = model.NewIntVar(0, 100000000, "passPctDeltaAbsSieve1");
IntVar passPctDeltaAbsSieve2 = model.NewIntVar(0, 100000000, "passPctDeltaAbsSieve2");
// [END variables]
// [START constraints]
// Add the mixture pass percentage constraints (Y1 = v%1*Y11 + v%2*Y12 + ... + v%n*Y1n).
// The formula for the amount of the mix that passes through each sieve is the weighted sum of the pass
// percentages of the materials in the mix.
// For example: if the mix is 50% material 1, 50% material 2, and 70% of material 1 passes through sieve 1,
// while 90% of material 2 passes through sieve 1,
// then 80% of the mix would pass through sieve 1 (= 50%*70% + 50%*90%).
model.Add(sieve1PassPctForMix == 7000 * volPctMaterial1 + 9000 * volPctMaterial2);
model.Add(sieve2PassPctForMix == 3000 * volPctMaterial1 + 7500 * volPctMaterial2);
// The volume percentages should add up to 100% constraint.
// The mix can for example be 40% material 1, 60% material 2: 40 + 60 = 100
model.Add(volPctMaterial1 + volPctMaterial2 == 10000);
// We calculate the difference between our target pass percentages and our target
model.Add(passPctDeltaSieve1 == sieve1PassPctForMix - 80000000);
model.Add(passPctDeltaSieve2 == sieve2PassPctForMix - 50000000);
// We now calculate the absolute values of these differences, so we can minimize their sum.
model.AddAbsEquality(passPctDeltaSieve1, passPctDeltaAbsSieve1);
model.AddAbsEquality(passPctDeltaSieve2, passPctDeltaAbsSieve2);
// !!!!!!!!!!!!!!!!
// !!!! ISSUE !!!!!
// Uncommenting the line below makes the solution INFEASIBLE. Why?
//model.Add(volPctMaterial2 == 3000); // 30% of the mix needs to be material 2
// Observation #1:
// Uncommenting the above line does NOT make the solution INFEASIBLE if we remove the
// two AddAbsEquality constraints. Why?
// Why does adding a variable that is the ABS() of another value constrain the solution?
// There always is a value that is the ABS() of another value. We are not mentioning
// passPctDeltaAbsSieve1 and passPctDeltaAbsSieve2 in any other constraints, so the algorithm
// should always be able to find a value for them (the ABS() of passPctDeltaSieve1 and passPctDeltaSieve2)
// Observation #2:
// Changing the value 3000 (30% ) in the above constraint to 5000 (50%) makes the solution FEASIBLE. Why?
// Both should be feasible.
// !!!!!!!!!!!!!!!!
// [END constraints]
// We minimize the sum of the absolute difference between the actual and target pass percentages for the mix.
model.Minimize(new SumArray(new IntVar[] {
passPctDeltaAbsSieve1,
passPctDeltaAbsSieve2,
}));
// [START solve]
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
// [END solve]