It's hard to describe this constraints. Please check this:
It is a selection problem.
| Item Name | Brand | Value | Price |
|---|---|---|---|
| item 1 | A | 0.1 | 0.2 |
| item 2 | B | 0.2 | 0.3 |
| item 3 | A | 0.1 | 0.3 |
We want to select several items from 1000 items satisfying this constraint:
The proportion of items with weighted price between 0.1 and 0.2 in the final selected combination is less than 50%.
weighted price is a little bit tricky concept:
The weighted price of an item = brand weighted price of all items under the brand of the item in the final selected combination
brand weighted price = sum(price) / sum(value)
eg. If we select item 1, item 2 and item 3 in the final combination:
weighted price of item 1 / item 3 = sum(price)/sum(value) = (0.2+0.3)/(0.1+0.1)
weighted price of item 2 = sum(price)/sum(value) = 0.3/0.2
I am using MILP solver (CBC, CPLEX). I want to know how to linearize this problem, or whether this attempt is possible. Thanks so much.
Update:
I'd like to provide an detailed example to help specify this problem:
Now we have 10 different items
| Item Name | Brand | Value | Price |
|---|---|---|---|
| item 1 | A | 0.1 | 0.2 |
| item 2 | B | 0.2 | 0.3 |
| item 3 | A | 0.1 | 0.3 |
| item 4 | A | 0.2 | 0.3 |
| item 5 | A | 0.3 | 0.5 |
| item 6 | B | 0.1 | 0.2 |
| item 7 | B | 0.2 | 0.3 |
| item 8 | A | 0.3 | 0.6 |
| item 9 | B | 0.3 | 0.3 |
| item 10 | B | 0.2 | 0.2 |
Constraint: (num of selected items with weighted price between 1.0 and 1.5) / (num of selected items) <= 50%
Assume item 1,3,5,7,9,10 are selected.
for item 1,3,5 (Brand A) weighted price = sum(price)/sum(value) = (0.2+0.3+0.5) / (0.1+0.1+0.3) = 2
for item 7,9,10 (Brand B) weighted price = sum(price)/sum(value) = (0.3+0.3+0.2) / (0.2+0.3+0.2) = 1.33
Thus there are 3 selected items whose weighted prices are between 1.0 and 1.5.
Constraint:
(num of selected items with weighted price between 1.0 and 1.5) / (num of selected items) =3/6=50%<=50%
Constraint is satisfied.
As you can see the most tricky part is that weighted price of each item changes with the final combination.
So if $x_{i}$ be binary variable, B is set of brands indexed over over $ I =\{1,2,...1000 \}$ and a combination set IB$=\{(1,A),(2,B),...\} $, $p$ as price and $v$ as value with $x=1$ if object $i$ is selected, then
$ M(y_{1,i}-1)+ 0.1\sum_{i\in IB:b=B_i} v_ix_{i} \le \sum_{i\in IB:b=B_i} p_ix_{i} \le 0.2\sum_{i\in IB:b=B_i} v_ix_i + M(1-y_{1,i})$
$M(y_{2,i}-1)+\sum_{i\in IB:b=B_i} p_ix_{i}\le 0.1\sum_{i\in IB:b=B_i} v_ix_{i} + M(1-y_{2,i})$
$M(y_{3,i}-1)+ 0.2\sum_{i\in IB:b=B_i} v_ix_i \le \sum_{i\in IB:b=B_i} p_ix_i\le+ M(1-y_{3,i})\ \ \forall i\in I$
$\sum_{j=1}^3 y_{j,i}=x_i\ \ \forall i\in I$
The above 3 constraints for all $i$ evaluates the weighted brand value using binary $y_{j,i}$ where $y_{1,i}=1$ if weighted value is $[0.1,0.2] $ for selected $i$.
If $N$ is predetermined number to be selected then
$ \sum_i x_i = N$
$ \sum_i y_{1,i} \le {N\over 2}$
or
$ 2\sum_i y_{1,i} \le \sum_i x_i$