Searching for solutions close to optimal

[Maxim Mikhaylov]

I am using CP-SAT solver to solve a scheduling problem. So far, I've been coming up with lots of hard constraints and searching for all feasible solutions using:

solver = ortools.sat.python.cp_model.CpSolver()
solver.SearchForAllSolutions(model, callback)

I decided to start adding soft constraints by defining penalties and setting the model's objective to minimize those penalties. I refer a lot to examples/python/shift_scheduling_sat.py when adding such constraints. Since I specify minimization objective, I can't use solver.SearchForAllSolutions(model, callback) anymore and have to use solver.SolveWithSolutionCallback(model, callback) that searches for a single optimal solution.

My question is: is it possible to search for many optimal solutions? The way I currently define soft constraints, there is still quite a few solutions with an objective function value of zero. Even if there is only one optimal solution, is it possible to search for many solutions that are close to optimal within some delta?

My application requires me to generate many alternative solutions that are "good" (there's many feasible solutions but some are better than others). When searching for all feasible solution without defining any soft constraints, there is sometimes way too many solutions that are hard to compare to each other (finding the "better" ones). On the other extreme, after defining some soft constraints I can only search for a single optimal solution. Is there some middle ground where I can search for, let's say, 50 solutions that are close to optimal?

[Xiang Chen]

You could solve once and then search for all solutions after

model.Add(objective == result)

or 

model.Add(result-delta <= objective)

model.Add(objective <= result+delta)

--
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/1111ab01-acad-4390-9135-f1371f536115%40googlegroups.com.

[Maxim Mikhaylov]

Thanks! I am posting details on how I made this work so that anyone who has the same problem in the future can see how I did it.

I had to change the type of the objective to make this work. Previously, my objective was defined as a _SumArray, like here, which resulted in TypeError: Not an linear expression when adding a constraint that you suggested.

I redefined the objective as _ScalProd; i.e. objective = cp_model.LinearExpr.ScalProd(cost_variables, cost_coefficients)

Here's what I had at the end:

# search for best value of objective function
solver.SolveWithSolutionCallback(model, callback)
result = int(solver.BestObjectiveBound())

# remove the minimization objective from the model to make SearchForAllSolutions work
model.Proto().ClearField('objective')

# search for all solutions within some delta from the best solution objective value
delta = 5
model.Add(objective <= result + delta)
solver.SearchForAllSolutions(model, callback)

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

[Xiang Chen]

A small comment:

result = int(solver.BestObjectiveBound()) 

Should actually be:

result = round(solver.ObjectiveValue())

as sometimes the objective is returned as 12.999999 instead of 13 for example.

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/daabc9a8-bed6-48b5-892d-e3aef92fde4e%40googlegroups.com.