如何在Ortools中定义约束以限制求解器生成的唯一值数量

Got it, let's tackle how to restrict the number of unique values your OR-Tools solver can generate. This is a common requirement, and we can implement it cleanly with helper variables and targeted constraints. Here's a step-by-step breakdown using the CP-SAT solver (the most popular OR-Tools solver for integer programming problems):

Core Approach #

The idea is to track which values are actually used by your decision variables, then cap the count of those used values. Here's the play-by-play:

1. Define your main decision variables: These are the variables you're solving for (e.g., x_0 to x_n).
2. Create boolean helper variables: For every possible value your main variables can take, make a boolean variable that flags whether that value is used by any main variable.
3. Link main variables to helpers: Add constraints that ensure if a main variable takes a specific value, the corresponding helper variable is set to True.
4. Cap the unique value count: Add a constraint that sums all helper variables and limits the total to your desired maximum number of unique values.

Full Code Example #

Let's put this into practice with a concrete Python example. We'll create 5 variables (each ranging from 1 to 10) and restrict them to using at most 3 unique values:

from ortools.sat.python import cp_model

def limit_unique_values():
    # Initialize the model
    model = cp_model.CpModel()
    
    # 1. Define main decision variables
    num_main_vars = 5
    min_possible_val = 1
    max_possible_val = 10
    main_vars = [model.NewIntVar(min_possible_val, max_possible_val, f'var_{i}') for i in range(num_main_vars)]
    
    # 2. Create boolean helper variables for each possible value
    value_used = {}
    for val in range(min_possible_val, max_possible_val + 1):
        value_used[val] = model.NewBoolVar(f'value_{val}_used')
    
    # 3. Link main variables to helper variables
    # Logic: If any main variable equals 'val', then value_used[val] must be True
    for var in main_vars:
        for val in range(min_possible_val, max_possible_val + 1):
            # Equivalent to: var == val → value_used[val] = 1
            # We enforce this by saying: if value_used[val] is False, var cannot equal val
            model.Add(var != val).OnlyEnforceIf(value_used[val].Not())
    
    # 4. Set the maximum number of unique values allowed
    max_unique = 3
    model.Add(sum(value_used.values()) <= max_unique)
    
    # Optional: Add a objective function (e.g., minimize the sum of main variables)
    model.Minimize(sum(main_vars))
    
    # Solve the model
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    # Print results
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        unique_count = solver.Value(sum(value_used.values()))
        print(f"Solution found with {unique_count} unique values:")
        for i, var in enumerate(main_vars):
            print(f"var_{i}: {solver.Value(var)}")
    else:
        print("No feasible solution exists with the given constraints.")

if __name__ == "__main__":
    limit_unique_values()

Key Notes #

• Optimizing for large value ranges: If your variables can take a huge range of values (e.g., 1 to 1000), iterating over every possible value might be inefficient. In that case, you can use dynamic constraints or group values, but for most practical cases, the above method works perfectly.
• Adjusting the constraint: If you want an exact number of unique values instead of a maximum, change the final constraint to model.Add(sum(value_used.values()) == max_unique).
• Alternative constraint formulation: Instead of the OnlyEnforceIf approach, you could also use model.AddImplication(var == val, value_used[val]) (which does the same thing more directly in CP-SAT).

内容的提问来源于stack exchange，提问作者Mike_Male