Как проверить без объектной функции, возможны ли ограничения?

Мой профессор дал мне задачу двоичного линейного программирования, но эта проблема немного отличается от задач оптимизации, которые я решал раньше (т.е., вероятно, это не максимизация или минимизация объектной функции).

Проблема заключается в следующем. Для матрицы M для элементов m_ij! = 0 существуют соответствующие переменные x_ijk. Записи m_ij = 0 можно игнорировать.

x_ijk равно 0 или 1, и я хочу попробовать 5 переменных x_ijk для каждого m_ij (то есть x_ij1, x_ij2, x_ij3, x_ij4 и x_ij5. Один из них равен 1, а другие - 0), достаточно для выполнения некоторых условий. (набор неравенств).

Проще говоря, это проверка того, является ли набор ограничений, включающий 5 переменных x_ijk для каждого m_ij, допустимыми (или выполнимыми) ограничениями.

Я решил некоторые задачи оптимизации, но никогда не решал задачу без целевой функции.

Что я должен установить здесь в качестве моей целевой функции? 0? ничего такого?

Я мог бы использовать lp_solve или CPLEX.

Заранее благодарю за совет!


c++ math mathematical-optimization linear-programming
person Eric Na    schedule 15.02.2013    source источник
comment
Да, любой постоянной целевой функции, которую принимает ваш решатель, будет достаточно. Возможно, вы захотите найти удовлетворение ограничений.   -  person Ram Narasimhan    schedule 15.02.2013
comment
Спасибо за ваш комментарий. Я не знал, что такие вещи (как программирование в ограничениях) вообще существуют. Я обязательно прочитаю это. Спасибо.   -  person Eric Na    schedule 15.02.2013

Ответы (1)


arrow_upward
4
arrow_downward

Это правильно, вы можете установить произвольное постоянное значение в качестве целевой функции.

Большинство решателей, которые я пробовал, допускают пустую целевую функцию. Просто исключите его из своей модели.

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

Не волнуйтесь, это должно сработать.

В ответ на ваш комментарий: Да, инструменты программирования ограничений могут обеспечить лучшую производительность при решении задач осуществимости, чем решатели LP (такие как CPLEX). Я играл с IBM ILOG CPLEX CP Optimizer несколько месяцев назад это было бесплатно для академических пользователей. И решатель LP, и решатель CP не справились с моими проблемами. Не ждите чуда от программирования с ограничениями.

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

Просто для информации: в конце концов, решатель программирования ограничений вызовет решатель LP (например, CPLEX).

Мой совет: попробуйте уже имеющийся у вас инструмент / используйте более естественную для вас формулировку задачи. Проверьте, может ли инструмент решить вашу проблему. Переключайте инструмент только в том случае, если инструмент не работает и вы не можете улучшить свою модель.

person Ali    schedule 15.02.2013
comment
Спасибо за совет! Во всяком случае, г-н Нарасимхан направил меня к программированию в ограничениях, и, похоже, существуют специальные инструменты для решения самой проблемы программирования в ограничениях. Стоит ли использовать эти наборы инструментов? или я могу просто использовать программы / пакеты линейного программирования, такие как MATLAB, CPLEX или lp_solve? Будет ли последний с функцией объекта, установленной как 0, работать так же, как эти инструменты программирования ограничений? У меня немало ограничений, но их можно управлять (не более 100), и все они линейны. - person Eric Na; 15.02.2013
comment
Большое тебе спасибо!! Это очень помогает !! Я могу использовать для этого MATLAB. Могу я задать еще один вопрос? Таким образом, всем переменным m_ij будет присвоено неотрицательное целочисленное значение, а переменные x_ijk являются неизвестными (либо 0, либо 1). Итак, в конечном итоге, если мой код заработает, компьютер найдет, какими будут эти значения x_ijk (0 или 1), верно? Или он просто проверяет, соответствует ли набор ограничений, и сообщает, что это нормально / или нет? - person Eric Na; 16.02.2013
comment
Извините, что снова задаю вопросы, и большое спасибо за ваш добрый совет !! - person Eric Na; 16.02.2013
comment
(более конкретно, для всех i, j, x_ij1 + x_ij2 + x_ij3 + x_ij4 + x_ij5 = 1 и некоторого неравенства, включающего множество m_ij (неотрицательное целое число), умноженное на эти значения x_ijk. Итак, вопрос заключался в том, найдет ли компьютер решения для x_ijk, или он просто проверяет, действителен ли набор ограничений?) - person Eric Na; 16.02.2013
comment
@ user25409 Даёт конечно решения. Возможно, вам придется прочитать документацию о том, как распечатать решение, большинство решателей просто сообщают, что они готовы, но ответственность за распечатку решения лежит на пользователе. - person Ali; 16.02.2013