- Возможный метод решения SDP-релаксации квадратичной задачи о рюкзаке (arXiv)
Автор: Тяньюнь Тан, Ким-Чуан То.
Аннотация: В этой статье мы рассматриваем SDP-релаксацию квадратичной задачи о рюкзаке (QKP). После использования факторизации Бюрера-Монтейро мы получаем невыпуклую задачу оптимизации, допустимая область которой является алгебраическим многообразием. Хотя на алгебраическом многообразии могут быть нерегулярные точки, мы доказываем, что алгебраическое многообразие является гладким многообразием, за исключением тривиальной точки для входных данных общего положения. Мы также анализируем локальные геометрические свойства нерегулярных точек на этом алгебраическом многообразии. Чтобы сохранить эквивалентность между задачей SDP и ее невыпуклой формулировкой, мы выводим новое ранговое условие, при котором эти две задачи эквивалентны. Это новое условие ранга может быть намного слабее, чем классическое условие ранга, если матрица коэффициентов имеет некоторые специальные структуры. Мы также доказываем, что при соответствующем условии ранга любая стационарная точка второго порядка невыпуклой задачи также является глобальным оптимальным решением без каких-либо предположений о регулярности. Этот результат отличается от предыдущих результатов, основанных на предположении о гладкости, подобной LICQ. Со всеми этими теоретическими свойствами мы разрабатываем алгоритм, который снабжает метод оптимизации многообразия стратегией выхода из неоптимальных нерегулярных точек. Наш алгоритм можно также использовать в качестве эвристики для решения квадратичной задачи о рюкзаке. Численные эксперименты проводятся для проверки высокой эффективности и надежности нашего алгоритма по сравнению с другими решателями SDP и эвристическим методом, основанным на динамическом программировании. В частности, наш алгоритм способен очень точно решить SDP-релаксацию миллиономерной QKP с разреженной матрицей стоимости примерно за 20 минут на скромном настольном компьютере.
2. Эволюционные многоцелевые алгоритмы для задач о рюкзаке со стохастической прибылью (arXiv)
Автор: Кокила Перера, Анета Нойманн, Франк Нойманн.
Аннотация: Было широко показано, что эволюционные многокритериальные алгоритмы успешны при использовании для различных задач стохастической комбинаторной оптимизации. Вероятностно-ограниченная оптимизация играет важную роль в сложных сценариях реального мира, поскольку позволяет лицам, принимающим решения, учитывать неопределенность среды. Мы рассматриваем вариант задачи о рюкзаке со стохастической прибылью, чтобы гарантировать определенный уровень уверенности в прибыли решений. Мы представляем многокритериальные формулировки задачи о рюкзаке с ограниченным шансом на прибыль и разрабатываем три двукритериальных метода оценки пригодности, которые работают независимо от конкретного требуемого уровня достоверности. Мы оцениваем наши подходы, используя известные многоцелевые эволюционные алгоритмы GSEMO и NSGA-II. Кроме того, мы вводим метод фильтрации для GSEMO, который улучшает качество конечной совокупности путем периодического удаления определенных решений из промежуточных совокупностей на основе их уровня достоверности. Мы показываем эффективность наших подходов на нескольких бенчмарках для обеих ситуаций, где предметы ранца имеют фиксированные однородные неопределенности и неопределенности, которые положительно коррелируют с ожидаемой прибылью предмета.
