python - 如何创建 "at least n"约束？

Question

我是约束编程的新手，正在尝试弄清楚如何进行“至少 n”约束。

例如，我有 int 变量 x、y 和 z，它们都在 0 到 5 的范围内。

现在我想要所有解决方案，其中至少有 2 个变量在 2 和 3 之间。

所以类似于“给定条件的总和 >= 2”

我如何在 python 中执行此操作，最好是使用 Google 的 OR-Tools？

谢谢

Answer 1

from ortools.sat.python import cp_model
import collections


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

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        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=' ')
                    break
        print()

    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