Настройка целочисленного линейного программирования

Измените опции, чтобы улучшить процесс решения

Примечание

Часто, можно изменить формулировку MILP, чтобы сделать его более легко разрешимым. Для предложений о том, как изменить вашу формулировку, смотрите Уильямса [1].

После того, как вы запускаетесь intlinprog однажды, вы можете хотеть изменить некоторые опции и повторно выполнить его. Изменения, которые вы можете хотеть видеть, включают:

  • Более низкое время выполнения

  • Понизьте итоговое значение целевой функции (лучшее решение)

  • Меньший итоговый разрыв

  • Больше или различные допустимые точки

Вот общие рекомендации для изменений опции, которые, скорее всего, помогут процессу решения. Попробуйте предложения в этом порядке:

  1. Для более быстрого и более точного решения увеличьте CutMaxIterations опция от ее 10 по умолчанию к более высокому номеру, такому как 25. Это может ускорить решение, но может также замедлить его.

  2. Для более быстрого и более точного решения измените CutGeneration опция к 'intermediate' или 'advanced'. Это может ускорить решение, но может использовать намного больше памяти и может замедлить решение.

  3. Для более быстрого и более точного решения измените IntegerPreprocess опция к 'advanced'. Это может оказать большое влияние на процесс решения, или выгодный или нет.

  4. Для более быстрого и более точного решения измените RootLPAlgorithm опция к 'primal-simplex'. Обычно это изменение не выгодно, но иногда это может быть.

  5. Чтобы попытаться найти больше или лучшие допустимые точки, увеличьте HeuristicsMaxNodes опция от ее 50 по умолчанию к более высокому номеру, такому как 100.

  6. Чтобы попытаться найти больше или лучшие допустимые точки, измените Heuristics опция к любому 'intermediate' или 'advanced'.

  7. Чтобы попытаться найти больше или лучшие допустимые точки, измените BranchRule опция к 'strongpscost' или, если тому выбору не удается улучшить решение, 'maxpscost'.

  8. Для более быстрого решения увеличьте ObjectiveImprovementThreshold опция от ее значения по умолчанию нуля к положительному значению, такому как 1e-4. Однако это изменение может вызвать intlinprog найти меньше целочисленных допустимых точек или менее точное решение.

  9. Чтобы попытаться остановить решатель более быстро, измените RelativeGapTolerance опция к более высокому значению, чем 1e-4 по умолчанию. Точно так же, чтобы попытаться получить более точный ответ, измените RelativeGapTolerance опция к нижнему значению. Эти изменения не всегда улучшают результаты.

Некоторые “целочисленные” решения не являются Целыми числами

Часто, некоторые, предположительно, компоненты с целочисленным знаком решения x(intcon) не точно целые числа. intlinprog рассматривает как целые числа все значения решения в IntegerTolerance из целого числа.

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

x(intcon) = round(x(intcon));

Внимание

Округление может вызвать решения стать неосуществимым. Проверяйте выполнимость после округления:

max(A*x - b) % see if entries are not too positive, so have small infeasibility
max(abs(Aeq*x - beq)) % see if entries are near enough to zero
max(x - ub) % positive entries are violated bounds
max(lb - x) % positive entries are violated bounds

Большие компоненты не ценное целое число

intlinprog не осуществляет это компоненты решения быть целым числом, оцененным, когда их абсолютные значения превышают 2.1e9. Когда ваше решение имеет такие компоненты, intlinprog предупреждает вас. Если вы получаете это предупреждение, проверяйте решение видеть, являются ли, предположительно, компоненты с целочисленным знаком решения близко к целым числам.

Большие запрещенные коэффициенты

intlinprog не позволяет компоненты проблемы, такие как коэффициенты в fA, или ub, превысить 1e15 в абсолютном значении. При попытке запуститься intlinprog с такой проблемой, intlinprog выдает ошибку.

Если вы получаете эту ошибку, иногда можно масштабировать проблему иметь меньшие коэффициенты:

  • Для коэффициентов в f это является слишком большим, пытается умножить f маленьким положительным масштабным коэффициентом.

  • Для ограничительных коэффициентов, которые являются слишком большими, попытайтесь умножить все границы и ограничительные матрицы тем же маленьким положительным масштабным коэффициентом.

Ссылки

[1] Уильямс, Х. Пол. Построение моделей в математическом программировании. Вайли, 2013.

Для просмотра документации необходимо авторизоваться на сайте