Ограничение выбранных переменных, решаемых в opensolver

Question

У меня есть линейная система из 17 уравнений, 506 переменных, которые решаются для минимального суммирования полных переменных. Пока это прекрасно работает, но решение является результатом комбинации из 19 переменных.

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

Я понял, что могу установить boolean = 1, если значение становится больше 0: (что означает, что выбрана переменная) и 0, если переменная не выбрана для оптимального решения.

И тогда сумма булевых чисел должна быть не более 10.

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

Так ли кто-нибудь есть предложения по:

1. Как мой сложный путь резко снижает производительность? (* У меня пока нет встроенного понимания алгоритмов opensolver.)
2. Более легкое предложение/в вариантах opensolver учитывает мое желание макс. 10 переменных решения?

Основываясь на информации, представленной ниже, я первый сократили размер проблемы:

У меня есть три списка данных с 18 записей в столбцах:

W7:W23,AC7:AD23

который вручную (с: W28 = 6000, AC28=600,W29 = 1,AC29 =1), в линейной комбинации, равной/превышать целевой список: EGM34:EG50

Так что я был поставлен переменные descion в W28:W29, AC28:AD29 Где я добавил ограничение W28,AC28:AD28 = integer в решатель (как оригинальный первенствует решатель как в opensolver)

И я добавил ограничение W29,AC29:AD29 = Boolean в решатель (как оригинал первенствует решатель, как в opensolver)

Тогда у меня есть умножение на целое число * Boolean = фактический коэффициент умножения для приведенных выше списков в (W7:W23 etc)

в целях ограничения факса выбранных переменных я также пытался, в дополнение к описанным ограничениям, чтобы ограничить ячейку =sum(W29,AC29:AD29) to <= 10 (эффективно уменьшая количество булевых значений, равное true ниже 11, или так я думал, но логические значения не вычисляются как логические алгоритмы).

Эти новые умноженных списки помещаются в W34:W50,AC34:AD50, а суммирование находится в: EGY34:EGY50 Поэтому окончательная проверка добавляется в качестве сдерживающего фактора, как:

EGY34:EGY50 =>EGM34:EGM50

И у меня был вопрос о том, как линейная solver оценивает эти ограничения, делает это:

a. Подумайте сумму EGY34:EGY50 must be larger or equal than/to EGM34:EGM50

или

б. Имеет ли он думать:.. «Для каждой строки х EGYx must be larger or equal than/to EGMx

До сих пор я отметил, б, но я хотел бы, чтобы убедиться, что

Но мои главные проблемы вопроса:

После использования эволюционнома алгоритм, который был любезно предложен в комментариях ниже, как/почему он пытается использовать значения как 0.99994 для переменных desicion, обозначенных как booleans?

Answer 1

Введение двоичных переменных действительно является стандартным способом реализации таких ограничений. К сожалению, он преобразует проблема f rom является проблемой линейного программирования как integer programming problem (в частности, проблема смешанного целочисленного линейного программирования). Стандартным подходом к таким проблемам является branch and bound algorithm. Это то, что использует встроенный решатель Excel, я не уверен в том, что вы используете открытый решатель. В лучшем случае (там, где есть много ограничений) он будет работать довольно быстро, даже с проблемами вашего размера. В худшем случае для вашей проблемы это может быть немного лучше, чем то, что вы получите, запустив алгоритм simplex C(506,10) = 2.8 x 10^20 раз (один раз для каждого возможного набора из 10 переменных решения). Другими словами, это может быть неосуществимо. Целочисленное программирование известно как NP-hard.

Если точное решение невозможно, вы всегда можете использовать эвристический алгоритм, такой как эволюционный подход.