Enumerate all solutions to a subset of variables

[olarozenfeld]

Additional context: https://groups.google.com/g/or-tools-discuss/c/JKiZLEzEo9E

I'm using CP-SAT to enumerate all feasible solutions, however in my problem there are variables that I "care about" and others are just "helper variables". A toy example: x,y,z with the constraint x=y, but I only want to enumerate all possible assignments to {x,y}.
So far, I found two ways to do that:

1. Run Solve(cp_model) in a loop, adding an Or constraint after every solution to fix at least one literal different to the current solution.
2. Run with the NewFeasibleSolutionObserver and iterate over all full assignments, computing a hash key for each one based on my key variables and thus merging the equivalent assignments manually.

Both of these are quite inefficient, for different reasons. On the problem I'm trying to solve, both these approaches proved effectively infeasible, no matter how much I tried reducing the problem space.

I would like to amend the solver to allow adding key_variables in solver parameters, and then having NewFeasibleSolutionObserver only iterate over different assignments to these key variables. From the or-tools-discuss thread, it looks like the feature would be helpful to a few other users as well.

I'm thinking of trying to implement this myself, and I would really appreciate any tips. Does this sound like a good idea? Is this feasible? Pointers to key sections of the code?

Thank you!

[lperron]

Same persons reading the post here, and having read it there :-)

[olarozenfeld]

Turned out it was actually very simple to do: https://github.com/google/or-tools/compare/stable...olarozenfeld:key-vars?expand=1
Should I add tests and send a PR? On my examples it reduces the solve time by a factor of ~7.5 (compared to option 1).

[lperron]

Thanks for the investigation. I do not want to add variable information in the parameters. So we need to think about it.

[olarozenfeld]

Agreed, I also thought putting it in the CpModelProto will be more consistent with the current design (similar to how you put solution hints there), I just wasn't sure how to stitch it through (probably make it a small class and use GetOrCreate on the Model? Maybe there already is a convenient place I missed?) Another thought: if I put in on the CpModelProto, I'd probably need to generalize it to all the things that solve a CpModel, in particular have it work on integer variables...
In any case, I solved my problem (I just use my fork), checking this in only has a purpose of helping others with the same problem, so likely very low priority for now.

[Ar-Kareem]

This was asked 3 years ago so I'm extremely hopeful that there is some solution I can try.

I'm also facing this problem, currently I'm using option 1 but it's way too costly and I can tell without trying that option 2 won't work either.

I would greatly appreciate any help here.

I also want to add that I'm extremely thankful for the or-tools team.