Product of Two Variable in Integer Programming Objective

Question

I'm trying to create an optimization problem in the following form using lpSolveAPI.

max 10(x₁ + x₂) * S₁ + 20(x₁ + x₂) * S₂

sub.to. S₁ + S₂ <= 1 # These are binary variables.

2 * x₁ + 3 * x₂ <= 30

1 * x₁ + 2 * x₂ <= 10

x₁ & x₂ are integers.

My problem is how to create this multiplicative variable? All the examples I'm coming across variables are linearly assigned. As mentioned earlier I'm using lpSolveAPI from R.

Answer 1

It sounds like you have a sum like (10*x1 + 10*x2) * S1 + (20*x1 + 20*x2) * S2 + ... with binary S1, S2, ... and you are trying to maximize this term.

One way to do this would be to define variables V1, V2, ..., with one for each of the S1, S2, ... variables. You can then add the following constraints:

V1 <= 10*x1 + 10*x2
V1 <= M*S1
V2 <= 20*x1 + 20*x2
V2 <= M*S2
...

Here, M is a large positive constant. No matter the value of S1, the variable V1 must satisfy V1 <= 10*x1 + 10*x2. If S1=0, then we additionally have V1 <= 0. If S1=1, then we additionally have V1 <= M. However if M is large enough, then this will never be a binding constraint.

Now, we can replace the objective with:

max V1 + V2 + ...

Since we are maximizing, the V variables will take value 0 when their corresponding S variable is not set, and it will take the value you want in the objective otherwise.