Linear programming - Non-Mutual Positivity Constraint

Question

I am attempting a maximisation problem subject to various constraints.

i.e. max y = x1 + x2 + x3 + .... + xn

where each xi is a vector of values over time: x1 = (x11, x12, x13,...)

Some of the constraints state that specific values of xit cannot be positive in the same time period.

i.e. if(x1t > 0), x2t = 0; if(x2t > 0), x1t = 0

For context, the constraint is equivalent to "maximise the revenue of a shop, but you cant sell product A and B on the same day"

How do I go about formulating an LP model in Excel (using solver) to solve this.

Answer 1

This is called a complementarity constraint. One way of modeling this is:

x(1,t) * x(2,t) = 0
x(i,t) ≥ 0

However, this is nonlinear (and in a somewhat nasty way). A linear approach, using an extra binary variable δ can look like:

x(1,t) ≤ UP(1,t) * δ(t)  
x(2,t) ≤ UP(2,t) * (1-δ(t))
x(i,t) ∈ [0,UP(i,t)]     'UP is an upper bound on x'
δ(t) ∈ {0,1}             'δ is a binary variable'