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

пример

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

Примеры

свернуть все

Скрипт Open 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
Скрипт Open 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
Скрипт 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.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 сделал приблизительно 5 000 шагов.

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

Скрипт Open 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
Скрипт Open 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. См. алгоритмы.

Скрипт Open 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)x2 , и x(7) примите только целочисленные значения.

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

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

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

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

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

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

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

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

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

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

Линейный вектор ограничения равенства в виде вектора из удваивается. beq представляет постоянный вектор в ограничениях Aeq*x = beq. beq имеет длину Meq, где Aeq Meq- 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 \exists. В противном случае номер совпадает с количеством столбцов 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 ниже: (сгиб – 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)

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

fВектор, представляющий объективный f'*x (необходимый)
intconПеременные указания вектора, которые принимают (требуемые) целочисленные значения
AineqМатрица в линейных ограничениях неравенства Aineq*x ≤ bineq

bineq

Вектор в линейных ограничениях неравенства Aineq*x ≤ bineq

Aeq

Матрица в линейных ограничениях равенства   Aeq*x = beq

beq

Вектор в линейных ограничениях равенства   Aeq*x = beq
lbВектор из нижних границ
ubВектор из верхних границ
x0Начальная допустимая точка
solver'intlinprog' (необходимый)

options

Опции создали использование optimoptions (необходимый)

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

  • f

  • intcon

  • solver

  • options

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

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

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

свернуть все

Решение, возвращенное как вектор, который минимизирует 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 остановленный, такие как превышение допуска.

Exitflags 3 и -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(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 не позволяет компоненты проблемы, такие как коэффициенты в fA, или 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)

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

Приложение

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

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

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

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

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

| | | |

Темы

Введенный в R2014a

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

Поддержка

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