How to multiply multiple variables in a linear programming problem?

Question

I was trying to formulate a problem as an integer linear programming problem.

I have binary variables x[i] and y[i] for i in [1,n] that are constrained to have a value of 0 or 1.

I want to make the following constraint: sum(x[i] * y[i] for i in array) <= 100

I want to be able to multiply the x[i] and y[i] together but then this becomes a quadratic equation (not linear).

Is there any way I could do this? I'm pretty new to linear programming so I would really appreciate any help!!

in which programming language will you implement the answer? — develarist
– develarist, Commented Dec 1, 2020 at 19:53

Erwin Kalvelagen · Accepted Answer · 2020-12-02 00:09:16Z

3

First a bit of theory. We can linearize

z = x*y

for binary variables x,y,z by:

z <= x
z <= y
z >= x+y-1

In your specific case, we can apply this as follows:

sum(i, z[i]) <= 100 
z[i] >= x[i] + y[i] - 1

where z[i] is an extra binary variable. We don't need the <= constraints z[i] <= x[i], z[i] <= y[i]. We can relax z[i] to be continuous between 0 and 1 which sometimes can help a bit in performance.

Note that the presence of binary variables no longer makes this an LP, but rather this is a MIP model.

edited Dec 2, 2020 at 0:09

answered Nov 30, 2020 at 2:14

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to multiply multiple variables in a linear programming problem?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related