CODEWITHSUNDEEP
linear-programmingconstraint-programmingor-tools
igor milanovic
igor milanovic

Reputation: 151

Getting all solutions in Google or-tools

I have a linear problem of finding all solutions that meet all constraints. For example my variables are = [0.323, 0.123, 1.32, 6.3...] Is it possible to get for example top 100 solutions sorted by fitness(maximization/minimization) function?

Upvotes: 1

Views: 2349

Answers (2)

mattmilten
mattmilten

Reputation: 6706

If you can define a fitness function as you suggested, then you might first want to solve the LP that maximizes this function. Afterwards you can include an objective cutoff that forces your second solution to be slightly worse than the first. You can implement this by introducing a cut that is your objective function with the right hand side of optimal value - epsilon.

Of course, this will not give you all (basic) solutions, but you might discover which variables are always at the same value or how much variance there is between the different solutions.

Upvotes: 0

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

In a continuous LP enumerating different solutions is a difficult concept. E.g. consider max x, s.t. x <= 1. Obviously x=1, x=0.99999 are solutions and so are the infinite number of solutions in between. We could enumerate "corner solutions" (or basic solutions). See here for an example. Such a scheme could be adapted to find the first 100 different corner points sorted by the objective. For models with discrete variables, many constraint programming solvers will give you the possibility to find many solutions.

Upvotes: 2

Related Questions