After thinking about this some more I have another suggestion that requires far fewer variables.
Besides the nominal variables themselves
IntVar[] x;
we can make a list of the at most five values present in a given solution
IntVar[] values;
And then use the AddElement constraint to make sure each of the variables is equal to one of these values. We define a set of indices and use the
IntVar[] indices;
for (int i = 0; i < nVars; i++)
{
model.AddElement(indices[i], values, x[i]);
}
The AddElement constraint ensures that x[i] == values[indices[i]]
Example: if values[1] = 29 and indices[3] = 1, then x[3] must be values[indices[3]] = values[1] = 29
The values and indices don't need to be constrained at all, they can legally take on any element in their domain, after which the variables x are all fixed. To avoid getting too many duplicate solutions in the x variables, we can constrain the values to be all different in the array as a sort of symmetry breaking.
This is a working c# code that demonstrates the idea:
using Google.OrTools.Sat;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
namespace SO68801590v3
{
class Program
{
static void Main(string[] args)
{
try
{
Google.OrTools.Sat.CpModel model = new CpModel();
ORModel myModel = new ORModel();
myModel.initModel(model);
IntVar[] decisionVariables = myModel.decisionVariables;
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter solutionPrinter = new VarArraySolutionPrinter(myModel.variablesToPrintOut);
solver.SearchAllSolutions(model, solutionPrinter);
Console.WriteLine(String.Format("Number of solutions found: {0}",
solutionPrinter.SolutionCount()));
}
catch (Exception e)
{
Console.WriteLine(e.Message);
Console.WriteLine(e.StackTrace);
throw;
}
Console.WriteLine("OK");
Console.ReadKey();
}
}
class ORModel
{
const int nVars = 13;
const int valMin = 28;
const int valMax = 40;
const int nValues = valMax - valMin + 1;
const int maxDifferentValues = 5;
IntVar[] x = new IntVar[nVars];
IntVar[] values = new IntVar[maxDifferentValues];
IntVar[] indices = new IntVar[nVars];
public IntVar[] decisionVariables
{
get
{
return x;
}
}
public IntVar[] variablesToPrintOut
{
get
{
IntVar[] variablesToPrintOut_ = new IntVar[2 * nVars + maxDifferentValues];
int ix = 0;
for (int i = 0; i < nVars; i++)
{
variablesToPrintOut_[ix] = x[i];
ix++;
}
for (int i = 0; i < nVars; i++)
{
variablesToPrintOut_[ix] = indices[i];
ix++;
}
for (int j = 0; j < maxDifferentValues; j++)
{
variablesToPrintOut_[ix] = values[j];
ix++;
}
return variablesToPrintOut_;
}
}
public void initModel(CpModel model)
{
// Make variables and indices
for (int i = 0; i < nVars; i++)
{
x[i] = model.NewIntVar(valMin, valMax, string.Format("X{0,3:D3}", i + 1));
indices[i] = model.NewIntVar(0, maxDifferentValues - 1, string.Format("Index{0,3:D3}", i + 1));
}
// Make the list of different values
for (int j = 0; j < maxDifferentValues; j++)
{
values[j] = model.NewIntVar(valMin, valMax, string.Format("Value{0,3:D3}", j + 1));
}
// Each variable has to be one of the defined values
// We'll use the AddElement constraint for this
// AddElement adds the element constraint: variables[index] == target
for (int i = 0; i < nVars; i++)
{
model.AddElement(indices[i], values, x[i]);
}
// As a kind of "symmetry breaking" we'll also make sure that the values are
// all different to avoid returning too many duplicate solutions
model.AddAllDifferent(values);
}
}
public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
private int solution_count_;
private IntVar[] variables;
public VarArraySolutionPrinter(IntVar[] variables)
{
this.variables = variables;
}
public override void OnSolutionCallback()
{
// using (StreamWriter sw = new StreamWriter(@"C:\temp\GoogleSATSolverExperiments.txt", true, Encoding.UTF8))
using (TextWriter sw = Console.Out)
{
sw.WriteLine(String.Format("Solution #{0}: time = {1:F2} s;",
solution_count_, WallTime()));
foreach (IntVar v in variables)
{
sw.Write(
String.Format(" {0} = {1}\r\n", v.ShortString(), Value(v)));
}
solution_count_++;
sw.WriteLine();
}
if (solution_count_ >= 10)
{
StopSearch();
}
}
public int SolutionCount()
{
return solution_count_;
}
}
}