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

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

Описание

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

Находит минимум задачи, заданной в

$\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 применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите Первый выбор Основанного на проблеме или Основанный на решателе подход.

пример

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 с линейными неравенствами

Открыть 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 со всеми типами ограничений

Открыть 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).

Использование начальной точки

Открыть 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.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

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

Открыть 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

Открыть 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....'

Система структуры output показов 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` - Нижние границы
`[]` (по умолчанию) | вектор действительных чисел или массив

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

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

Пример: lb = [0;-Inf;4] означает x(1) ≥ 0, x(3) ≥ 4.

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

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

Верхние границы, заданные как вектор или массив типа double. 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

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

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

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

`relativegap`	Относительное процентное различие между верхними (`U`) и ниже (`L`) ограничения целевой функции, которые `intlinprog` вычисляет в своем алгоритме branch-and-bound. `relativegap = 100(U - L) / (abs(U) + 1)` Если `intcon = []`, `relativegap = []`. Примечание* Хотя вы задаете `RelativeGapTolerance` как десятичное число, итеративное отображение и `output.relativegap` сообщите погрешность в процентах, что означает 100-кратное измерение относительного промежутка. Если выходное сообщение ссылается на относительный промежуток, это значение является измеренным относительным промежутком, а не процентом.
`absolutegap`	Различие между верхней и нижней границами целевой функции, что `intlinprog` вычисляет в своем алгоритме branch-and-bound. Если `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)

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

Приложение

Задача Optimize Live Editor обеспечивает визуальный интерфейс для 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` - Начальная точка
`[]` (по умолчанию) | вещественный массив

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

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

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

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

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

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

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

Ограничения

Совет

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

Приложение

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

Значения по умолчанию `BranchRule` является `'reliability'`

См. также

Темы

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

Поддержка

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

intlinprog

Синтаксис

Описание

Примеры

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

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

Использование начальной точки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

Совет

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

Приложение

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

Значения по умолчанию BranchRule является 'reliability'

См. также

Темы

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

Поддержка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значения по умолчанию `BranchRule` является `'reliability'`