整数与二进制变量乘积的线性化及PuLP实现约束疑问

Great catch! That last constraint z ≥ i is definitely a mistake — it would create impossible contradictions when the binary variable b is 0, and it’s redundant when b is 1. Let’s break this down clearly:

Why the Final Constraint Is Wrong #

Let’s split into the two possible states of binary variable b:

1. When b = 1:
   The product ib = i*1 = i, so we need z = i. The first three constraints already enforce this:

   • z ≤ I*1 = I (redundant, since i ≤ I by definition)
   • z ≤ i
   • z ≥ i - (1-1)*I = i
     Combining z ≤ i and z ≥ i forces z = i — the fourth constraint z ≥ i adds nothing here.

2. When b = 0:
   The product ib = i*0 = 0, so we need z = 0. But the fourth constraint z ≥ i would require z ≥ i ≥ 0, while the first constraint z ≤ I*0 = 0 forces z ≤ 0. This creates a contradiction unless i = 0, which defeats the purpose (since i can be any integer between 0 and I).

Correct Linearization Constraints #

You should discard the z ≥ i constraint. The correct set of constraints to replace z = i*b is:

• z ≤ I*b
• z ≤ i
• z ≥ i - (1 - b)*I
• z ≥ 0

The z ≥ 0 constraint ensures that when b = 0, z can’t be negative (which aligns with ib = 0 and i ≥ 0).

PuLP Implementation Example #

Here’s how you’d code this in PuLP to avoid mistakes:

import pulp

# Initialize the problem
prob = pulp.LpProblem("Linearize_ib_Product", pulp.LpMinimize)

# Define variables
i = pulp.LpVariable("i", lowBound=0, upBound=5, cat='Integer')  # Example upper bound I=5
b = pulp.LpVariable("b", cat='Binary')
z = pulp.LpVariable("z", lowBound=0, cat='Integer')  # z represents the product i*b

# Add correct linearization constraints
I = 5  # Upper bound of integer variable i
prob += z <= I * b
prob += z <= i
prob += z >= i - (1 - b) * I
prob += z >= 0

# Add your objective function and other problem-specific constraints here
# prob += [your objective/constraints]

# Solve the problem
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# Print results to verify
print(f"i = {pulp.value(i)}")
print(f"b = {pulp.value(b)}")
print(f"z = {pulp.value(z)}")
print(f"i*b = {pulp.value(i)*pulp.value(b)}")

This code will correctly enforce z = i*b for all valid values of i and b.

内容的提问来源于stack exchange，提问作者zongwang.zhang