Задача минимизации сложения векторного комбинаторика

Question

Я работаю над проблемой, и мне кажется, что это может быть аналогом существующей проблемы в математическом программировании, но у меня возникают проблемы с поиском любой такой проблемы.

Проблема заключается в следующем: у нас есть n наборов d размерных векторов, так что каждый набор содержит ровно d + 1 векторов.В каждом наборе все векторы имеют одинаковую длину (более того, угол между любыми двумя векторами в наборе одинаков для любого набора, но я не уверен, имеет ли это значение).Затем нам нужно выбрать ровно один вектор из каждого набора и вычислить сумму этих векторов.Наша цель состоит в том, чтобы сделать наш выбор таким образом, чтобы сумма векторов была минимальной.

Такое ощущение, что проблема в некотором роде связана с проблемой кратчайшего вектора или вариантом планирования задания, когда планирование задания на машине влияет на все машины, или проблемой раздела.

Звонит ли эта проблема?В частности, я ищу исследование для решения этой проблемы, так как в настоящее время моя лучшая ставка - использовать ILP, но я чувствую, что должно быть что-то более умное, что можно сделать.

Answer 1

Я думаю, что это проблема MIQP (смешанное целочисленное квадратичное программирование) или MISOCP (смешанный целочисленный конус второго порядка):

Пусть

 v(i,j) be i vectors in group j (data)
 x(i,j) in {0,1}: binary decision variables
 w: sum of selected vectors (decision variable)

Тогда проблему можно сформулировать так:

 min ||w||
 sum(i, x(i,j)) = 1   for all j
 w = sum((i,j), x(i,j)*v(i,j))

Если хотите, вы можете заменить w. На самом деле я не использую ограничение вашего угла (это ограничение для данных, а не для переменных решения модели). x переменные выбраны так, что мы выбираем ровно один вектор из каждой группы.

Минимизация 2-нормы может быть заменена минимизацией суммы квадратов элементов (то есть минимизации квадрата нормы).

Предполагая 2-норму, это проблема MISOCP или выпуклая проблема MIQP, для которой доступно довольно много решателей. Для 1-норм и бесконечностей можно сформулировать линейную задачу МИП. Решатели MIP широко доступны.