Каков подходящий метод оптимизации (алгоритм) для решения таких задач (линейное смешанное целое число)?

Question

У меня есть эта проблема оптимизации:

В этой задаче C_ {i, k} - это матрица двоичных значений (т. Е. 0 или 1), а w_i - вектор целых чисел, p_f - это вероятность, а \ epsilon - это константа. Я понимаю, что проблема является линейной смешанно-целочисленной задачей. Но меня смущает метод или алгоритм, который я должен использовать для решения проблемы, и как я могу go продолжить, выполнив анализ выпуклости. Ваши отзывы приветствуются. Большое спасибо.

Answer 1

Это проблема 0-1 ранца . Эта проблема может быть решена с использованием динамического программирования c или алгоритма ветвления и ограничения. Для ветвления и границы вы можете выбрать любую переменную z_k, решить две подзадачи с z_k, равным либо 0, либо 1. Каждая подзадача имеет точную структуру в качестве исходной задачи.