Set the amount of possible unique values for variables in ORTOOLS CP-SAT

Viewed 689

Looking to set/limit the amount of unique variables generated by ortools cp-sat. I currently have a list of 13 variables i.e. x1, x2, x3... I want to be able to ensure that out of these 13 variables only 5 unique values are given. I understand that i will have to assign a Boolean variable to each variable, but am unsure on how to do this. Here is another similar question that got answered, however when i input that code i get an error saying that AddImplication requires a Boolean where my variable should be entered, according to his answer..

How to define a constraint in Ortools to set a limit of distinct values

Thank you all in advance hope someone out here knows something :)

2 Answers

In addition to your variables, you need to make a new boolean variable for each of the possible values in their domains (b1, b2, b3...) . It is those boolean variables that you would use in the constraints mentioned in https://stackoverflow.com/posts/60448315/revisions.

Then you would need to add implication constraints for each variable / value:

x1 == 1 => b1 == 1
x2 == 1 => b1 == 1
...
xn == 1 => b1 == 1

x1 == 2 => b2 == 1
x2 == 2 => b2 == 1
...
xn == 2 => b2 == 1
etc.

Then add the constraints mentioned in https://stackoverflow.com/posts/60448315/revisions.

This is a working example in c#:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using Google.OrTools.Sat;

namespace SO68801590v2
{
    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(decisionVariables);
                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[13];
        IntVar[,] b = new IntVar[nVars, nValues];
        IntVar[] b_any = new IntVar[nValues];

        public IntVar[] decisionVariables
        {
            get
            {
                return x;
            }
        }

        public void initModel(CpModel model)
        {

            for (int i = 0; i < nVars; i++)
            {
                // The variables.
                x[i] = model.NewIntVar(valMin, valMax, string.Format("X{0,3:D3}", i + 1));
                for (int j = 0; j < nValues; j++)
                {
                    int value = j + valMin;
                    // A boolean equivalent to "Xi == value j"
                    b[i, j] = model.NewBoolVar(string.Format("X{0,3:D3}_{1,3:D3}", i + 1, value));
                    model.Add(x[i] == value).OnlyEnforceIf(b[i, j]);
                    model.Add(x[i] != value).OnlyEnforceIf(b[i, j].Not());
                }
            }
            // Booleans equivalent to "some value X == value j"
            for (int j = 0; j < nValues; j++)
            {
                List<IntVar> list = new List<IntVar>();
                for (int i = 0; i < nVars; i++)
                {
                    list.Add(b[i, j]);
                }
                int value = j + valMin;
                b_any[j] = model.NewBoolVar(string.Format("Value{0,3:D3}IsPresent", value));
                model.AddMaxEquality(b_any[j], list);
            }
            // Now make sure we respect the limit of distinct values
            model.Add(new SumArray(b_any) <= maxDifferentValues);
        }
    }

    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.Write(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_;
        }

    }
}

Since there are a lot of valid solutions I limited the printout to 10 of them.

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_;
        }
    }
}
Related