Best way to generate multiple optimal/close-to-optimal solutions with CP-SAT

[Paul]

Dear all,

I'm working on an optimization problem using CP-SAT (Python API). I've found it very effective to converge towards an optimal solution to my problem.

For the sake of my project, I'd like to get several close-to-optimal solutions (say about 10), and I'm struggling to find an efficient way to do that with CP-SAT.

As I couldn't find a parameter to do that, I came up with the idea of :

 - Running the solver a first time, keeping track of the optimum

 - Adding this optimum as a constraint for the model

 - Run the solver again, this time with the SearchForAllSolutions function

However, running the solver with this additionnal constraint is way longer. Even without using SearchForAllSolutions but sticking to Solve, the solver will take much longer to find one solution than it did to find one when trying to optimize in the first place.

Am I going in the right direction ? Is there a better way to get several good enough solutions for a problem using CP-SAT ?

Would love any insight on this question !

Regards,

[Priidik Vilumaa]

Hi,

what we do is run the model normally, and record intermediate solutions in the callback. Then later get, say, best 10.

Something like:

```

class MyCallback():

...

def on_solution_callback(self):

self.solutions.append(solution)

...

solver.Solve(model, callback)

...

You can find the callback examples somewhere in Github or guides, I bet.

The advantage of this method is that you'll only run the optimization once. But if your optimization is too fast :) , then you'll barely get any solutions, and the difference in quality of the top 10 might be quite big.

Another idea is to perturb the objective coefficients. Optimize towards something in run1, towards something else in run2. This might do well for you, if your single run is fast.

I'm sure somebody will come up with more tricks.

Best,

Priidik

[Paul]

Hi Priidik,

That's the solution I went for so far, but my problem as you said is that the quality of the top 10 quickly goes down.

Typically, say my optimum is ObjectiveValue = 50, I know that there are more than one solution that matches this objective value, but I can't figure out a way to get a couple different ones out of them :/

Also, I've noticed the solutions I get with this kind of callback will often be very similar, the better ones being slightly tweaked versions of the others to enhance the objective value, while I'd be more interested in obtaining diverse solutions.

I'll be exploring the objective perturbation idea, although it brings me back to the issue of running the solver a considerable amount of time.

I've been thinking as well, could hinting be an option to guide my model into several directions ? Not sure I'm comfortable enough with the underlying mecanism :/

Thanks for your answer, have a nice day !

Paul

[Priidik Vilumaa]

Hi,

hints might work, although I wouldn't say I've had any real success with them ever. If you manage to take some key decisions of the problem (preferably 0/1 vars) and constrain them to be this way or that way for a particular run, then you might be able to manually explore a more diverse region get nice results from each subregion. 

Another idea is to take your first solution, and the constrain the solution to be "reasonably different" in the next run. Keep building the set of prior solutions and always ask for a "reasonably different one" in the new run.

Best,

Priidik

[Paul]

Thanks for taking the time to provide me with ideas, I'll see the results I can get !

In case anyone comes around, I'm still keen on more information or ideas, also I'll try to give an update once I'm done, on what I've found the most efficient.

Cheers

[Frederic Didier]

Depending on your problem, you might get diverse solution with multiple run by changing the random seed and permuting the variable order: 

random_seed:123,permute_variable_randomly:true

I don't think you can avoid calling the solver multiple times.

Enumerating all solutions might be an option, but only if your problem is small, and there are not too many of them.

--
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/5abfc713-b28a-447d-89a9-d889607f930en%40googlegroups.com.