By Christine

2019-08-13 20:08:06 8 Comments

I am new to constraint programming and try to figure out how to do a "at least n" constraint.

For example I have int variables x, y and z all within a range of 0 to 5.

Now I want all solutions in which at least 2 of the variables are between 2 and 3.

So something like a "sum of given conditions >= 2"

How would I do this in python and ideally with Google's OR-Tools?



@Laurent Perron 2019-08-14 00:28:55

from ortools.sat.python import cp_model
import collections

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        self.__variables = variables
        self.__num_vars = len(variables)
        self.__num_values = len(variables[0])
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for var in range(self.__num_vars):
            for value in range(self.__num_values):
                if self.BooleanValue(self.__variables[var][value]):
                    print('var[%i]=%i' % (var, value), end=' ')

    def solution_count(self):
        return self.__solution_count

num_vars = 3
max_values = 5

model = cp_model.CpModel()
vars = collections.defaultdict(list)

for var in range(num_vars):
    for value in range(max_values + 1):
        vars[var].append(model.NewBoolVar('x_%i_%i' % (var, value)))

# Exactly one value per variable
for var in range(num_vars):
    model.Add(sum(vars[var]) == 1)

# At least 2 between 2 and 3
model.Add(sum(vars[var][2] for var in range(num_vars)) +
          sum(vars[var][3] for var in range(num_vars)) >= 2)

# Enumerate all solutions
solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(vars)
status = solver.SearchForAllSolutions(model, solution_printer)

print('Status = %s' % solver.StatusName(status))
print('Number of solutions found: %i' % solution_printer.solution_count())


var[0]=3      var[1]=2      var[2]=0 
var[0]=3      var[1]=2      var[2]=5 
var[0]=3      var[1]=2      var[2]=4 
var[0]=3      var[1]=2      var[2]=1 
var[0]=3      var[1]=2      var[2]=3 
var[0]=3      var[1]=0      var[2]=3 
var[0]=3      var[1]=1      var[2]=3 
var[0]=3      var[1]=5      var[2]=3 
var[0]=3      var[1]=4      var[2]=3 
var[0]=3      var[1]=4      var[2]=2 
var[0]=3      var[1]=0      var[2]=2 
var[0]=3      var[1]=1      var[2]=2 
var[0]=3      var[1]=2      var[2]=2 
var[0]=3      var[1]=5      var[2]=2 
var[0]=3      var[1]=3      var[2]=2 
var[0]=3      var[1]=3      var[2]=4 
var[0]=3      var[1]=3      var[2]=5 
var[0]=3      var[1]=3      var[2]=1 
var[0]=3      var[1]=3      var[2]=0 
var[0]=3      var[1]=3      var[2]=3 
var[0]=5      var[1]=3      var[2]=3 
var[0]=1      var[1]=3      var[2]=3 
var[0]=4      var[1]=3      var[2]=3 
var[0]=2      var[1]=3      var[2]=3 
var[0]=0      var[1]=3      var[2]=3 
var[0]=2      var[1]=3      var[2]=0 
var[0]=2      var[1]=3      var[2]=5 
var[0]=2      var[1]=3      var[2]=4 
var[0]=2      var[1]=3      var[2]=1 
var[0]=2      var[1]=3      var[2]=2 
var[0]=5      var[1]=3      var[2]=2 
var[0]=1      var[1]=3      var[2]=2 
var[0]=4      var[1]=3      var[2]=2 
var[0]=0      var[1]=3      var[2]=2 
var[0]=0      var[1]=2      var[2]=2 
var[0]=5      var[1]=2      var[2]=2 
var[0]=4      var[1]=2      var[2]=2 
var[0]=1      var[1]=2      var[2]=2 
var[0]=2      var[1]=2      var[2]=2 
var[0]=2      var[1]=0      var[2]=2 
var[0]=2      var[1]=1      var[2]=2 
var[0]=2      var[1]=5      var[2]=2 
var[0]=2      var[1]=4      var[2]=2 
var[0]=2      var[1]=2      var[2]=1 
var[0]=2      var[1]=2      var[2]=0 
var[0]=2      var[1]=2      var[2]=5 
var[0]=2      var[1]=2      var[2]=4 
var[0]=2      var[1]=2      var[2]=3 
var[0]=2      var[1]=0      var[2]=3 
var[0]=2      var[1]=1      var[2]=3 
var[0]=5      var[1]=2      var[2]=3 
var[0]=4      var[1]=2      var[2]=3 
var[0]=1      var[1]=2      var[2]=3 
var[0]=2      var[1]=5      var[2]=3 
var[0]=2      var[1]=4      var[2]=3 
var[0]=0      var[1]=2      var[2]=3 
Status = OPTIMAL
Number of solutions found: 56

@sal 2019-08-13 20:19:32

Assuming you have these conditions

x = 2.5
y = 4
z = 2.9

then you could build a list of values, and then apply lambda, map and sum to find things out. For example:

# Create the list of values
values = [x, y, z]

# Apply a lambda to each element of the list, checking if they
# are within [2,3]. This would return a boolean, so I am translating
# those to 1 and 0
ones_or_zeroes = map(lambda x: 1 if 2<=x<=3 else 0, values)

# Check condition of how many matched the condition:
condition = sum(ones_or_zeroes)

It can be of course compacted as:

if sum(map(lambda x: 1 if 2<=x<=3 else 0, values)) >= 2:
    # then at least 2 variables match the costraint

Related Questions

Sponsored Content

11 Answered Questions

[SOLVED] Calling a function of a module by using its name (a string)

  • 2008-08-06 03:36:08
  • ricree
  • 600498 View
  • 1480 Score
  • 11 Answer
  • Tags:   python object

37 Answered Questions

[SOLVED] How to pair socks from a pile efficiently?

21 Answered Questions

[SOLVED] Does Python have a ternary conditional operator?

31 Answered Questions

[SOLVED] "Least Astonishment" and the Mutable Default Argument

25 Answered Questions

[SOLVED] How can I safely create a nested directory?

29 Answered Questions

[SOLVED] What does if __name__ == "__main__": do?

37 Answered Questions

[SOLVED] How do I check whether a file exists without exceptions?

44 Answered Questions

10 Answered Questions

[SOLVED] Does Python have a string 'contains' substring method?

38 Answered Questions

[SOLVED] What does the "yield" keyword do?

Sponsored Content