#c #optimization #cplex #quadratic-programming
#c #оптимизация #cplex #квадратичное программирование
Вопрос:
Я реализовал UBQP (то есть квадратичную задачу без ограничений и с двоичными переменными) в CPLEX (версия 12.6.2) в вызываемой библиотеке на C, и я заинтересован в получении нескольких решений (не только оптимальных, но и других возможных).
Я взял оригинал CPLEX populate.cpp код и получение его подпрограмм для получения пула решений, таких как CPXpopulate(env, lp).
Проблема в том, что размер моего пула решений всегда равен 1, он содержит только оптимальное. Вместо этого, если я дам populate.cpp задача LP (т. Е. линейная задача минимизации) работает правильно.
Я попробовал обычные команды:
status = CPXsetdblparam (env, CPXPARAM_MIP_Pool_RelGap, 0.5);
status = CPXsetintparam (env, CPXPARAM_MIP_Pool_Capacity, 25);
status = CPXsetintparam (env, CPXPARAM_MIP_Pool_Replace, 1);
status = CPXsetdblparam (env,CPXPARAM_Simplex_Tolerances_Feasibility,0.01);
status = CPXsetdblparam (env, CPXPARAM_MIP_Tolerances_Integrality, 0.01);
status = CPXsetintparam (env, CPXPARAM_MIP_Pool_Intensity, N);
это должно заставить CPLEX генерировать больше решений, но этого не происходит.
Если я установлю N = 4 (это максимальное значение) в CPXPARAM_MIP_Pool_Intensity, оптимизация не удалась, но если установить N = 0, …,3, я получу не более 1 решения.
Есть ли способ получить несколько решений в такой задаче?
Комментарии:
1. Здесь есть technote, который устарел, но содержит несколько полезных указателей. Вы пробовали использовать populate из interactive (чтобы убедиться, что вы получаете те же результаты)?
2. Чтобы другие могли ознакомиться с ними поближе, вы можете поделиться своей моделью здесь (например, в формате SAV) через сайт обмена файлами, например filedropper.com .
3. @rkersh Использование заполнения из интерактивного приводит к 3 решениям вместо 1. Остальные 2 решения тривиальны: 000 … 0 и 111 … 1, они, безусловно, не то, что мне нужно, и я помню, что нашел их также в вызываемой библиотеке, устанавливающей некоторые параметры в какое-то значение, которое я не помню. Я не уверен, что я правильно реализовал то, что написано в этом technote, однако теперь я могу получить несколько решений (в основном, добавляя ограничения, которые заставляют сотрудника меняться и выполнять цикл). Проблема сейчас в том, что время выполнения, которое я вижу, намного больше, чем я ожидал!
4. Хотя populate работал очень быстро (даже если он дал мне только 1 решение), вышеупомянутый алгоритм работает очень медленно. При равных условиях заполнение выполняется менее чем за 100 мс, в то время как этот алгоритм занял более 70 000 мс!
5. Трудно что-либо сказать о производительности, не зная больше о вашей конкретной модели. В technote упоминается, что перечисление всех решений и / или использование альтернативных методов может занять много времени.
Ответ №1:
Чтобы получить большое количество возможных решений с помощью CPLEX, вы должны использовать CPLEX.populate() вместо CPLEX.solve()