Почему `intlinprog` Matlab возвращает почти целые числа для целочисленных переменных?

Question

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

Согласно intlinprogСтраница , в разделе Limitations, решение, кажется, ищется в нецелочисленном пространстве и считается удовлетворяющим целочисленным ограничениям, если якобы целочисленные переменные имеют очень маленькую нецелую часть.

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

Answer 1

Базовый алгоритм intlinprog основан на процедуре, называемой "Ветвь и связывание" (BnB).В этой алгоритмической структуре пространство решений не буквально «ищется», а скорее, ограничения целостности обрабатываются неявно.Эта схема оказалась наиболее эффективным алгоритмом для общих проблем MILP.(Конечно, существует ряд алгоритмов для специфических задач, которые работают по разным принципам и рассматривают целочисленные величины как целые числа, например, алгоритмы графа / сети).

Непрерывно Релаксации играют заметную роль в BnB: после устранения («релаксации») ограничений целостности переменных, остается проблема линейной оптимизации, которая может быть решена очень эффективно.Во время этой процедуры ветвления и границ решается последовательность таких непрерывных релаксаций, каждая с различными оценками целочисленных переменных.

Теперь эти подзадачи решаются с помощью арифметики с плавающей запятой, и, естественно, результат не может быть гарантированно целочисленным.Следовательно, большинство решателей MILP имеют настраиваемый допуск, который управляет значением «целое число».

Краткое описание различных алгоритмических компонентов, стоящих за intlinprog, дано в документации .