How to linearize the product of a 2-values-categorical variable and a non-negative continuous variable?

Question

I have been looking for the answer to this question for quite a long time, but couldn't find one. I know the solution in case the multiplication is between a binary (0-1) and a continuous variable, but not in case the multiplication is between a categorial variable (which can be equal to either a constant or another one) and a continuous variable.

################ Definition of the optimization problem ################

The variables of my problem are the following:

• var1 (continuous variable, lower bound = 0, upper bound 5000)
• var2 (continuous variable, lower bound = 0, upper bound 5000)

The constraint is the following:

• var1 + var2 = 3000

The cost function is the following:

• C = var1*coeff1 + var2*coeff2

where coeff2 is a constant (positive float) and coeff1 is a variable that can be equal to x or y (positive floats).

The value of coeff1 is defined as follows:

• If var1>threshold then var1 = x else var1 = y where threshold is a constant

################################################################

The biggest problem here, I think, is that I can't define a variable for coeff1 because in this case the multiplication var1*coeff1 in the cost function would be non-linear.

If coeff1 was a binary variable (0-1), I would have solved the problem in the same way it is explained here Linearization of the product of a binary and non-negative continuous variable. However, my variable is not binary (0-1) but categorical (x-y) and I could not find a way to apply the same theory in my case.

Do you have any idea on how to solve this optimization problem? More generically, do you know if it possible to linearize the multiplication between a continuous and a 2-values-variable?

For those who use python, I recreated this problem using the Pulp package. Here is a sample code with the missing part that I don't know how to define.

import pulp
from pulp import PULP_CBC_CMD

# Create the problem
problem = pulp.LpProblem("Power_Cost_Minimization", pulp.LpMinimize)

# Define the variables
var1 = pulp.LpVariable("var_1", lowBound=0, cat="Continuous")
var2 = pulp.LpVariable("var_2", lowBound=0, cat="Continuous")

# Define the parameters
x = 0.6
y = 0.9
coeff2 = 0.3
threshold = 1000

# Add constraint
problem.addConstraint(var1+var2 == 3000, name = "constraint")

# Part in which I define the values of coeff1, which can be either equal to x or y
"""I need your help here"""

# Define the objective function
problem += var1*coeff1 + var2*coeff2

# Solve the problem
problem.solve(PULP_CBC_CMD(msg=1))

# Print the optimal cost
optimal_cost = pulp.value(problem.objective)
print("Optimal cost =", optimal_cost)

Answer 1

Do you have any idea on how to solve this optimization problem?

First, note that there isn't really such a thing as a categorical variable in LP terminology (that I've heard of). There are semicontinuous variables that take 0 or a fixed value, but pulp seems not to support those, and anyway that isn't quite what you're looking for.

I haven't thought of a better way to do this than two auxiliary variables: one binary, for "is this y?" and the second for the y-contribution to the objective variable v1y, requiring a big-M constraint. Your original formulation was missing your stated upper bounds, and these bounds are important to determine a reasonable M. I show an AffineExpression for coeff1 even though it cannot be used directly in the objective, so that it can be used in objective verification after solve.

Also note that v1y is not given an upper constraint or upper bound. This would need to change if the sense of your problem changes to maximization.

import pulp

x = 0.6
y = 0.9
threshold = 3000

var1 = pulp.LpVariable('var1', cat=pulp.LpContinuous, lowBound=0, upBound=5000)
var2 = pulp.LpVariable('var2', cat=pulp.LpContinuous, lowBound=0, upBound=5000)
is_y = pulp.LpVariable('isy', cat=pulp.LpBinary)
v1y = pulp.LpVariable('v1y', cat=pulp.LpContinuous, lowBound=0)
coeff1 = x*(1 - is_y) + y*is_y  # not usable in objective
coeff2 = 0.3

'''
Objective expands to:
  (x(1 - is_y) + y*is_y)var1 + coeff2*var2
  
Minimum is:
  x*var1 + coeff2*var2

If is_y, then the extra contribution to the objective is
  v1y = (y - x)var1
'''

prob = pulp.LpProblem(name='power_cost_minimization', sense=pulp.LpMinimize)
prob.objective = v1y + x*var1 + coeff2*var2
prob.addConstraint(name='threshold', constraint=var1 + var2 == threshold)

# If is_y, then v1y >= (y - x)var1
# Otherwise v1y >= 0 (via bound)
M = 5000*(y - x)*2
prob.addConstraint(
    name='v1y_linearize',
    constraint=v1y >= (y - x)*var1 - M*(1 - is_y),
)

print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('var1 =', var1.value())
print('var2 =', var2.value())
print('coeff1 =', coeff1.value())
print('coeff2 =', coeff2)
print('coeff1 is based on', 'y' if is_y.value() else 'x')
print('Verify objective:', prob.objective.value(), '==', coeff1.value()*var1.value() + coeff2*var2.value())

power_cost_minimization:
MINIMIZE
1*v1y + 0.6*var1 + 0.3*var2 + 0.0
SUBJECT TO
threshold: var1 + var2 = 3000

v1y_linearize: - 3000 isy + v1y - 0.3 var1 >= -3000

VARIABLES
0 <= isy <= 1 Integer
v1y Continuous
var1 <= 5000 Continuous
var2 <= 5000 Continuous

var1 = 0.0
var2 = 3000.0
coeff1 = 0.6
coeff2 = 0.3
coeff1 is based on x
Verify objective: 900.0 == 900.0

The value of coeff1 is defined as follows: If var1>threshold then var1 = x else var1 = y where threshold is a constant

This is not coherent so I have disregarded it in the solution above.

More generically, do you know if it possible to linearize the multiplication between a continuous and a 2-values-variable?

Yes, certainly: you need to decompose the 2-valued variable (or, really, any discrete muti-valued variable) into an affine expression that is a function of an integral variable. With only two values, this is expressed as a linear function of a binary variable. Details will vary based on where the expression needs to be used and what the optimisation sense is.