0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ Thanks Rob, I realize I'm missing the link constraints. I was reading up on Big M Constraints yesterday and I just didn't know how relate the 10% to minimum 3 items, to the revenue. I'll try your method tonight and see where that takes me $\endgroup$ Commented Sep 1, 2020 at 23:19
  • $\begingroup$ Thanks for the edit, I just noticed it. What does j stand for if you don't mind me asking. $\endgroup$ Commented Sep 2, 2020 at 2:37
  • 1
    $\begingroup$ @dassouki $\sum_j = \sum_{j=1}^n$ $\endgroup$ Commented Sep 2, 2020 at 3:23
  • $\begingroup$ So would this be correct just to make sure I'm on the same page as you x = 1, 2, 3, 4 y = 0 or 1 y = 1, 0, 1, 1 M = 1000, 1000, 1000, 1000 1: 0.1 (1 + 2 + 3 + 4) - 1 <= (0.1 * (1000 + 1000 + 1000 + 1000) * (1 - 1) 2: 0.1 (1 + 2 + 3 + 4) - 2 <= (0.1 * (1000 + 1000 + 1000 + 1000) * (1 - 0) 3: 0.1 (1 + 2 + 3 + 4) - 3 <= (0.1 * (1000 + 1000 + 1000 + 1000) * (1 - 1) 4: 0.1 (1 + 2 + 3 + 4) - 4 <= (0.1 * (1000 + 1000 + 1000 + 1000) * (1 - 1) $\endgroup$ Commented Sep 2, 2020 at 16:41
  • 1
    $\begingroup$ If $x_2=2$, then $y_2$ cannot be $0$. $\endgroup$ Commented Sep 2, 2020 at 17:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.