CODEWITHSUNDEEP
linear-programmingpulp
cheesus
cheesus

Reputation: 1181

PuLP MILP constraint: at least one variable must be below 0

I'm trying to add a constraint to a MILP problem with the purpose of making sure, that at least one of the decision variables is below 0. Is there a way to do this?

Upvotes: 0

Views: 1536

Answers (1)

abc
abc

Reputation: 11929

Let x_1, x_2,...,x_n be your variables.
You want that the value of at least one of the x variables is below zero. You can achieve this in the following way.

Let's not introduce N binary variables y_1, y_2,...,y_n, one for each of the x variables.
You add one constraint for each of the n variables as follows.

x_1 ≤ M * (1 - y_1)
x_2 ≤ M * (1 - y_2)
...
x_n ≤ M * (1 - y_n)
y_1 + y_2 + ... + y_n ≥ 1

where M is a large constant. With the last constraint you impose that at least one y_i variables has value y_i = 1, that leads to x_i <= 0 for the corresponding x_i.

An example with pulp is as follows.

import pulp 

N = 10
M = 1000

x = pulp.LpVariable.dicts("x", range(N), cat=pulp.LpInteger, upBound=10)    
y = pulp.LpVariable.dicts("y", range(N), cat=pulp.LpBinary)    

# Note the UB on the x variables in order not to make the problem unbounded
prob = pulp.LpProblem("example", pulp.LpMaximize)

prob += pulp.lpSum(x[i] for i in range(N))

for i in range(N):
   prob += x[i] <= M * (1 - y[i])

prob += pulp.lpSum(y[i] for i in range(N)) >= 1

prob.solve()

for i in range(N):
    print(x[i], x[i].varValue)

which outputs:

x_0 10.0
x_1 10.0
x_2 10.0
x_3 10.0
x_4 10.0
x_5 10.0
x_6 10.0
x_7 10.0
x_8 10.0
x_9 0.0

Upvotes: 2

Related Questions