Mixed Integer / Binary Linear Programming: interactions of multiple variables in a model.

Question

I'm been struggling to solve a part of a model I'm working on. For simplicity's sake, let's assume that the model has to:

• pick i out of n items. x_i to x_n. to minimize cost c
• revenue r per item is set at a constant where each product has a certain amount of revenue associated with it.
• for the items the model picks, the minimum it can use is 10% of total investment.
• only pick up to 3 items of the population.

If n = 100, and the model decides to pick x1, x3, and x6 then the some of the constraints are:

total = x1 + x3 + x6 (total = sum f xi)
x1 >= 10% * total for i in range: xi >= .1 * total
x3 >= 10% * total
x6 >= 10% * total

let's assume that y_i is the Binary variable used to identify which item is selected. The constraint there would be:

Sum of y_i to y_n <= 3

Revenue constraint:

r == ri * y_i (the problem with this is it doesn't take not account
all of the revenues for all of the items rather it just takes the revenue
for one item based not eh binary and we can't multiple to variables by each other)

The model is a cost minimization where each item x has a cost associated to it c_1 to c_n so the objective function becomes min sum of ci x x_i

I am struggling to solve this. Any thoughts?

Answer 1

I'm not sure where revenue fits into the business problem. If your objective is to minimize total cost $\sum_i c_i x_i$, maybe you want to impose a lower bound on total revenue? If so, the constraint is $\sum_i r_i y_i \ge R$.

You are missing constraints that link $x$ and $y$. You want to enforce $x_i > 0 \implies y_i=1$. If $M_i$ is a (small) upper bound on $x_i$, you can do that via linear "big-M" constraints $x_i \le M_i y_i$.

You also want to enforce $y_i = 1 \implies x_i \ge 0.1\sum_j x_j$, which you can do via additional linear big-M constraints $0.1\sum_j x_j - x_i \le (0.1\sum_j M_j) (1 - y_i)$.