使用Pulp CBC求解器能否为约束设置优先级？生产排程技术问询

Hey Kevin, great question! When you need to enforce constraint priorities in linear programming—where high-priority constraints must be fully satisfied before even considering lower-priority ones—there are two practical approaches you can implement with PuLP and the CBC solver. Let’s break them down with code examples tailored to your production scheduling problem.

1. Hierarchical Goal Programming (Strict Priority Enforcement) #

This method solves your problem in layers: first, we find a feasible solution that satisfies all high-priority constraints (1,2,3,4). Then, we use that feasible region as a starting point to minimize violations of low-priority constraints (5,6). This guarantees high-priority constraints are never violated, even if time runs out.

Step-by-Step Implementation #

First, define and solve the high-priority only problem:

import pulp as lp

# Initialize variables (-1, 0, 1 integer values)
n_rows = 3
n_columns = 10
v_list = []
for r in range(n_rows):
    row = [lp.LpVariable(f"v_{r}_{c}", lowBound=-1, upBound=1, cat='Integer') for c in range(n_columns)]
    v_list.append(row)
t = 1  # Assumes constraint 1/2 refers to absolute value ≤1 (matches variable bounds)

# Layer 1: Solve for high-priority constraints only
high_prob = lp.LpProblem("High_Priority_Constraints", lp.Minimize)

# Add high-priority constraints
# Constraint 1 & 2: Absolute value bounds (explicitly added here)
for r in range(n_rows):
    for c in range(n_columns):
        v = v_list[r][c]
        high_prob += v <= t
        high_prob += -v <= t

# Constraint 3: Each row sum ≤2
for r in range(n_rows):
    high_prob += lp.lpSum(v_list[r]) <= 2

# Constraint 4: Sum of rows a + b ≤2
high_prob += lp.lpSum(v_list[0] + v_list[1]) <= 2

# Dummy objective to find feasible solution (minimize total variable sum)
high_prob += lp.lpSum([v for row in v_list for v in row])

# Solve with time limit (adjust to your needs)
high_prob.solve(lp.PULP_CBC_CMD(timeLimit=10))

# Check if high-priority constraints are feasible
if lp.LpStatus[high_prob.status] != 'Optimal':
    print("Error: High-priority constraints are infeasible!")
else:
    # Layer 2: Minimize violations of low-priority constraints within high-priority feasible region
    low_prob = lp.LpProblem("Low_Priority_Optimization", lp.Minimize)

    # Add violation variables for low-priority constraints
    # Constraint 5: Each column sum ≤2
    col_over = [lp.LpVariable(f"col_over_{c}", lowBound=0) for c in range(n_columns)]
    for c in range(n_columns):
        col_sum = lp.lpSum([v_list[r][c] for r in range(n_rows)])
        low_prob += col_sum - 2 <= col_over[c]

    # Constraint 6: Sum of consecutive variables per row ≤1 (adjust loop if your "continuous" definition differs)
    cont_over = []
    for r in range(n_rows):
        for c in range(n_columns - 1):
            var = lp.LpVariable(f"cont_over_{r}_{c}", lowBound=0)
            cont_over.append(var)
            low_prob += lp.lpSum([v_list[r][c], v_list[r][c+1]]) - 1 <= var

    # Re-add all high-priority constraints to lock in feasible region
    for r in range(n_rows):
        for c in range(n_columns):
            v = v_list[r][c]
            low_prob += v <= t
            low_prob += -v <= t
    for r in range(n_rows):
        low_prob += lp.lpSum(v_list[r]) <= 2
    low_prob += lp.lpSum(v_list[0] + v_list[1]) <= 2

    # Objective: Minimize total violations of low-priority constraints
    low_prob += lp.lpSum(col_over) + lp.lpSum(cont_over)

    # Solve with warm start using high-priority solution to speed up
    low_prob.solve(lp.PULP_CBC_CMD(timeLimit=10, warmStart=True))

    # Extract results
    for r in range(n_rows):
        row_vals = [v.varValue for v in v_list[r]]
        print(f"Row {r} values: {row_vals}")

2. Weighted Penalty Method (Single Problem Solve) #

This approach turns constraint violations into penalty terms in your objective function. Assign extremely large weights to high-priority violations, so the solver will prioritize satisfying those constraints over optimizing your original objective or low-priority constraints.

Implementation Code #

import pulp as lp

# Initialize variables
n_rows = 3
n_columns = 10
v_list = []
for r in range(n_rows):
    row = [lp.LpVariable(f"v_{r}_{c}", lowBound=-1, upBound=1, cat='Integer') for c in range(n_columns)]
    v_list.append(row)
t = 1

# Define penalty weights: High-priority violations get massive weight
HIGH_PENALTY_WEIGHT = 10**6  # Must be large enough to outweigh any objective gain
LOW_PENALTY_WEIGHT = 1

prob = lp.LpProblem("Prioritized_Scheduling", lp.Minimize)

# Add violation variables for all constraints
# High-priority violations
row_over = [lp.LpVariable(f"row_over_{r}", lowBound=0) for r in range(n_rows)]
ab_over = lp.LpVariable("ab_over", lowBound=0)

# Low-priority violations
col_over = [lp.LpVariable(f"col_over_{c}", lowBound=0) for c in range(n_columns)]
cont_over = []
for r in range(n_rows):
    for c in range(n_columns - 1):
        cont_over.append(lp.LpVariable(f"cont_over_{r}_{c}", lowBound=0))

# Add constraints with violation variables
# Constraint 1 & 2 (absolute value)
for r in range(n_rows):
    for c in range(n_columns):
        v = v_list[r][c]
        prob += v <= t
        prob += -v <= t

# Constraint 3: Row sum ≤2 (allow over via row_over)
for r in range(n_rows):
    prob += lp.lpSum(v_list[r]) - row_over[r] <= 2

# Constraint 4: a+b row sum ≤2 (allow over via ab_over)
prob += lp.lpSum(v_list[0] + v_list[1]) - ab_over <= 2

# Constraint 5: Column sum ≤2 (allow over via col_over)
for c in range(n_columns):
    prob += lp.lpSum([v_list[r][c] for r in range(n_rows)]) - col_over[c] <= 2

# Constraint 6: Consecutive variable sum ≤1 (allow over via cont_over)
for r in range(n_rows):
    for c in range(n_columns - 1):
        prob += lp.lpSum([v_list[r][c], v_list[r][c+1]]) - cont_over[r*(n_columns-1)+c] <= 1

# Build objective function: Original objective + weighted penalties
original_obj = 2*lp.lpSum(v_list[0]) + 2*lp.lpSum(v_list[1]) + 4*lp.lpSum(v_list[2])
high_penalty = HIGH_PENALTY_WEIGHT * (lp.lpSum(row_over) + ab_over)
low_penalty = LOW_PENALTY_WEIGHT * (lp.lpSum(col_over) + lp.lpSum(cont_over))

prob += original_obj + high_penalty + low_penalty

# Solve with time limit
prob.solve(lp.PULP_CBC_CMD(timeLimit=20))

# Check if high-priority constraints are satisfied (violation variables should be 0)
print("High-priority violation checks:")
for r in range(n_rows):
    print(f"Row {r} over: {row_over[r].varValue}")
print(f"a+b row over: {ab_over.varValue}")

Key Notes & Tradeoffs #

• Hierarchical Method: Guarantees high-priority constraints are met, even if time runs out mid-solve. Requires solving two problems, but the first solve is fast since it only handles critical constraints.
• Weighted Penalty Method: Solves in one step, but you must choose penalty weights carefully. If the high-priority weight isn’t large enough, the solver might violate those constraints to improve the original objective. Test weights by checking if violation variables for high-priority constraints are zero in the final solution.
• Variable Bounds: Since your variables are restricted to -1, 0, 1, make sure to set cat='Integer' and lowBound=-1, upBound=1 when defining LpVariable—this will speed up the solver compared to unrestricted integers.

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