I'm trying to find an existing algorithm for the following problem:

i.e, let's say we have 3 variables, x, y, z (all must be integers). I want to find values for all variables that MUST match some constraints, such as x y<4, x<=50, z>x, etc.

In addition, there are extra POSSIBLE constraints, like y>=20, etc. (same as before). The objective function (which i'm intrested in maximizing its value) is the number of EXTRA constraints that are met in the optimal solution (the "must" constraints the fact that all values are integers, is a demand. without it, there's no valid solution).

CodePudding user response：

If using OR-Tools, as the model is integral, I would recommend using CP-SAT, as it offers indicator constraints with a nice API.

The API would be:

b = model.NewBoolVar('indicator variable')
model.Add(x   2 * y >= 5).OnlyEnforceIf(b)

...

model.Maximize(sum(indicator_variables))

To get maximal performance, I would recommend using parallelism.

solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8  # or more on a bigger computer
status = solver.Solve(model)