intlinprog

Смешанное целочисленное линейное программирование (MILP)

свернуть все на странице

Синтаксис

x = intlinprog (f, intcon, A, b)

x = intlinprog (f, intcon, A, b, Aeq, beq)

x = intlinprog (f, intcon, A, b, Aeq, beq, lb, ub)

x = intlinprog (f,intcon,A,b,Aeq,beq,lb,ub,x0)

x = intlinprog (f,intcon,A,b,Aeq,beq,lb,ub,x0,options)

x = intlinprog (проблема)

[x, fval, exitflag, output] = intlinprog (___)

Описание

Решатель линейного программирования со смешанным целым числом.

Находит минимум проблемы, указанный в

$\underset{}{}^{} minxfTx, подлежащие {\begin{array}{l} x (intcon) , являются \\ integersA\cdotx\leqbAeq\cdotx=beqlb\leqx\lequb \end{array}$ .

f, x, intcon, b, beq, lb и ub - векторы, а A и Aeq - матрицы.

В качестве векторов или массивов можно указать f, intcon, lb и ub. См. раздел Аргументы матрицы.

Примечание

intlinprog применяется только к подходу, основанному на решателе. Обсуждение двух подходов к оптимизации см. в разделе Первый выбор подхода на основе проблем или подхода на основе решателей.

пример

x = intlinprog(f,intcon,A,b) решает min f'*x таким, чтобы компоненты x в intcon являются целыми числами, и A*x ≤ b.

x = intlinprog(f,intcon,A,b,Aeq,beq) решает вышеуказанную задачу при дополнительном удовлетворении ограничений равенства Aeq*x = beq. Набор A = [] и b = [] если неравенства не существует.

пример

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для конструктивных переменных, x, чтобы решение всегда находилось в диапазоне lb ≤ x ≤ ub. Набор Aeq = [] и beq = [] если равенства отсутствуют.

пример

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)оптимизирует использование начальной осуществимой точки x0. Набор lb = [] и ub = [] если не существует границ.

пример

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) минимизирует использование опций оптимизации, указанных в options. Использовать optimoptions для установки этих параметров. Набор x0 = [] если начальная точка не существует.

пример

x = intlinprog(problem) использует problem структура для инкапсуляции всех входных данных решателя. Можно импортировать problem структура из файла MPS с использованием mpsread. Можно также создать problem структура из OptimizationProblem объект с помощью prob2struct.

пример

[x,fval,exitflag,output] = intlinprog(___), для любых входных аргументов, описанных выше, возвращает fval = f'*x, значение exitflag описание условия выхода и структура output содержит информацию о процессе оптимизации.

Примеры

свернуть все

Решение MILP с линейными неравенствами

Открыть сценарий в реальном времени

Решить проблему

$\underset{}{}_{}_{} \begin{array}{llllllllllllllllllll} _{} \\ _{}_{} \\ _{}_{} \\ _{}_{} minx8x1+x2subjectto{x2isanintegerx1+2x2≥-14-4x1-x2≤-332x1+x2≤20 . \end{array}$

Запишите вектор целевой функции и вектор целочисленных переменных.

f = [8;1];
intcon = 2;

Преобразование всех неравенств в форму A*x <= b умножением неравенства «больше, чем» на -1.

A = [-1,-2;
    -4,-1;
    2,1];
b = [14;-33;20];

Звонить intlinprog.

x = intlinprog(f,intcon,A,b)

LP:                Optimal objective value is 59.000000.                                            


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

Решение MILP со всеми типами ограничений

Открыть сценарий в реальном времени

Решить проблему

$\underset{minx}{} (-_{}_{}_{} 3x1-2x2-x3) \begin{array}{llllllllllllllllllll} _{} \\ _{}_{} \\ _{}_{}_{} \\ _{}_{}_{} \end{array}$ subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

Запишите вектор целевой функции и вектор целочисленных переменных.

f = [-3;-2;-1];
intcon = 3;

Запишите линейные ограничения неравенства.

A = [1,1,1];
b = 7;

Запишите линейные ограничения равенства.

Aeq = [4,2,1];
beq = 12;

Запишите связанные ограничения.

lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binary

Звонить intlinprog.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

Использовать начальную точку

Открыть сценарий в реальном времени

Сравните количество шагов для решения задачи целочисленного программирования как с начальной возможной точкой, так и без нее. Задача состоит из восьми переменных, четырех линейных ограничений равенства, и все переменные ограничены положительными.

Определите матрицу и вектор ограничений линейного равенства.

Aeq = [22    13    26    33    21     3    14    26
    39    16    22    28    26    30    23    24
    18    14    29    27    30    38    26    26
    41    26    28    36    18    38    16    26];
beq = [ 7872
       10466
       11322
       12058];

Установите нижние границы, ограничивающие все переменные неотрицательными.

N = 8;
lb = zeros(N,1);

Укажите, что все переменные являются целочисленными.

intcon = 1:N;

Установка вектора целевой функции f.

f = [2    10    13    17     7     5     7     3];

Решите проблему, не используя начальную точку, и проверьте отображение, чтобы увидеть количество узлов, связанных ветвями.

[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);

LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1591.000000.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.88         0              -              -                                          
   18027      1.48         1   2.906000e+03   4.509804e+01                                          
   21859      1.95         2   2.073000e+03   2.270974e+01                                          
   23546      2.11         3   1.854000e+03   1.180593e+01                                          
   24121      2.16         3   1.854000e+03   1.563342e+00                                          
   24294      2.18         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

Для сравнения найдите решение, используя начальную осуществимую точку.

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);

LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1591.000000.                                                      
                   Relative gap is 59.20%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    3627      0.35         2   2.154000e+03   2.593968e+01                                          
    5844      0.56         3   1.854000e+03   1.180593e+01                                          
    6204      0.60         3   1.854000e+03   1.455526e+00                                          
    6400      0.62         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

Без начальной точки, intlinprog предприняло около 30 000 шагов, связанных ветвями.
Используя начальную точку, intlinprog сделал около 5000 шагов.

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

Решение MILP с опциями Nondefault

Открыть сценарий в реальном времени

Решить проблему

$\underset{minx}{} (-_{}_{}_{} 3x1-2x2-x3) \begin{array}{llllllllllllllllllll} _{} \\ _{}_{} \\ _{}_{}_{} \\ _{}_{}_{} \end{array}$ subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

без отображения итеративного дисплея.

Укажите входные данные решателя.

f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary
x0 = [];

Укажите отсутствие отображения.

options = optimoptions('intlinprog','Display','off');

Запустите решатель.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)

Решение MILP с помощью проблемного подхода

Открыть сценарий в реальном времени

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

$\underset{minx}{} (-_{}_{}_{} 3x1-2x2-x3) \begin{array}{llllllllllllllllllll} _{} \\ _{}_{} \\ _{}_{}_{} \\ _{}_{}_{} \end{array}$ subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

Создание OptimizationProblem объект с именем prob для представления этой проблемы. Чтобы задать двоичную переменную, создайте переменную оптимизации с целым типом, нижней границей 0 и верхней границей 1.

x = optimvar('x',2,'LowerBound',0);
xb = optimvar('xb','LowerBound',0,'UpperBound',1,'Type','integer');
prob = optimproblem('Objective',-3*x(1)-2*x(2)-xb);
cons1 = sum(x) + xb <= 7;
cons2 = 4*x(1) + 2*x(2) + xb == 12;
prob.Constraints.cons1 = cons1;
prob.Constraints.cons2 = cons2;

Преобразование проблемного объекта в проблемную структуру.

problem = prob2struct(prob);

Решите возникшую структуру проблемы.

[sol,fval,exitflag,output] = intlinprog(problem)

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'

Оба sol(1) и sol(3) являются двоично-значными. Какое значение соответствует двоичной переменной оптимизации xb?

prob.Variables

ans = struct with fields:
     x: [2x1 optim.problemdef.OptimizationVariable]
    xb: [1x1 optim.problemdef.OptimizationVariable]

Переменная xb появляется последним в Variables дисплей, так xb соответствует sol(3) = 1. См. раздел Алгоритмы.

Анализ решения и процесса MILP

Открыть сценарий в реальном времени

Звонить intlinprog с большим количеством выходных данных для просмотра деталей решения и процесса.

Цель - решить проблему

$\underset{minx}{} (-_{}_{}_{} 3x1-2x2-x3) \begin{array}{llllllllllllllllllll} _{} \\ _{}_{} \\ _{}_{}_{} \\ _{}_{}_{} \end{array}$ subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

Укажите входные данные решателя.

f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary

Звонить intlinprog со всеми выходами.

[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'

Структура вывода показывает numnodes является 0. Это означает, что intlinprog решил проблему перед ветвлением. Это один из признаков того, что результат надежен. Также, absolutegap и relativegap поля 0. Это еще один признак того, что результат надежен.

Входные аргументы

свернуть все

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

Вектор коэффициента, заданный как действительный вектор или вещественный массив. Вектор коэффициентов представляет целевую функцию f'*x. Запись предполагает, что f является вектором столбца, но можно использовать вектор строки или массив. Внутри, linprog новообращенные f к вектору столбца f(:).

При указании f = [], intlinprog пытается найти осуществимую точку, не пытаясь минимизировать объективную функцию.

Пример: f = [4;2;-1.7];

Типы данных: double

`intcon` - Вектор целочисленных ограничений
вектор целых чисел

Вектор целочисленных ограничений, заданный как вектор положительных целых чисел. Значения в intcon указать компоненты переменной принятия решения, x целочисленные. intcon имеет значения из 1 через numel(f).

intcon также может быть массивом. Внутри, intlinprog преобразует массив intcon к вектору intcon(:).

Пример: intcon = [1,2,7] средства x(1), x(2), и x(7) принимать только целочисленные значения.

Типы данных: double

`A` - Матрица ограничений линейного неравенства
реальная матрица

Матрица ограничений линейного неравенства, заданная как матрица двойников. A представляет линейные коэффициенты в ограничениях A*x ≤ b. A имеет размер Mоколо-N, где M - количество ограничений и N = numel(f). Чтобы сохранить память, A может быть разреженным.

Пример: A = [4,3;2,0;4,-1]; означает три линейных неравенства (три строки) для двух переменных решения (два столбца).

Типы данных: double

`b` - вектор ограничения линейного неравенства;
действительный вектор

Вектор ограничения линейного неравенства, заданный как вектор двойников. b представляет вектор константы в ограничениях A*x ≤ b. b имеет длину M, где A является Mоколо-N.

Пример: [4,0]

Типы данных: double

`Aeq` - Матрица ограничений линейного равенства
`[]` (по умолчанию) | вещественная матрица

Матрица ограничений линейного равенства, заданная как матрица двойников. Aeq представляет линейные коэффициенты в ограничениях Aeq*x = beq. Aeq имеет размер Meqоколо-N, где Meq - количество ограничений и N = numel(f). Чтобы сохранить память, Aeq может быть разреженным.

Типы данных: double

`beq` - вектор ограничения линейного равенства;
`[]` (по умолчанию) | реальный вектор

Линейный вектор ограничения равенства, заданный как вектор двойников. beq представляет вектор константы в ограничениях Aeq*x = beq. beq имеет длину Meq, где Aeq является Meqоколо-N.

Пример: [4,0]

Типы данных: double

`lb` - Нижние границы
`[]` (по умолчанию) | вещественный вектор или массив

Нижние границы, указанные как вектор или массив двойников. lb представляет нижние границы элементарно в lb ≤ x ≤ ub.

Внутри, intlinprog преобразует массив lb к вектору lb(:).

Пример: lb = [0;-Inf;4] средства x(1) ≥ 0, x(3) ≥ 4.

Типы данных: double

`ub` - Верхние границы
`[]` (по умолчанию) | вещественный вектор или массив

Верхние границы, заданные как вектор или массив двойников. ub представляет верхние границы элементарно в lb ≤ x ≤ ub.

Внутри, intlinprog преобразует массив ub к вектору ub(:).

Пример: ub = [Inf;4;10] средства x(2) ≤ 4, x(3) ≤ 10.

Типы данных: double

`x0` - Начальная точка
`[]` (по умолчанию) | real array

Начальная точка, заданная как вещественный массив. Количество элементов в x0 совпадает с числом элементов f, когда f существует. В противном случае число совпадает с числом столбцов A или Aeq. Внутри решатель преобразует массив x0 в вектор x0(:).

Обеспечение x0 может изменить количество времени intlinprog принимает, чтобы сойтись. Трудно предсказать, как x0 влияет на решатель. Для получения предложений по использованию соответствующих Heuristics с x0, см. Советы.

x0 должны быть выполнимыми в отношении всех ограничений. Если x0 невозможно, решатель ошибается. Если у вас нет выполнимого x0, комплект x0 = [].

Пример: x0 = 100*rand(size(f))

Типы данных: double

`options` - Опции для `intlinprog`
параметры, созданные с помощью `optimoptions`

Опции для intlinprog, указанный как выход optimoptions.

Некоторые опции отсутствуют в optimoptions дисплей. Эти параметры выделены курсивом в следующей таблице. Дополнительные сведения см. в разделе Параметры просмотра.

Выбор	Описание	Дефолт
`AbsoluteGapTolerance`	Ненегативный реал. `intlinprog` останавливается, если разница между внутренним вычисленным верхним (`U`) и ниже (`L`) границы целевой функции меньше или равны `AbsoluteGapTolerance`: `U – L <= AbsoluteGapTolerance`.	`0`
`BranchRule`	Правило выбора компонента для ветвления: `'maxpscost'` - дробный компонент с максимальной псевдокостью. См. раздел Ветвление и привязка. `'strongpscost'` - Дробная составляющая с максимальной псевдокостью и более точной оценкой псевдокостности, чем в `'maxpscost'`. См. раздел Ветвление и привязка. `'reliability'` - Дробная составляющая с максимальной псевдокостью и еще более точной оценкой псевдокостности, чем в `'strongpscost'`. См. раздел Ветвление и привязка. `'mostfractional'` - компонент, дробная часть которого ближе всего `1/2`. `'maxfun'` - Дробная составляющая с максимальным соответствующим компонентом в абсолютном значении целевого вектора `f`.	`'reliability'`
`ConstraintTolerance`	Реально от `1e-9` через `1e-3` это максимальное расхождение, которое линейные ограничения могут иметь и по-прежнему считаться удовлетворенными. `ConstraintTolerance` не является критерием остановки.	`1e-4`
`CutGeneration`	Уровень генерации реза (см. раздел Генерация реза): `'none'` - Без порезов. Делает `CutMaxIterations` не имеет значения. `'basic'` - Нормальная генерация погонов. `'intermediate'` - Используйте другие типы вырезов. `'advanced'` - Использовать большинство типов вырезов.	`'basic'`
`CutMaxIterations`	Количество проходов через все методы генерации вырезов перед входом в фазу ответвления и границы, целое число от `1` через `50`. Отключите генерацию вырезов, установив `CutGeneration` опция для `'none'`.	`10`
`Display`	Уровень отображения (см. Итерационный просмотр): `'off'` или `'none'` - Нет итеративного дисплея `'final'` - Показывать только конечные значения `'iter'` - Показать итеративный дисплей	`'iter'`
`Heuristics`	Алгоритм поиска возможных точек (см. Эвристика поиска возможных решений): `'basic'` `'intermediate'` `'advanced'` `'rss'` `'rins'` `'round'` `'diving'` `'rss-diving'` `'rins-diving'` `'round-diving'` `'none'`	`'basic'`
`HeuristicsMaxNodes`	Строго положительное целое число, ограничивающее число узлов `intlinprog` может исследовать в своем филиале и связанный поиск возможных точек. Применяется только к `'rss'` и `'rins'`. См. раздел Эвристика для поиска возможных решений.	`50`
`IntegerPreprocess`	Типы целочисленной предварительной обработки (см. раздел Смешанная целочисленная предварительная обработка программы): `'none'` - Используйте очень мало шагов предварительной обработки целых чисел. `'basic'` - Используйте умеренное число шагов предварительной обработки целых чисел. `'advanced'` - Использовать все доступные шаги предварительной обработки целых чисел.	`'basic'`
`IntegerTolerance`	Реально от `1e-6` через `1e-3`, где максимальное отклонение от целого числа, которое является компонентом решения `x` может иметь и по-прежнему считаться целым числом. `IntegerTolerance` не является критерием остановки.	`1e-5`
`LPMaxIterations`	Строго положительное целое число, максимальное количество итераций симплексного алгоритма на узел во время процесса ветвления и ограничения.	`max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))` В этом выражении `numberOfEqualities` означает количество строк `Aeq`, `numberOfInequalities` означает количество строк `A`, и `numberOfVariables` означает количество элементов `f`.
`LPOptimalityTolerance`	Неотрицательный реал, где сниженные затраты должны превышать `LPOptimalityTolerance` для переменной, которая должна быть принята в основу.	`1e-7`
LPPreprocess	Тип предварительной обработки решения для ослабленной линейной программы (см. Предварительная обработка линейной программы): `'none'` - Нет предварительной обработки. `'basic'` - Использовать предварительную обработку.	`'basic'`
`MaxNodes`	Строго положительное целое число, которое является максимальным числом узлов `intlinprog` исследует в своем процессе ветвления и связывания.	`1e7`
`MaxFeasiblePoints`	Строго положительное целое число. `intlinprog` останавливается, если находит `MaxFeasiblePoints` целочисленные возможные точки.	`Inf`
`MaxTime`	Положительное реальное значение, которое является максимальным временем в секундах, `intlinprog` бежит.	`7200`
`NodeSelection`	Выберите узел для просмотра. `'simplebestproj'` - Лучшая проекция. См. раздел Ветвление и привязка. `'minobj'` - Исследуйте узел с минимальной целевой функцией. `'mininfeas'` - Исследуйте узел с минимальной суммой целочисленных несходимостей. См. раздел Ветвление и привязка.	`'simplebestproj'`
`ObjectiveCutOff`	В реальности больше, чем `-Inf`. Во время расчета ветвей и границ, `intlinprog` отбрасывает любой узел, где решение линейного программирования имеет целевое значение, превышающее `ObjectiveCutOff`.	`Inf`
`ObjectiveImprovementThreshold`	Ненегативный реал. `intlinprog` изменяет текущее осуществимое решение только в том случае, если оно находит другое с целевым значением функции, которое, по крайней мере, `ObjectiveImprovementThreshold` нижний: (fold - fnew )/( 1 + \| fold \|) > Порог изменения.	`0`
`OutputFcn`	Одна или несколько функций, вызываемых функцией оптимизации при событиях. Укажите как `'savemilpsolutions'`, дескриптор функции или массив ячеек дескрипторов функции. Для пользовательских функций вывода передайте дескрипторы функций. Функция вывода может остановить решатель. `'savemilpsolutions'` собирает целочисленные возможные точки в `xIntSol` матрица в рабочей области, где каждый столбец является одной целочисленной возможной точкой. Сведения о записи пользовательской функции вывода см. в разделах Функция вывода intlinprog и Синтаксис функции печати.	`[]`
`PlotFcn`	Отображает различные показатели прогресса во время выполнения алгоритма; выбрать из предопределенных графиков или написать свой собственный. Проход `'optimplotmilp'`, дескриптор функции или массив ячеек дескрипторов функции. Для пользовательских функций печати передайте дескрипторы функций. Значение по умолчанию - нет (`[]`): `'optimplotmilp'` строит график внутренних вычисленных верхней и нижней границ на целевом значении решения. Сведения о написании пользовательской функции печати см. в разделах Функция вывода intlinprog и Синтаксис функции печати.	`[]`
`RelativeGapTolerance`	Реально от `0` через `1`. `intlinprog` останавливается, если относительная разница между внутренним вычисленным верхним (`U`) и ниже (`L`) границы целевой функции меньше или равны `RelativeGapTolerance`: `(U – L) / (abs(U) + 1) <= RelativeGapTolerance`. `intlinprog` автоматически изменяет допуск для больших `L` величины: допуск = `min(1/(1+\|L\|), RelativeGapTolerance)` Примечание Хотя вы указываете `RelativeGapTolerance` в виде десятичного числа итеративное отображение и `output.relativegap` сообщите о разрыве в процентах, что в 100 раз больше измеренного относительного разрыва. Если сообщение о выходе относится к относительному промежутку, то это значение является измеренным относительным промежутком, а не процентом.	`1e-4`
`RootLPAlgorithm`	Алгоритм решения линейных программ: `'dual-simplex'` - Алгоритм двойного симплекса `'primal-simplex'` - Основной симплексный алгоритм	`'dual-simplex'`
`RootLPMaxIterations`	Неотрицательное целое число, которое является максимальным числом итераций симплексного алгоритма для решения задачи начального линейного программирования.	`max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))` В этом выражении `numberOfEqualities` означает количество строк `Aeq`, `numberOfInequalities` означает количество строк `A`, и `numberOfVariables` означает количество элементов `f`.

Пример: options = optimoptions('intlinprog','MaxTime',120)

`problem` - Структура, инкапсулирующая входные данные и опции
структура

Структура, инкапсулирующая входные данные и опции, указанные в следующих полях.

`f`	Вектор, представляющий цель `f'*x` (обязательно)
`intcon`	Вектор, указывающий переменные, принимающие целочисленные значения (обязательно)
`Aineq`	Матрица в линейных ограничениях неравенства `Aineq*x` ≤ `bineq`
`bineq`	Вектор в линейных ограничениях неравенства `Aineq*x` ≤ `bineq`
`Aeq`	Матрица в линейных ограничениях равенства `Aeq*x = beq`
`beq`	Вектор в линейных ограничениях равенства `Aeq*x = beq`
`lb`	Вектор нижних границ
`ub`	Вектор верхних границ
`x0`	Начальная осуществимая точка
`solver`	`'intlinprog'` (обязательно)
`options`	Параметры, созданные с помощью `optimoptions` (обязательно)

Необходимо указать по крайней мере эти поля в структуре проблемы. Другие поля необязательны:

f
intcon
solver
options

Пример: problem.f = [1,2,3]; problem.intcon = [2,3]; problem.options = optimoptions('intlinprog'); problem.Aineq = [-3,-2,-1]; problem.bineq = -20; problem.lb = [-6.1,-1.2,7.3]; problem.solver = 'intlinprog';

Типы данных: struct

Выходные аргументы

свернуть все

`x` - Решение
действительный вектор

Решение, возвращаемое как вектор, который минимизирует f'*x подчиняется всем ограничениям, целочисленным ограничениям и линейным ограничениям.

Когда проблема неосуществима или безгранична, x является [].

`fval` - Целевое значение
действительный скаляр

Объективное значение, возвращаемое как скалярное значение f'*x на решении x.

Когда проблема неосуществима или безгранична, fval является [].

`exitflag` - Условие остановки алгоритма
целое число

Условие остановки алгоритма, возвращаемое как целое число, определяющее причину остановки алгоритма. Ниже перечислены значения exitflag и соответствующие причины intlinprog остановлено.

`3`	Решение возможно по отношению к родственнику `ConstraintTolerance` допуск, но не осуществим в отношении абсолютного допуска.
`2`	`intlinprog` преждевременно остановлен. Найдена целочисленная возможная точка.
`1`	`intlinprog` сходится к решению `x`.
`0`	`intlinprog` преждевременно остановлен. Целочисленная возможная точка не найдена.
`-1`	`intlinprog` останавливается функцией вывода или функцией графика.
`-2`	Выполнимая точка не найдена.
`-3`	Проблема корневого LP не вызывает проблем.
`-9`	Решатель потерял выполнимость.

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

Exitflags 3 и -9 относятся к решениям, имеющим большие несходимости. Они обычно возникают из матриц линейных ограничений, которые имеют большое число условий, или проблем, которые имеют большие компоненты решения. Чтобы исправить эти проблемы, попробуйте масштабировать матрицы коэффициентов, устранить избыточные линейные ограничения или установить более жесткие границы для переменных.

`output` - Краткое описание процесса решения
структура

Сводка процесса решения, возвращенная в виде структуры, содержащей информацию о процессе оптимизации.

`relativegap`	Относительная процентная разница между верхними (`U`) и ниже (`L`) границы целевой функции, которая `intlinprog` вычисляется в его алгоритме ветвления и ограничения. `relativegap = 100(U - L) / (abs(U) + 1)` Если `intcon = []`, `relativegap = []`. Примечание* Хотя вы указываете `RelativeGapTolerance` в виде десятичного числа итеративное отображение и `output.relativegap` сообщите о разрыве в процентах, что в 100 раз больше измеренного относительного разрыва. Если сообщение о выходе относится к относительному промежутку, то это значение является измеренным относительным промежутком, а не процентом.
`absolutegap`	Разница между верхней и нижней границами целевой функции, которая `intlinprog` вычисляется в его алгоритме ветвления и ограничения. Если `intcon = []`, `absolutegap = []`.
`numfeaspoints`	Найдено целых возможных точек. Если `intcon = []`, `numfeaspoints = []`. Кроме того, если первоначальная ослабленная проблема неосуществима, `numfeaspoints = []`.
`numnodes`	Число узлов в алгоритме ветвления и ограничения. Если раствор был найден во время предварительной обработки или во время начальных отрубов, `numnodes = 0`. Если `intcon = []`, `numnodes = []`.
`constrviolation`	Нарушение ограничения, положительное для нарушенных ограничений. `constrviolation = max([0; norm(Aeqx-beq, inf); (lb-x); (x-ub); (Aix-bi)])`
`message`	Выйти из сообщения.

Ограничения

Часто некоторые предположительно целочисленные компоненты решения 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 не допускает компоненты проблемы, такие как коэффициенты в f, A, или ub, для превышения 1e25 в абсолютном значении. При попытке выполнить intlinprog с такой проблемой, intlinprog выдает ошибку.

Совет

Чтобы задать двоичные переменные, задайте их целыми числами в intcon, и дать им нижние границы 0 и верхние границы 1.
Сохранение памяти путем задания разреженных матриц линейных ограничений A и Aeq. Однако нельзя использовать разреженные матрицы для b и beq.
Если включить x0 аргумент, intlinprog использует это значение в 'rins' и управляемую эвристику погружения до тех пор, пока она не найдет лучшую целочисленную осуществимую точку. Таким образом, когда вы предоставляете x0, вы можете получить хорошие результаты, установив 'Heuristics' опция для 'rins-diving' или другой параметр, использующий 'rins'.
Предоставление логических индексов для целочисленных компонентов, что означает двоичный вектор с 1 указывая целое число, преобразуйте в intcon форма с использованием find. Например,
```
logicalindices = [1,0,0,1,1,0,0];
intcon = find(logicalindices)
```
```
intcon =

     1     4     5
```
intlinprog заменяет bintprog. Обновление старого bintprog код для использования intlinprog, внести следующие изменения:
- Набор intcon кому 1:numVars, где numVars - количество переменных в проблеме.
- Набор lb кому zeros(numVars,1).
- Набор ub кому ones(numVars,1).
- Обновите все соответствующие параметры. Использовать optimoptions для создания параметров intlinprog.
- Изменение звонка на bintprog следующим образом:
  [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)

Альтернативная функциональность

Приложение

Задача «Оптимизировать интерактивный редактор» обеспечивает визуальный интерфейс для intlinprog.

Вопросы совместимости

развернуть все

Дефолт `BranchRule` является `'reliability'`

В R2019a изменилось поведение

Значение по умолчанию для BranchRule опция - 'reliability' вместо 'maxpscost'. При тестировании это значение дало лучшую производительность по многим проблемам, как во времени решения, так и в количестве исследованных узлов ветвления.

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

См. также

linprog | mpsread | Оптимизировать | optimoptions | prob2struct

Темы

Представлен в R2014a

Документация

intlinprog

Синтаксис

Описание

Примеры

Решение MILP с линейными неравенствами

Решение MILP со всеми типами ограничений

Использовать начальную точку

Решение MILP с опциями Nondefault

Решение MILP с помощью проблемного подхода

Анализ решения и процесса MILP

Входные аргументы

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

`intcon` - Вектор целочисленных ограничений
вектор целых чисел

`A` - Матрица ограничений линейного неравенства
реальная матрица

`b` - вектор ограничения линейного неравенства;
действительный вектор

`Aeq` - Матрица ограничений линейного равенства
`[]` (по умолчанию) | вещественная матрица

`beq` - вектор ограничения линейного равенства;
`[]` (по умолчанию) | реальный вектор

`lb` - Нижние границы
`[]` (по умолчанию) | вещественный вектор или массив

`ub` - Верхние границы
`[]` (по умолчанию) | вещественный вектор или массив

`x0` - Начальная точка
`[]` (по умолчанию) | real array

`options` - Опции для `intlinprog`
параметры, созданные с помощью `optimoptions`

`problem` - Структура, инкапсулирующая входные данные и опции
структура

Выходные аргументы

`x` - Решение
действительный вектор

`fval` - Целевое значение
действительный скаляр

`exitflag` - Условие остановки алгоритма
целое число

`output` - Краткое описание процесса решения
структура

Ограничения

Совет

Альтернативная функциональность

Приложение

Вопросы совместимости

Дефолт `BranchRule` является `'reliability'`

См. также

Темы

Документация по панели инструментов оптимизации

Поддержка

Документация

intlinprog

Синтаксис

Описание

Примеры

Решение MILP с линейными неравенствами

Решение MILP со всеми типами ограничений

Использовать начальную точку

Решение MILP с опциями Nondefault

Решение MILP с помощью проблемного подхода

Анализ решения и процесса MILP

Входные аргументы

f - Вектор коэффициентов вещественный вектор | вещественный массив

intcon - Вектор целочисленных ограничений вектор целых чисел

A - Матрица ограничений линейного неравенства реальная матрица

b - вектор ограничения линейного неравенства; действительный вектор

Aeq - Матрица ограничений линейного равенства [] (по умолчанию) | вещественная матрица

beq - вектор ограничения линейного равенства; [] (по умолчанию) | реальный вектор

lb - Нижние границы [] (по умолчанию) | вещественный вектор или массив

ub - Верхние границы [] (по умолчанию) | вещественный вектор или массив

x0 - Начальная точка [] (по умолчанию) | real array

options - Опции для intlinprog параметры, созданные с помощью optimoptions

problem - Структура, инкапсулирующая входные данные и опции структура

Выходные аргументы

x - Решение действительный вектор

fval - Целевое значение действительный скаляр

exitflag - Условие остановки алгоритма целое число

output - Краткое описание процесса решения структура

Ограничения

Совет

Альтернативная функциональность

Приложение

Вопросы совместимости

Дефолт BranchRule является 'reliability'

См. также

Темы

Документация по панели инструментов оптимизации

Поддержка

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

`intcon` - Вектор целочисленных ограничений
вектор целых чисел

`A` - Матрица ограничений линейного неравенства
реальная матрица

`b` - вектор ограничения линейного неравенства;
действительный вектор

`Aeq` - Матрица ограничений линейного равенства
`[]` (по умолчанию) | вещественная матрица

`beq` - вектор ограничения линейного равенства;
`[]` (по умолчанию) | реальный вектор

`lb` - Нижние границы
`[]` (по умолчанию) | вещественный вектор или массив

`ub` - Верхние границы
`[]` (по умолчанию) | вещественный вектор или массив

`x0` - Начальная точка
`[]` (по умолчанию) | real array

`options` - Опции для `intlinprog`
параметры, созданные с помощью `optimoptions`

`problem` - Структура, инкапсулирующая входные данные и опции
структура

`x` - Решение
действительный вектор

`fval` - Целевое значение
действительный скаляр

`exitflag` - Условие остановки алгоритма
целое число

`output` - Краткое описание процесса решения
структура

Дефолт `BranchRule` является `'reliability'`