linear programming - Adding constrain to check if there exist a combination of pairs such that it statisfy a ratio?

Question

Lets say I have a set of items in a set x0, ..., x14 each consisting its own values v0, ..., v14

I am trying to at most 8 items such that I get the maximum value.

I am able to get the following maximization problem

max v0*x0 + ... + v14*x14
s.t.
x0 + ... + x14 <= 8
0 <= x0 <= 1
.
.
0 <= x14 <= 1
 

However, I need to add another constrains, that is for the items chosen, I should be able to pair them such that their ratio is less than 2.

i.e. lets say that the item chosen is x0, x1, x3, x4, x8, x9, x10, x11 with the maximum value they would also have a configuration of pairing such that,

(v0 * x0)/(v1 * x1)  <= 2, 
(v3 * x3)/(v9 * x9)  <= 2,
(v4 * x4)/(v11 * x11)<= 2,
(v8 * x8)/(v10 * x10)<= 2,

Any idea on how to formulate the above set of constrains?

question from:https://stackoverflow.com/questions/65829748/adding-constrain-to-check-if-there-exist-a-combination-of-pairs-such-that-it-sta

Answer 1

So you can precompute the valid pairs, and their value (the sum of the 2 elements)

So there are at most 14 * 13 / 2 potential ordered pairs, much less valid ones.

You need to select 4 pairs subject to the constraint that once a pair is selected, any pairs involving the same elements cannot be selected. This is a simple at most one constraints on 14 subsets of pairs.

for all item in items:
  sum(bool_pair for all bool_pair involving item) <= 1

You can use CP-SAT or the linear solver wrapper to solve this.