WedX - журнал о программировании и компьютерных науках

Целочисленные программы. Как заставить решение быть кратным целому числу?

Итак, я пытаюсь создать этот IP-адрес с оптимальным решением, в котором все переменные являются целыми числами, и все они кратны числу, например 3. (поэтому переменные в решении должны быть либо 0,3,6 ,9,12 и т.д.)

Я кодирую на R, и довольно легко установить ограничение, согласно которому решение должно быть целым числом (all.int = TRUE), но я не уверен, как сделать его кратным числу. Какие изменения я должен внести в формулировку Ax ‹= b? Ваша помощь будет принята с благодарностью! На данный момент я совершенно не понимаю, как это сделать на самом деле.

r constraints mathematical-optimization integer-programming
30.07.2015

Ответы:


1

Для этого вы можете определить некоторую целочисленную переменную x, а затем определить y = 3*x. Теперь y является целым числом и кратным 3.

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

library(lpSolve)
mod <- lp(direction = "max",
          objective.in = c(0, 1),  # (x, y)
          const.mat = rbind(c(3, -1),  # 3x - y = 0
                            c(0, 1)),  # y <= 10
          const.dir = c("=", "<="),
          const.rhs = c(0, 10),
          all.int = TRUE)
mod$solution[2]
# [1] 9
30.07.2015
  • Вау, спасибо! Это было действительно полезно! Итак, мне нужно добавить новую переменную [поэтому добавление нового столбца в const.mat, в данном случае «y»], чтобы зафиксировать решение «x» как кратное? 30.07.2015
  • @ Тимоти, мы определяем y = 3x, поэтому y - это переменная, кратная 3. 30.07.2015

    • 2

    Насколько я понимаю, ваш критерий состоит в том, что мод 3 ответа равен 0. Если да, то как насчет mod(intResult,3) == 0?

    Поскольку я не пишу на вашем языке, приведенное выше может быть недопустимым для R, но я думаю, вы поняли идею, поскольку приведенное выше действительно для C, предполагая, что mod — это имя функции, которая возвращает intResult по модулю 3.

    30.07.2015
  • OP указал, что это проблема целочисленного программирования, поэтому все ограничения должны быть линейными в переменных. Функция по модулю не является линейной функцией своего входа, поэтому ее здесь нельзя использовать. 30.07.2015
  • Я только что снова прочитал вопрос ОП, и нигде не упоминается требование, чтобы функция была линейной. Поскольку по модулю возвращается целое число, это должно быть честной игрой. Посмотрим, что скажет сам ОП. 01.08.2015
  • Заголовок начинается с целочисленных программ, а вопрос начинается с Итак, я пытаюсь создать этот IP, и вопрос помечен как целочисленное программирование, поэтому совершенно ясно, что это вопрос целочисленного программирования. Как вы можете прочитать из вики-статьи, все ограничения в целочисленных программах должны быть линейными в решении. переменные. 01.08.2015
  • Mod — целочисленная операция. Получить жизнь. 01.08.2015
  • Я не говорил о целочисленной операции, я говорил о линейной функции переменных решения. Целочисленные программы могут включать такие ограничения, как 3x ‹= 1 или x-2y ›= 3, потому что функции 3x и x-2y являются линейными функциями переменных; например поскольку x принимает значения 1, 2, 3, 4, 5, функция 3x принимает значения 3, 6, 9, 12, 15 (линейное изменение). x mod 3 не имеет этого свойства, принимая значения 1, 2, 0, 1, 2 (нелинейные) для входов 1, 2, 3, 4, 5. Линейные ограничения являются основным свойством IP. Поскольку кажется, что вы не знакомы с IP, я бы посоветовал вам использовать менее воинственный тон в ваших комментариях. 01.08.2015
    • Новые материалы
    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Учебные заметки: создание моего первого пакета Node.js
    Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..
    Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
    Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..
    Для любых предложений по сайту: wedx@cp9.ru