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

Описание

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

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

minxfTx при условии , что {x(intcon) являются целыми числамиA⋅x≤bAeq⋅x=beqlb≤x≤ub.

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 содержащая информацию о процессе оптимизации.

Примеры

свернуть все

Открыть Live Script

Решите задачу

minx8x1+x2subjectto{x2isanintegerx1+2x2≥-14-4x1-x2≤-332x1+x2≤20.

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

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

x = 2×1

    6.5000
    7.0000
Открыть Live Script

Решите задачу

minx(-3x1-2x2-x3)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).

x = 3×1

         0
    5.5000
    1.0000
Открыть 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 предпринять больше шагов.

Открыть Live Script

Решите задачу

minx(-3x1-2x2-x3)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)
x = 3×1

         0
    5.5000
    1.0000
Открыть Live Script

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

minx(-3x1-2x2-x3)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).

sol = 3×1

         0
    5.5000
    1.0000


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. См. Алгоритмы.

Открыть Live Script

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

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

minx(-3x1-2x2-x3)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).

x = 3×1

         0
    5.5000
    1.0000


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'*x. Это обозначение принимает, что f является вектор-столбец, но вы можете свободно использовать вектор-строку или массив. Внутренне, linprog преобразует f в вектор-столбец f(:).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: ub = [Inf;4;10] означает x(2) ≤ 4, x(3) ≤ 10.

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

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

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

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

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

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

Опции для 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)

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

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

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

свернуть все

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

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

Целевое значение, возвращенное как скалярное значение f'*x в решении x.

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

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

3

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

2

intlinprog остановлен преждевременно. Найдена целочисленная допустимая точка.

1

intlinprog сходился к решению x.

0

intlinprog остановлен преждевременно. Целое число допустимая точка не найдено.

-1

intlinprog остановлен выходной функцией или функцией построения графика.

-2

Допустимая точка не найдена.

-3

Корневая задача LP неограниченна.

-9

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

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

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

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

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(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-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.

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

расширить все

Поведение изменено в R2019a

См. также

| | | |

Темы

Введенный в R2014a

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

Поддержка

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