intlinprog

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

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

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

$\min_{x} f^{T} x подвергающийся {\begin{array}{l} x (intcon) целые числа \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

f, x, intcon, b, beq, lb и ub являются векторами, и A и Aeq являются матрицами.

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

Примечание

intlinprog применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.

Синтаксис

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(problem)

[x,fval,exitflag,output]
= 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 с линейными неравенствами

Скрипт Open Live Script

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

$\min_{x} 8 x_{1} + x_{2} s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{2} i s a n i n t e g e r \\ x_{1} + 2 x_{2} \geq - 14 \\ - 4 x_{1} - x_{2} \leq - 33 \\ 2 x_{1} + x_{2} \leq 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 со всеми типами ограничений

Скрипт Open Live Script

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

$\min_{x} (- 3 x_{1} - 2 x_{2} - x_{3}) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{3} b i n a r y \\ x_{1}, x_{2} \geq 0 \\ x_{1} + x_{2} + x_{3} \leq 7 \\ 4 x_{1} + 2 x_{2} + x_{3} = 12 . \end{array}$

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

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).

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

Скрипт Open Live Script

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

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

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.68         0              -              -                                          
   18188      1.24         1   2.906000e+03   4.509804e+01                                          
   22039      1.60         2   2.073000e+03   2.270974e+01                                          
   24105      1.74         3   1.854000e+03   9.973046e+00                                          
   24531      1.77         3   1.854000e+03   1.347709e+00                                          
   24701      1.78         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.32         2   2.154000e+03   2.593968e+01                                          
    5844      0.50         3   1.854000e+03   1.180593e+01                                          
    6204      0.53         3   1.854000e+03   1.455526e+00                                          
    6400      0.54         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 сделал приблизительно 5 000 шагов.

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

Решите MILP с опциями не по умолчанию

Скрипт Open Live Script

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

не показывая итеративное отображение.

Задайте входные параметры решателя.

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 Используя основанный на проблеме подход

Скрипт Open Live Script

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

Создайте объект 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 и процесс

Скрипт Open Live Script

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

Цель состоит в том, чтобы решить проблему

Задайте входные параметры решателя.

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-by-N, где M является количеством ограничений и N = numel(f). Чтобы сохранить память, A может быть разреженным.

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

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

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

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

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

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

`Aeq` — Линейная матрица ограничений равенства
`[]` (значение по умолчанию) | действительная матрица

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

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

`beq` — Линейный ограничительный вектор равенства
`[]` (значение по умолчанию) | вектор действительных чисел

Линейный ограничительный вектор равенства, заданный как вектор, удваивается. beq представляет постоянный вектор в ограничениях Aeq*x = beq. beq имеет длину Meq, где Aeq является Meq-by-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` Начальная точка
`[]` (значение по умолчанию) | действительный массив

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

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

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

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

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

`опции` Опции для `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'` — Исследуйте узел с минимальной суммой целого числа infeasibilities. Смотрите Ответвление и Связанный.	`'simplebestproj'`
`ObjectiveCutOff`	Действительный больше, чем `-Inf`. Во время вычисления метода ветвей и границ `intlinprog` отбрасывает любой узел, где линейное решение для программирования имеет объективное значение, превышающее `ObjectiveCutOff`.	`Inf`
`ObjectiveImprovementThreshold`	Неотрицательный действительный. `intlinprog` изменяет текущее выполнимое решение только, когда это определяет местоположение другого со значением целевой функции, которое является, по крайней мере`, ObjectiveImprovementThreshold` ниже: (сгиб – fnew) / (1 + \|fold \|)> ObjectiveImprovementThreshold.	0
`OutputFcn`	Задайте одну или несколько функций что оптимизация вызовы функции в событиях как `'savemilpsolutions'`, указатель на функцию или cell-массив указателей на функцию. Для пользовательских выходных функций передайте указатели на функцию. `'savemilpsolutions'` собирает целочисленные допустимые точки в матрице `xIntSol` в вашей рабочей области, где каждый столбец является одной целочисленной допустимой точкой. Для получения информации о записи пользовательской выходной функции см. intlinprog Синтаксис Выходной функции и Функции построения графика.	`[]`
`PlotFcn`	Строит различные меры прогресса, в то время как алгоритм выполняется; выберите из предопределенных графиков или запишите свое собственное. Передайте `'optimplotmilp'`, указатель на функцию или cell-массив указателей на функцию. Для пользовательских функций построения графика передайте указатели на функцию. Значение по умолчанию не ни один (`[]`): `'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'); проблема. 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, такой как превышение допуска.

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

`вывод` Сводные данные процесса решения
структура

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

`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 выдает ошибку.
В настоящее время вы не можете запустить 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)

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

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

BranchRule по умолчанию является 'надежностью'

Поведение изменяется в R2019a

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

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

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

intlinprog

Примечание

Синтаксис

Описание

Примеры

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

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

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

Решите MILP с опциями не по умолчанию

Решите MILP Используя основанный на проблеме подход

Исследуйте решение MILP и процесс

Входные параметры

f Вектор коэффициентов вектор действительных чисел | действительный массив

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

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

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

Aeq — Линейная матрица ограничений равенства [] (значение по умолчанию) | действительная матрица

beq — Линейный ограничительный вектор равенства [] (значение по умолчанию) | вектор действительных чисел

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

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

x0 Начальная точка [] (значение по умолчанию) | действительный массив

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

Примечание

problem — Входные параметры инкапсуляции структуры и опции структура

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

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

fval Объективное значение действительный скаляр

exitflag Алгоритм, останавливающий условие целое число

вывод Сводные данные процесса решения структура

Примечание

Ограничения

Внимание

Советы

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

BranchRule по умолчанию является 'надежностью'

Смотрите также

Темы

Введенный в R2014a

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

Поддержка

`f` Вектор коэффициентов
вектор действительных чисел | действительный массив

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

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

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

`Aeq` — Линейная матрица ограничений равенства
`[]` (значение по умолчанию) | действительная матрица

`beq` — Линейный ограничительный вектор равенства
`[]` (значение по умолчанию) | вектор действительных чисел

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

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

`x0` Начальная точка
`[]` (значение по умолчанию) | действительный массив

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

`problem` — Входные параметры инкапсуляции структуры и опции
структура

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

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

`exitflag` Алгоритм, останавливающий условие
целое число

`вывод` Сводные данные процесса решения
структура