Формирование билинейной программы оптимизации как целочисленной линейной программы

Question

В моей работе я столкнулся со следующей проблемой: учитывая матрицу подобия D, где $ d_ {i, j} \ in \ Re $ представляет сходство между объектами $ i $ и $ j $, я хотел бы выбрать объекты $ k $, для $ k \ in {1, \ dots, n} $, таким образом, чтобы минимизировать сходство между выбранными объектами. Моя первая попытка официально сформулировать эту проблему заключалась в использовании следующей целочисленной программы:

$ \ minim $ $ d_ {1,2} X_1X_2 + d_ {1,3} X_1X_3 + \ dots + d_ {1, n} X_1X_n + d_ {2,1} X_2X_1 + \ dots + d_ {n, n-1} X_nX_ {n-1} $

такой, что $ X_1 + X_2 + \ dots + X_n = k $ и $ X_y \ in {0,1} $, для $ y = 1, \ dots, n $

В вышеуказанной программе $ X_y $ указывает, был ли выбран объект $ y $. Ясно, что указанная выше программа не является линейной. Я попытался сделать объектную функцию линейной, используя переменные $ X_ {1,2} $, которая указывает, были ли выбраны оба объекта $ X_1 $ и $ X_2 $. Тем не менее, я изо всех сил пытаюсь сформулировать ограничение, что должны быть выбраны именно объекты $ k $, т. Е. Предыдущее ограничение $ X_1 + X_2 + \ dots + X_n = k $.

Поскольку я не специалист по математическому программированию, интересно, можете ли вы помочь мне в этом.

Спасибо заранее! Все самое лучшее,

Артур

Answer 1

Вы были на правильном пути, просто не хватает одну вещь:

Пусть x_i будет 1, если объект я выбран и 0 в противном случае.

Пусть y_ij быть 1, если объекты i & j оба выбраны и 0 в противном случае

IP-идет следующим образом:

увеличить

sum d_ij y_ij 

S.T.

sum x_i = k 

x_i + x_j - 1 <= y_ij for all i<j 

x & y binary variables 

Странная ищет ссылки ограничение говорит, что y_ij = 1 iff x_i + x_j =2

определяют только одну переменную у каждой пары!

Надеется, что это помогает