Get variable solution domain

[Igor Proshkin]

I am using CP-SAT solver in python. I can get a value for all my variables if I use Solve() or I can get all values if I use SearchForAllSolutions(). 

Is there a way to get variable solution domains instead?

Example:

from ortools.sat.python import cp_model

model = cp_model.CpModel()
x = model.NewIntVar(0, 1000000, 'x')


model.Add(x > 100)
model.Add(x < 10000)

solver = cp_model.CpSolver()
solver.Solve(model)

#Get x domain? 101..9999 

[Laurent Perron]

See https://github.com/google/or-tools/blob/stable/ortools/sat/doc/solver.md#searching-for-all-solutions-in-a-satisfiability-model

When searching for all solutions, you need a callback to collect the values of variables in each solution.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/98e71d97-3321-4776-b425-8c1c6648ae91o%40googlegroups.com.

[Igor Proshkin]

Yes, I understand how to get all solutions with SearchForAllSolutions, but is there a way to get the domain (list of ranges) instead. In my case, the number of solutions can be very big but they all belong to one or two ranges. I don't want to have my callback called million times if I would be able to get just a range of possible values. 

You probably calculating and storing each variable domain somewhere during solve (or even pre-solve). Can I access it from python? If not, can I do it in c++?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEebHx96JAdb55NcUN7eMEWOmqiGpwts-dEw0mKeAQ1%3D6Xg%40mail.gmail.com.

[Laurent Perron]

You cannot escape the exponential search part if you want to find all values that are part of a solution.

Imagine you have a constraint that x must be even, then you domain is not described by a single interval.

Now, in your trivial case, 

solver = cp_model.CpSolver()

solver.parameters.fill_tightened_domains_in_response = True

solver.Solve(model)

print(solver.ResponseProto())

will produce the following result

status: OPTIMAL

solution: 101

num_booleans: 1

num_branches: 1

num_integer_propagations: 1

wall_time: 0.000451

user_time: 0.000451

deterministic_time: 8e-08

tightened_variables {

  name: "x"

  domain: 101

  domain: 9999

}

But note that this information is very approximate in the general case.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAA%3D%3D6MHWx8z9SXWwW7XnG1xJ5xouBPiJ%3DaAn_gYB7DiPuq5Vyw%40mail.gmail.com.

[Igor Proshkin]

Is this tightened_variables domain is always a single range?

Do you precalculate any multirange domains that can be accessible?

For example in this code:

v1 = model.NewIntVar(0, 1000000, "v1")

b1 = model.NewBoolVar("b1")

model.Add(v1 < 1000).OnlyEnforceIf(b1)

model.Add(v1 > 10000).OnlyEnforceIf(b1.Not())

The v1 domain would be two ranges: [0..999, 10001..1000000] 

Laurent,  thank you so much for your help. Every time I got the response I am learning something very useful.

[Laurent Perron]

Can you try it ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f9f77876-d558-4bb3-94ba-d79b2b839c9fo%40googlegroups.com.

[Igor Proshkin]

Yes, this is the result:

status: FEASIBLE

solution: 10001

solution: 0

num_booleans: 4

num_branches: 8

num_binary_propagations: 14

num_integer_propagations: 10

wall_time: 0.0002119

user_time: 0.00021180000000000003

deterministic_time: 3.719999999999999e-06

tightened_variables {

  name: "v1"

  domain: 0

  domain: 1000000

}

tightened_variables {

  name: "b1"

  domain: 0

  domain: 1

}

and this is the code:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

v1 = model.NewIntVar(0, 1000000, "v1")
b1 = model.NewBoolVar("b1")

model.Add(v1 < 1000).OnlyEnforceIf(b1)
model.Add(v1 > 10000).OnlyEnforceIf(b1.Not())

solver = cp_model.CpSolver()
solver.Solve(model)

solver.parameters.fill_tightened_domains_in_response = True
solver.Solve(model)
print(solver.ResponseProto())

On Tuesday, June 9, 2020 at 10:51:21 AM UTC-7, Igor Proshkin wrote:

[Laurent Perron]

Unfortunate :-)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/312107e2-2703-4d97-9620-03b5ac03ce55o%40googlegroups.com.

[Laurent Perron]

It turns out it was a bug in our presolve

I pushed the fix on master. Now it outputs:

tightened_variables {

  name: "v1"

  domain: 0

  domain: 999

  domain: 10001

  domain: 1000000

}

tightened_variables {

  name: "b1"

  domain: 0

  domain: 1

}

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Christopher Hamkins]

I too am interested in finding variable domains that could be part of some solution.

We have a product model with hundreds of features and constraints. A user makes selections for certain features, which further restrict the solution and the values allowed for the other features. We want to show the user the remaining values in the feature domains which are still possible in some solution, and provide a single solution to use as  "default values" for the rest of the features.

In the original CP-Solver we do this by saving the feature domains at the end of the initial propagation before the first Decision by the solver. Although this is not mathematically perfect, since some values could still be rejected via failed decisions and backtracking, it is "good enough" for our purposes of guiding the user and does not add any overhead to the solution search. All the values rejected in the constraint propagation are never part of a solution, Of the remaining values, it turns out that for our models failure discovered only after Decisiions and backtracking is the exception and not the rule. If the user selects such a value, a failure is discovered and the user has to change his or her selection.

In the CP-SAT solver I have been unable to find something equivalent to "end of the initial propagation" to save the feature domains at that point. Can anyone provide some guidance on how to do something equivalent in the CP-SAT solver?

[Frederic Didier]

This is exactly what was discussed here, if you solve with

fill_tightened_domains_in_response:true (and optionally stop_after_presolve:true if you just want to be fast, but don't want supper tight domain)  the solver should return what you want in the tightened_variables field.

The feature is not super used yet, so let us know if something does not work as intended.

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ac6d8ff4-014a-4d83-af35-2db7e06d9e44o%40googlegroups.com.

[Christopher Hamkins]

Thank you very much I will give this a try.

[Christopher Hamkins]

Working in c# with the CP-SAT solver I made a very small model with some key featues of our product models:

- Conditionally active restriction tables

- Conditionally active assignments

Here's the code:

using System;

using Google.OrTools.Sat;

namespace GoogleSATSolverExperiments02

{

    class GoogleSatSolverExperiments02Main

    {

        static void Main(string[] args)

        {

            // Create the model

            Google.OrTools.Sat.CpModel model = new CpModel();

            MyORModel myModel = new MyORModel();

            myModel.initModel(model);

            IntVar[] decisionVariables = myModel.decisionVariables;

            // Create a solver and solves the model.

            Console.WriteLine("Basic model:");

            CpSolver solver = new CpSolver();

            solver.StringParameters = "fill_tightened_domains_in_response:true";

            Console.WriteLine(solver.StringParameters);

            MySolutionPrinter solutionPrinter = new MySolutionPrinter(decisionVariables);

            solver.SearchAllSolutions(model, solutionPrinter);

            Console.WriteLine(String.Format("Number of solutions found: {0}",

                solutionPrinter.SolutionCount()));

            foreach (IntegerVariableProto ivp in solver.Response.TightenedVariables)

            {

                Console.WriteLine(ivp.ToString());

            }

            // Try it again with only presolve

            Console.WriteLine("Basic model:");

            solver.StringParameters = "fill_tightened_domains_in_response:true stop_after_presolve:true";

            Console.WriteLine(solver.StringParameters);

            solutionPrinter.reset();

            solver.SearchAllSolutions(model, solutionPrinter);

            Console.WriteLine(String.Format("Number of solutions found: {0}",

                solutionPrinter.SolutionCount()));

            foreach (IntegerVariableProto ivp in solver.Response.TightenedVariables)

            {

                Console.WriteLine(ivp.ToString());

            }

            // Restrict the model with a simulated user selection C == 0

            Console.WriteLine("\nModel with additional restriction C == 0:");

            model.Add(myModel.C == 0L);

            solver.StringParameters = "fill_tightened_domains_in_response:true";

            Console.WriteLine(solver.StringParameters);

            solutionPrinter.reset();

            solver.SearchAllSolutions(model, solutionPrinter);

            Console.WriteLine(String.Format("Number of solutions found: {0}",

                solutionPrinter.SolutionCount()));

            foreach (IntegerVariableProto ivp in solver.Response.TightenedVariables)

            {

                Console.WriteLine(ivp.ToString());

            }

            Console.WriteLine("Press any key to continue...");

            Console.ReadKey();

        }

    }

    class MyORModel

    {

        public IntVar A;

        public IntVar B;

        public IntVar C;

        public IntVar D;

        public IntVar Atab;

        public IntVar Btab;

        public IntVar Ctab;

        public Constraint tableConstraint;

        public Constraint valueAssignmentConstraint;

        public IntVar tableCondition;

        public BoundedLinearExpression tableConditionExpression;

        public Constraint tableConditionConstraint;

        public BoundedLinearExpression tableConditionExpressionNegated;

        public Constraint tableConditionNegatedConstraint;

        public IntVar[] decisionVariables

        {

            get

            {

                return new IntVar[] { A, B, C, D, tableCondition };

            }

        }

        public void initModel(CpModel model)

        {

            // The variables themselves

            A = model.NewIntVar(0L, 2L, "A");

            B = model.NewIntVar(0L, 1L, "B");

            C = model.NewIntVar(0L, 2L, "C");

            D = model.NewIntVar(0L, 2L, "D");

            // Tuple set for restriction table

            // Values for A, B, C may only be values listed on a line in this table, if D == 0.

            long[,] tableData = new long[2, 3]

            {

             { 0, 1, 0 },

             { 1, 0, 0 },

            };

            // Tuple set header

            // Since OnlyEnforceIf() is not supported for AddAllowedAssignments constraint,

            // need to simulate this using local table variables and enforcing equality

            // with the original variables in case the enforcing condition is true.

            Atab = model.NewIntVarFromDomain(A.Domain, "Atab");

            Btab = model.NewIntVarFromDomain(B.Domain, "Btab");

            Ctab = model.NewIntVarFromDomain(C.Domain, "Ctab");

            IntVar[] tupleSetHeader = new IntVar[] { Atab, Btab, Ctab };

            // Table constraint

            tableConstraint = model.AddAllowedAssignments(tupleSetHeader, tableData);

            // Table only applies when D == 0

            // IntVar implements the ILiteral interface required as argument to OnlyEnforceIf

            tableCondition = model.NewBoolVar("tableCondition");

            // Link the boolan variable to the expression D == 0

            // This is basically copied from an example given in 

            // https://github.com/google/or-tools/blob/master/ortools/sat/doc/channeling.md

            // and seems to be the only way to do it although it seems pretty awkward

            tableConditionExpression = (D == 0);

            tableConditionConstraint = model.Add(tableConditionExpression);

            tableConditionConstraint.OnlyEnforceIf(tableCondition);

            tableConditionExpressionNegated = (D != 0);

            tableConditionNegatedConstraint = model.Add(tableConditionExpressionNegated);

            tableConditionNegatedConstraint.OnlyEnforceIf(tableCondition.Not());

            // When the table is enforced, real variables and local table variables must be the same.

            Constraint Aequality = model.Add(A == Atab);

            Aequality.OnlyEnforceIf(tableCondition);

            Constraint Bequality = model.Add(B == Btab);

            Bequality.OnlyEnforceIf(tableCondition);

            Constraint Cequality = model.Add(C == Ctab);

            Cequality.OnlyEnforceIf(tableCondition);

            // To avoid irrelevant multiple solutions, assign local table variables to the 

            // first line of the table when it is not enforced

            Constraint AtabDefault = model.Add(Atab == tableData[0, 0]);

            AtabDefault.OnlyEnforceIf(tableCondition.Not());

            Constraint BtabDefault = model.Add(Btab == tableData[0, 1]);

            BtabDefault.OnlyEnforceIf(tableCondition.Not());

            Constraint CtabDefault = model.Add(Ctab == tableData[0, 2]);

            CtabDefault.OnlyEnforceIf(tableCondition.Not());

            // Value assignment constraint

            // C may only take on the value 2 if the table is not enforced (i.e. D != 0).

            valueAssignmentConstraint = model.Add(C == 2L);

            valueAssignmentConstraint.OnlyEnforceIf(tableCondition.Not());

        }

    }

    public class MySolutionPrinter : CpSolverSolutionCallback

    {

        public MySolutionPrinter(IntVar[] variables)

        {

            variables_ = variables;

        }

        public override void OnSolutionCallback()

        {

            Console.Write("Solution #{0}: ", solution_count_);

            foreach (IntVar v in variables_)

            {

                Console.Write(

                String.Format(" {0}={1};", v.ShortString(), Value(v)));

            }

            solution_count_++;

            Console.WriteLine();

        }

        public int SolutionCount()

        {

            return solution_count_;

        }

        internal void reset()

        {

            solution_count_ = 0;

        }

        private int solution_count_;

        private IntVar[] variables_;

    }

}

This is the output:

Basic model:

fill_tightened_domains_in_response:true

Solution #0:  A=2; B=0; C=2; D=1; tableCondition=0;

Solution #1:  A=0; B=0; C=2; D=1; tableCondition=0;

Solution #2:  A=1; B=0; C=2; D=1; tableCondition=0;

Solution #3:  A=1; B=0; C=0; D=0; tableCondition=1;

Solution #4:  A=1; B=0; C=2; D=2; tableCondition=0;

Solution #5:  A=0; B=0; C=2; D=2; tableCondition=0;

Solution #6:  A=2; B=0; C=2; D=2; tableCondition=0;

Solution #7:  A=2; B=1; C=2; D=1; tableCondition=0;

Solution #8:  A=0; B=1; C=2; D=1; tableCondition=0;

Solution #9:  A=1; B=1; C=2; D=1; tableCondition=0;

Solution #10:  A=1; B=1; C=2; D=2; tableCondition=0;

Solution #11:  A=0; B=1; C=2; D=2; tableCondition=0;

Solution #12:  A=2; B=1; C=2; D=2; tableCondition=0;

Solution #13:  A=0; B=1; C=0; D=0; tableCondition=1;

Number of solutions found: 14

{ "name": "A", "domain": [ "0", "2" ] }

{ "name": "B", "domain": [ "0", "1" ] }

{ "name": "C", "domain": [ "0", "0", "2", "2" ] }

{ "name": "D", "domain": [ "0", "2" ] }

{ "name": "Atab", "domain": [ "0", "1" ] }

{ "name": "Btab", "domain": [ "0", "1" ] }

{ "name": "Ctab", "domain": [ "0", "0" ] }

{ "name": "tableCondition", "domain": [ "0", "1" ] }

Basic model:

fill_tightened_domains_in_response:true stop_after_presolve:true

Number of solutions found: 0

Model with additional restriction C == 0:

fill_tightened_domains_in_response:true

Solution #0:  A=1; B=0; C=0; D=0; tableCondition=1;

Solution #1:  A=0; B=1; C=0; D=0; tableCondition=1;

Number of solutions found: 2

{ "name": "A", "domain": [ "0", "1" ] }

{ "name": "B", "domain": [ "0", "1" ] }

{ "name": "C", "domain": [ "0", "0" ] }

{ "name": "D", "domain": [ "0", "0" ] }

{ "name": "Atab", "domain": [ "0", "1" ] }

{ "name": "Btab", "domain": [ "0", "1" ] }

{ "name": "Ctab", "domain": [ "0", "0" ] }

{ "name": "tableCondition", "domain": [ "1", "1" ] }

Press any key to continue...

When the solution search was actually done, the contents of the tightened variables are exactly what I expected.

However, there was no output of any tightened variables using stop_after_presolve:true because the list of tightened variables was empty. Apparently it is only filled in the response when a real solution is found.

Is there any way to get access to the tightened variables without actually doing a real solution search?

[Christopher Hamkins]

The TightenedVariables field in CpSolverResponse in c#  seems to have been introduced sometime between OrTools versions 6.7 and 7.3

[Frederic Didier]

Yeah sorry, I realized there was a bug after I replied to you, I submitted a fix internally but I am not sure yet when it will be pushed to the or-tool repository (hopefully soon).

I think if you specify a time limit that is not too long, it is a decent work around until this work with stop_after_presolve:true.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/6d58fcd6-0f55-4781-a0fc-cc5aa0d83451o%40googlegroups.com.

[Christopher Hamkins]

Thanks for the quick response and fix! I'll watch for the fix.

[Laurent Perron]

I just pushed the fix.

Thanks

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cabcfd57-b968-4d6c-96eb-e0d22158dad7o%40googlegroups.com.

[Christopher Hamkins]

To test with the fix I cloned the source from GitHub master (7.7.7814) and built from source as described (did this for the first time, had used binaries previously).

During the test step "tools\make test_dotnet" I first got an error with fsdiet.fs about wrong parameter type, changed line 41 from

let obj = cost.Minimize(1L)

to

let obj = cost.Minimize(1)

after which it worked.

But there is a more serious error during execution of NetworkRoutingSat as follows. The problem is reproducible and also occurs in the debugger when I started the project in Visual Studio.

Model mp_c10_b5_d10.t5-10.cd2-5.bd3-5.mc20.fc10.s0

Computing all possible paths

    - extra hops = 6

    - max paths per demand = 1200

Fatal error. System.AccessViolationException: Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

   at Google.OrTools.Sat.operations_research_satPINVOKE.SatHelper_SolveWithStringParametersAndSolutionCallback(Int32, Byte[], System.String, System.Runtime.InteropServices.HandleRef)

   at Google.OrTools.Sat.operations_research_satPINVOKE.SatHelper_SolveWithStringParametersAndSolutionCallback(Int32, Byte[], System.String, System.Runtime.InteropServices.HandleRef)

   at Google.OrTools.Sat.SatHelper.SolveWithStringParametersAndSolutionCallback(Google.OrTools.Sat.CpModelProto, System.String, Google.OrTools.Sat.SolutionCallback)

   at Google.OrTools.Sat.CpSolver.SearchAllSolutions(Google.OrTools.Sat.CpModel, Google.OrTools.Sat.SolutionCallback)

   at NetworkRoutingSat+NetworkRoutingSolver.ComputeAllPathsForOneDemandAndOnePathLength(Int32, Int32, Int32)

   at NetworkRoutingSat+NetworkRoutingSolver.ComputeAllPaths(Int32, Int32)

   at NetworkRoutingSat+NetworkRoutingSolver.InitPaths(NetworkRoutingData, Int32, Int32)

   at NetworkRoutingSat+NetworkRoutingSolver.Init(NetworkRoutingData, Int32, Int32)

   at NetworkRoutingSat.Main(System.String[])

Is this a bug or am I doing something wrong?

Am Dienstag, 16. Juni 2020 13:17:19 UTC+2 schrieb Laurent Perron:

I just pushed the fix.

Thanks

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mar. 16 juin 2020 à 12:04, Christopher Hamkins <christoph...@ksb.com> a écrit :

Thanks for the quick response and fix! I'll watch for the fix.

Am Dienstag, 16. Juni 2020 11:55:39 UTC+2 schrieb Frederic Didier:

Yeah sorry, I realized there was a bug after I replied to you, I submitted a fix internally but I am not sure yet when it will be pushed to the or-tool repository (hopefully soon).

I think if you specify a time limit that is not too long, it is a decent work around until this work with stop_after_presolve:true.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Laurent Perron]

most likely different versions of protobuf in c++ and C#.

Can you check the deps of you C# project ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c13d4191-f980-4d01-9c24-ce49de2cef89o%40googlegroups.com.

[Christopher Hamkins]

The c# project is the NetworkRoutingSat.csproj included in the examples (not my code). When I open it in VS, it is showing a dependency on Google.Protobuf 3.11.2.

I guess the c++ is using 3.12.2 which is in the or-tools\dependencies\sources folder.

Is the defined dependency on 3.11.2 coming from a setting on my machine or is it defined in the or-tools package itself?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c13d4191-f980-4d01-9c24-ce49de2cef89o%40googlegroups.com.

[Mizux Dev]

it comes from the Google.OrTools csproj

<ItemGroup>
  <PackageReference Include="Google.Protobuf" Version="3.11.2"/>
</ItemGroup> 

: https://github.com/google/or-tools/blob/e9616e190fd99f13cd7acad953c93b9de02a4c2d/ortools/dotnet/Google.OrTools/Google.OrTools.csproj.in#L139-L141 

ps: Protobuf just releqse the 3.12.3, 15 days ago...

https://github.com/protocolbuffers/protobuf/releases

ERRATUM: after investigation, it seems the 3.12.3 is borken -> need to target the 3.12.2

ref: https://github.com/google/or-tools/commit/95b9094f1a7d8e3cd0522cb6be70171823407cb6

[Igor Proshkin]

Laurent,

I just tried my old example and noticed that the variable names are no longer in the  tightened_variables  :

status: OPTIMAL
solution: 10001
solution: 0
num_booleans: 1
num_branches: 2
num_integer_propagations: 2
wall_time: 0.014527400000000001
user_time: 0.014527600000000002
deterministic_time: 1.84e-06
solution_info: "default_lp"
tightened_variables {

  domain: 0
  domain: 999
  domain: 10001
  domain: 1000000
}
tightened_variables {

  domain: 0
  domain: 1
}
num_restarts: 2

How can I locate the variable I am interested in, in tightened_variables?

[Igor Proshkin]

I guess  tightened_variables are sorted by variable index, right?

If so, can I just do tightened_variables[my_var.Index()]?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/946f8da7-aeb7-4a2d-9def-7a38bad8426dn%40googlegroups.com.

[Laurent Perron]

Yes, same order

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAA%3D%3D6MFPO-ha0Dc26g%3D_GiK-16c2kz2YLRWiMYXGwUcQd6_7aA%40mail.gmail.com.

[Igor Proshkin]

I am using  tightened_variables to get my variable domains, and I notice this:
If I use AddBoolOr constraint, the domain is calculated correctly:

model = CpModel()

v1 = model.NewIntVar(0, 10, "v1")

lit1 = model.NewBoolVar("lit1")
lit2 = model.NewBoolVar("lit2")

model.Add(v1 == 3).OnlyEnforceIf(lit1)
model.Add(v1 == 5).OnlyEnforceIf(lit2)

model.AddBoolOr([lit1, lit2])

solver = CpSolver()
solver.parameters.fill_tightened_domains_in_response = True
solver.Solve(model)

titened_vars = solver.ResponseProto().tightened_variables
print(titened_vars[v1.Index()].domain)

[3, 3, 5, 5]

If I use AddModuleEquality, it's also calculated correctly:

model = CpModel()

v2 = model.NewIntVar(0, 10, "v2")

model.AddModuloEquality(3, v2, 7)

solver = CpSolver()
solver.parameters.fill_tightened_domains_in_response = True
solver.Solve(model)

titened_vars = solver.ResponseProto().tightened_variables
print(titened_vars[v2.Index()].domain)

[3, 3, 10, 10]

But if I combine them together:

model = CpModel()

v1 = model.NewIntVar(0, 10, "v1")

lit1 = model.NewBoolVar("lit1")
lit2 = model.NewBoolVar("lit2")

model.Add(v1 == 3).OnlyEnforceIf(lit1)
model.Add(v1 == 5).OnlyEnforceIf(lit2)

model.AddBoolOr([lit1, lit2])

v2 = model.NewIntVar(0, 10, "v2")

model.AddModuloEquality(v1, v2, 7)

solver = CpSolver()
solver.parameters.fill_tightened_domains_in_response = True
solver.Solve(model)

titened_vars = solver.ResponseProto().tightened_variables
print(titened_vars[v2.Index()].domain)

I would expect the result to be [3, 3, 5, 5, 10, 10], but I got [3, 10]

I understand that the domain is not the tightest one possible in every situation, but how hard would it be to fix it (if possible) in this situation?

I use these two constraints a lot in my calculations, and knowing the exact domain would speed them up significantly.

PS:

I also just noticed that mod parameter in AddModuloEquality has to be a constant, not a variable. Is it by design?

[Laurent Perron]

Presolve on IntMod is minimal.

You can have a look at PresolveIntMod in cp_model_presolve.cc.

In particular, I am not sure we do the complete domain reduction on the variable when the target is very sparse.

And it does not have to be constant. We just propagate/presolve more in that case (meaning we mostly do nothing in the non constant case).

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f763bb7d-fc20-4ef7-8314-80f471d25a47n%40googlegroups.com.

[Igor Proshkin]

In the PresolveIntMod function, I noticed that you perform domain redaction when both the target and mod variables are fixed. However, in my case, mod is fixed but the target represents a small subset of values in the [0..mod-1] range. I'm wondering if it would be beneficial to apply the same procedure that you use for a fixed target to all values in the target domain iteratively, if the target domain size is smaller than some threshold parameter?

model = CpModel()

v1 = model.NewIntVar(0, 6, "v1")

v2_3 = model.NewIntVar(1, 10, "")
v2_5 = model.NewIntVar(1, 10, "")

v2 = model.NewIntVar(0, 10, "v2_2")
lit3 = model.NewBoolVar("lit3")
lit5 = model.NewBoolVar("lit5")

model.AddModuloEquality(3, v2_3, 7)
model.AddModuloEquality(5, v2_5, 7)

model.Add(v2 == v2_3).OnlyEnforceIf(lit3)
model.Add(v2 == v2_5).OnlyEnforceIf(lit5)
model.AddExactlyOne([lit3, lit5])

model.Add(v1 == 3).OnlyEnforceIf(lit3)
model.Add(v1 == 5).OnlyEnforceIf(lit5)

solver = CpSolver()
solver.parameters.fill_tightened_domains_in_response = True
solver.Solve(model)

titened_vars = solver.ResponseProto().tightened_variables
print(titened_vars[v1.Index()].domain)

print(titened_vars[v2.Index()].domain)

It correctly calculates the vars domains:
[3, 3, 5, 5]

[3, 3, 5, 5, 10, 10]

Regarding the mod parameter, I found out that it needs to be a constant value. When I used a variable, I received an INVALID_MODEL error. It seems that the variable domain should be strictly positive, as I discovered from the logs. It's a little confusing because positive values of the variable should definitely make the model feasible. Would it be better just to reduce the domain to positive numbers in presolve?

[Laurent Perron]

No, I validate models. I do not want to change the model to make it valid. 

It usually hides deeper problems. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7ddbf0d8-1389-4c82-b0ea-2f62d362cbf7n%40googlegroups.com.

[Igor Proshkin]

What about the first point?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPyyUTuqVWrjVEvF3QtdJDyfTnsUL-96H0VLqcGAKQ7bQYY0XA%40mail.gmail.com.

[Laurent Perron]

I have not written the code :-)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAA%3D%3D6MEB4bbm8cfvknVJnqRhgFnJjkp5VrOJBpxjfy6QYyU3kw%40mail.gmail.com.

[Igor Proshkin]

I tried to substitute "targetVar = Var % const" with:
const_i = new_var_i % const, for all i = 0..const-1
and then use AddElement(target, [new_var_i], var)
It gives me a tighter domain sometimes, but not all the time.

I then iterate over all values in the domain ranges, assign my variable a value and verify that model is still feasible.
What is the fastest set of options to verify the model feasibility if I am not interested in the actual solution, only in the model feasibility?

[Laurent Perron]

Feasibility is still NP-Complete.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f5f4035f-50a8-4337-9cdd-6a858429de32n%40googlegroups.com.

[Igor Proshkin]

I understand that. In my case, I am going iteratively check the feasibility of thousands the relatively small models. I am trying to avoid overhead, considering I don't need the actual solutions.