В своей работе я столкнулся со следующей проблемой: учитывая матрицу подобия D, где $d_{i,j} \in \Re$ представляет сходство между объектами $i$ и $j$, я хотел бы выбрать $k $ объектов, для $k \in {1, \dots, n}$, таким образом, чтобы минимизировать сходство между выбранными объектами. Моя первая попытка формально сформулировать эту задачу заключалась в использовании следующей целочисленной программы:
$\minimize$ $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$.
Поскольку я не эксперт в области математического программирования, мне интересно, не могли бы вы мне помочь с этим.
Заранее спасибо! Всего наилучшего,
Артур
