La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

intlinprog

Programación lineal de enteros mixtos (MILP)

Sintaxis

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

Descripción

Solver de programación lineal de enteros mixta.

Encuentra el mínimo de un problema especificado por

$$\underset{x}{\min }{f}^{T}x\text{ subject to }\{\begin{array}{l}x(\text{intcon})\text{ are integers or extended integers}\hfill \\ A\cdot x\le b\hfill \\ Aeq\cdot x=beq\hfill \\ lb\le x\le ub.\hfill \end{array}$$

f, x, intcon, b, beq, lb y ub son vectores, y A y Aeq son matrices.

Puede especificar f, intcon, lb y ub como vectores o arreglos. Consulte Argumentos de matriz.

Nota

intlinprog se aplica únicamente al enfoque basado en solvers. Para ver una exposición sobre los dos enfoques de optimización, consulte En primer lugar, elija el enfoque basado en problemas o el enfoque basado en solvers.

x = intlinprog(f,intcon,A,b) resuelve min f'*x de forma que los componentes de x en intcon son enteros y que A*x ≤ b.

x = intlinprog(f,intcon,A,b,Aeq,beq) resuelve el problema anterior y satisface, al mismo tiempo, las restricciones de igualdad Aeq*x = beq. Establezca A = [] y b = [] si no existen desigualdades.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) define un conjunto de límites inferiores y superiores en las variables de diseño, x, de modo que la solución siempre se encuentra en el rango lb ≤ x ≤ ub. Establezca Aeq = [] y beq = [] si no existen igualdades.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) optimiza utilizando un punto factible inicial x0. Establezca lb = [] y ub = [], si no existen límites.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) minimiza utilizando las opciones de optimización que se especifican en options. Utilice optimoptions para configurar estas opciones. Establezca x0 = [], si no existe ningún punto inicial.

x = intlinprog(problem) utiliza una estructura problem para encapsular todas las entradas de solver. Puede importar una estructura problem de un archivo MPS utilizando mpsread. También puede crear una estructura problem a partir de un objeto OptimizationProblem utilizando prob2struct.

[x,fval,exitflag,output] = intlinprog(___), para cualquiera de los argumentos de entrada que se describen arriba, devuelve fval = f'*x, un valor exitflag que describe la condición de salida, y una estructura output que contiene información sobre el proceso de optimización.

Ejemplos

Resolver una MILP con desigualdades lineales

Resuelva el problema

$$\underset{x}{\min }8x_1+x_{2}subjectto\{\begin{array}{l}{x}_{2}isaninteger\\ x_1+2x_2\ge -14\\ -4x_1-x_2\le -33\\ 2x_1+x_2\le 20.\end{array}$$

Escriba el vector de función objetivo y el vector de variables enteras.

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

Convierta todas las desigualdades al formato A*x <= b multiplicando las desigualdades "mayor que" por -1.

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

Llame a 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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

x = 2×1

    6.5000
    7.0000

Resolver una MILP con todos los tipos de restricciones

Resuelva el problema

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12.\end{array}$$

Escriba el vector de función objetivo y el vector de variables enteras.

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

Escriba las restricciones de desigualdad lineales.

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

Escriba las restricciones de igualdad lineales.

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

Escriba las restricciones de límite.

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

Llame a 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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

x = 3×1

         0
    5.5000
    1.0000

Utilizar un punto inicial

Compare el número de pasos para resolver un problema de programación de enteros tanto con un punto factible inicial como sin él. El problema tiene ocho variables y cuatro restricciones de igualdad lineales, y tiene todas las variables restringidas para ser positivas.

Defina la matriz y el vector de igualdad lineales.

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];

Establezca límites inferiores que restrinjan todas las variables para que sean no negativas.

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

Especifique que todas las variables son valores enteros.

intcon = 1:N;

Establezca el vector de función objetivo f.

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

Resuelva el problema sin utilizar un punto inicial y examine la visualización para ver el número de nodos de ramificación y acotación.

[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.90         0              -              -                                          
   14739      1.24         1   2.154000e+03   2.593968e+01                                          
   18258      1.56         2   1.854000e+03   1.180593e+01                                          
   18673      1.60         2   1.854000e+03   1.563342e+00                                          
   18829      1.61         2   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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

Encuentre la solución utilizando un punto factible inicial y compare.

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.46         2   2.154000e+03   2.593968e+01                                          
    5844      0.68         3   1.854000e+03   1.180593e+01                                          
    6204      0.71         3   1.854000e+03   1.455526e+00                                          
    6400      0.73         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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

• Sin un punto inicial, intlinprog necesitó unos 30.000 pasos de ramificación y acotación.

• Con un punto inicial, intlinprog necesitó unos 5.000 pasos.

Proporcionar un punto inicial no siempre ayuda. Para este problema, proporcionar un punto inicial ahorra tiempo y pasos computacionales. Sin embargo, para algunos problemas, proporcionar un punto inicial puede provocar que intlinprog dé más pasos.

Resolver una MILP con opciones no predeterminadas

Resuelva el problema

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12\end{array}$$

sin mostrar una visualización iterativa.

Especifique las entradas del solver.

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 = [];

No especifique ninguna visualización.

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

Ejecute el solver.

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

x = 3×1

         0
    5.5000
    1.0000

Resolver una MILP utilizando un enfoque basado en problemas

Este ejemplo muestra cómo configurar un problema utilizando el enfoque basado en problemas y cómo resolverlo utilizando el enfoque basado en solvers. El problema es

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12\end{array}$$

Cree un objeto OptimizationProblem llamado prob para representar este problema. Para especificar una variable binaria, cree una variable de optimización con tipo de entero, un límite inferior de 0 y un límite superior de 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;

Convierta el objeto de problema en una estructura de problema.

problem = prob2struct(prob);

Resuelva la estructura de problema resultante.

[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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

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

Tanto sol(1) como sol(3) tienen valores binarios. ¿Qué valor corresponde a la variable de optimización binaria xb?

prob.Variables

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

La variable xb aparece la última en la visualización Variables, por lo que xb se corresponde con sol(3) = 1. Consulte Algorithms.

Examinar la resolución de una MILP y el proceso

Llame a intlinprog con más salidas para ver los detalles de la resolución y del proceso.

El objetivo es resolver el problema

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12.\end{array}$$

Especifique las entradas del solver.

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

Llame a intlinprog con todas las salidas.

[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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.

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

La estructura de salida muestra que numnodes es 0. Esto significa que intlinprog resolvió el problema antes de ramificar. Es una indicación de que el resultado es fiable. Asimismo, los campos absolutegap y relativegap son 0. Esta es otra indicación de que el resultado es fiable.

Argumentos de entrada

f — Vector de coeficientes

vector real | arreglo real

Vector de coeficientes, especificado como un vector real o un arreglo real. El vector de coeficientes representa la función objetivo f'*x. La notación asume que f es un vector columna, pero usted es libre de utilizar un vector fila o un arreglo. Internamente, linprog convierte f en el vector columna f(:).

Si especifica f = [], intlinprog trata de encontrar un punto factible sin intentar minimizar una función objetivo.

Ejemplo: f = [4;2;-1.7];

Tipos de datos: double

intcon — Vector de restricciones de enteros

vector de enteros

Vector de restricciones de enteros, especificado como un vector de enteros positivos. Los valores de intcon indican los componentes de la variable de decisión x que son valores enteros. intcon tiene valores de 1 a numel(f).

intcon también puede ser un arreglo. Internamente, intlinprog convierte un arreglo intcon en el vector intcon(:).

Ejemplo: intcon = [1,2,7] significa que x(1), x(2) y x(7) solo toman valores enteros.

Tipos de datos: double

A — Restricciones de desigualdad lineales

matriz real

Restricciones de desigualdad lineales, especificadas como una matriz real. A es una matriz de M por N, donde M es el número de desigualdades y N es el número de variables (longitud de f). Para problemas grandes, pase A como una matriz dispersa.

A codifica las M desigualdades lineales

A*x <= b,

donde x es el vector columna de N variables x(:) y b es un vector columna con M elementos.

Por ejemplo, considere estas desigualdades:

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

Especifique las desigualdades introduciendo las siguientes restricciones.

A = [1,2;3,4;5,6];
b = [10;20;30];

Ejemplo: Para especificar que los componentes de x suman 1 o menos, tome A = ones(1,N) y b = 1.

Tipos de datos: double

b — Restricciones de desigualdad lineales

vector real

Restricciones de desigualdad lineales, especificadas como un vector real. b es un vector de M elementos relacionado con la matriz A. Si pasa b como un vector fila, los solvers convierten internamente b en el vector columna b(:). Para problemas grandes, pase b como un vector disperso.

b codifica las M desigualdades lineales

A*x <= b,

donde x es el vector columna de N variables x(:) y A es una matriz de tamaño M por N.

Por ejemplo, considere estas desigualdades:

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

Especifique las desigualdades introduciendo las siguientes restricciones.

A = [1,2;3,4;5,6];
b = [10;20;30];

Ejemplo: Para especificar que los componentes de x suman 1 o menos, utilice A = ones(1,N) y b = 1.

Tipos de datos: double

Aeq — Restricciones de igualdad lineales

matriz real

Restricciones de igualdad lineales, especificadas como una matriz real. Aeq es una matriz de Me por N, donde Me es el número de igualdades y N es el número de variables (longitud de f). Para problemas grandes, pase Aeq como una matriz dispersa.

Aeq codifica las Me igualdades lineales

Aeq*x = beq,

donde x es el vector columna de N variables x(:) y beq es un vector columna con Me elementos.

Por ejemplo, considere estas igualdades:

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

Especifique las igualdades introduciendo las siguientes restricciones.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Ejemplo: Para especificar que los componentes de x suman 1, tome Aeq = ones(1,N) y beq = 1.

Tipos de datos: double

beq — Restricciones de igualdad lineales

vector real

Restricciones de igualdad lineales, especificadas como un vector real. beq es un vector de Me elementos relacionado con la matriz Aeq. Si pasa beq como un vector fila, los solvers convierten internamente beq en el vector columna beq(:). Para problemas grandes, pase beq como un vector disperso.

beq codifica las Me igualdades lineales

Aeq*x = beq,

donde x es el vector columna de N variables x(:) y Aeq es una matriz de tamaño Me por N.

Por ejemplo, considere estas igualdades:

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

Especifique las igualdades introduciendo las siguientes restricciones.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Ejemplo: Para especificar que los componentes de x suman 1, utilice Aeq = ones(1,N) y beq = 1.

Tipos de datos: double

lb — Límites inferiores

[] (predeterminado) | vector o arreglo real

Límites inferiores, especificados como un vector o un arreglo de dobles. lb representa los límites inferiores por elementos en lb ≤ x ≤ ub.

Internamente, intlinprog convierte un arreglo lb en el vector lb(:).

Ejemplo: lb = [0;-Inf;4] significa x(1) ≥ 0, x(3) ≥ 4.

Tipos de datos: double

ub — Límites superiores

[] (predeterminado) | vector o arreglo real

Límites superiores, especificados como un vector o un arreglo de dobles. ub representa los límites superiores por elementos en lb ≤ x ≤ ub.

Internamente, intlinprog convierte un arreglo ub en el vector ub(:).

Ejemplo: ub = [Inf;4;10] significa x(2) ≤ 4, x(3) ≤ 10.

Tipos de datos: double

x0 — Punto inicial

[] (predeterminado) | arreglo real

Punto inicial, especificado como un arreglo real. El número de elementos de x0 es el mismo que el número de elementos de f, cuando existe f. De lo contrario, el número es el mismo que el número de columnas de A o de Aeq. Internamente, el solver convierte un arreglo x0 en un vector x0(:).

Proporcionar x0 puede cambiar la cantidad de tiempo que necesita intlinprog para convergir. Es difícil predecir cómo x0 afecta al solver. Para sugerencias sobre cómo utilizar una Heuristics adecuada con x0, consulte Consejos.

x0 debe ser factible con respecto a todas las restricciones. Si x0 no es factible, el solver genera un error. Si no tiene un x0 factible, establezca x0 = [].

Ejemplo: x0 = 100*rand(size(f))

Tipos de datos: double

options — Opciones para intlinprog

opciones creadas utilizando optimoptions

Opciones para intlinprog, especificadas como la salida de optimoptions.

Algunas opciones no aparecen en la visualización optimoptions. Estas opciones se muestran en cursiva en la siguiente tabla. Para obtener más detalles, consulte Consultar las opciones de optimización.

Opción	Descripción	Valor predeterminado
AbsoluteGapTolerance	Valor real no negativo. intlinprog se detiene si la diferencia entre los límites superior (U) e inferior (L) calculados internamente en la función objetivo es menor que o igual a AbsoluteGapTolerance: U – L <= AbsoluteGapTolerance.	0
BranchRule	Regla para escoger el componente para la ramificación: 'maxpscost': el componente fraccional con el máximo pseudocoste. Consulte Ramificación y acotación. 'strongpscost': el componente fraccional con el máximo pseudocoste y una estimación más precisa del pseudocoste que en 'maxpscost'. Consulte Ramificación y acotación. 'reliability': el componente fraccional con el máximo pseudocoste y una estimación incluso más precisa del pseudocoste que en 'strongpscost'. Consulte Ramificación y acotación. 'mostfractional': el componente cuya parte fraccional es la que más se acerca a 1/2. 'maxfun': el componente fraccional con un componente correspondiente máximo en el valor absoluto del vector objetivo f.	'reliability'
ConstraintTolerance	Valor real de 1e-9 a 1e-3 que es la discrepancia máxima que pueden tener las restricciones lineales para que se sigan considerando satisfactorias. ConstraintTolerance no es un criterio de detención.	1e-4
CutGeneration	Nivel de generación de corte (consulte Generación de cortes): 'none': ningún corte. Hace que CutMaxIterations sea irrelevante. 'basic': generación de corte normal. 'intermediate': utiliza más tipos de corte. 'advanced': utiliza la mayoría de tipos de corte.	'basic'
CutMaxIterations	Número de pases por todos los métodos de generación de cortes antes de entrar en la fase de ramificación y acotamiento, un entero de 1 a 50. Deshabilite la generación de cortes estableciendo la opción CutGeneration en 'none'.	10
Display	Nivel de visualización (consulte Visualización iterativa): 'off' o 'none': sin visualización iterativa 'final': muestra solo los valores finales 'iter': muestra la visualización iterativa	'iter'
Heuristics	Algoritmo para buscar puntos factibles (consulte Heurística para encontrar soluciones factibles): 'basic' 'intermediate' 'advanced' 'rss' 'rins' 'round' 'diving' 'rss-diving' 'rins-diving' 'round-diving' 'none'	'basic'
HeuristicsMaxNodes	Entero estrictamente positivo que limita el número de nodos que puede explorar intlinprog en su búsqueda de ramificación y acotación de puntos factibles. Se aplica únicamente a 'rss' y a 'rins'. Consulte Heurística para encontrar soluciones factibles.	50
IntegerPreprocess	Tipos de preprocesamiento de enteros (consulte Preprocesamiento de programas de enteros mixtos): 'none': utiliza muy pocos pasos de preprocesamiento de enteros. 'basic': utiliza un número moderado de pasos de preprocesamiento de enteros. 'advanced': utiliza todos los pasos de preprocesamiento de enteros disponibles.	'basic'
IntegerTolerance	Valor real de 1e-6 a 1e-3, donde se da la desviación máxima del entero que puede tener un componente de la solución x para que se siga considerando un entero. IntegerTolerance no es un criterio de detención.	1e-5
LPMaxIterations	Entero estrictamente positivo, el número máximo de iteraciones de algoritmo simplex por nodo durante el proceso de ramificación y acotamiento.	max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)) En esta expresión, numberOfEqualities significa el número de filas de Aeq, numberOfInequalities significa el número de filas de A y numberOfVariables significa el número de elementos de f.
LPOptimalityTolerance	Valor real no negativo donde los costes reducidos deben superar LPOptimalityTolerance para que una variable se incorpore a la base.	1e-7
LPPreprocess	Tipo de preprocesamiento para la solución al programa lineal relajado (consulte Preprocesamiento de la programación lineal): 'none': sin preprocesamiento. 'basic': utiliza preprocesamiento.	'basic'
MaxNodes	Entero estrictamente positivo que es el número máximo de nodos que explora intlinprog en su proceso de ramificación y acotación.	1e7
MaxFeasiblePoints	Entero estrictamente positivo. intlinprog se detiene si encuentra MaxFeasiblePoints puntos factibles enteros.	Inf
MaxTime	Valor real positivo que es el tiempo máximo en segundos que se ejecuta intlinprog.	7200
NodeSelection	Escoja el nodo que desea explorar a continuación. 'simplebestproj': mejor proyección. Consulte Ramificación y acotación. 'minobj': explora el nodo con la función objetivo mínima. 'mininfeas': explora el nodo con la suma mínima de infactibilidades enteras. Consulte Ramificación y acotación.	'simplebestproj'
ObjectiveCutOff	Valor real mayor que -Inf. Durante el cálculo de ramificación y acotación, intlinprog descarta los nodos en los que la solución de programación lineal tiene un valor objetivo mayor que ObjectiveCutOff.	Inf
ObjectiveImprovementThreshold	Valor real no negativo. intlinprog cambia la solución factible actual solo cuando ubica otra con un valor de función objetivo que es al menos menor que ObjectiveImprovementThreshold: (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold.	0
OutputFcn	Una o más funciones que una función de optimización llama en eventos. Especifíquelas como 'savemilpsolutions', un identificador de función o un arreglo de celdas de identificadores de función. Para funciones de salida personalizadas, pase identificadores de función. Una función de salida puede detener el solver. 'savemilpsolutions' recopila los puntos factibles enteros en la matriz xIntSol del espacio de trabajo, donde cada columna es un punto factible entero. Para obtener más información sobre escribir una función de salida personalizada, consulte intlinprog Output Function and Plot Function Syntax.	[]
PlotFcn	Representa varias medidas de progreso mientras el algoritmo se ejecuta; seleccione una de las gráficas predefinidas o escriba la suya propia. Pase 'optimplotmilp', un identificador de función o un arreglo de celdas de identificadores de función. Para funciones de gráfica personalizadas, pase identificadores de función. La opción predeterminada es ninguno ([]): 'optimplotmilp' representa los límites superiores e inferiores calculados internamente en el valor objetivo de la solución. Para obtener más información sobre cómo escribir una función de gráfica personalizada, consulte intlinprog Output Function and Plot Function Syntax.	[]
RelativeGapTolerance	Valor real de 0 a 1. intlinprog se detiene si la diferencia relativa entre los límites superior (U) e inferior (L) calculados internamente en la función objetivo es menor que o igual a RelativeGapTolerance: (U – L)/(|U| + 1) <= RelativeGapTolerance. Nota Aunque especifique RelativeGapTolerance como un número decimal, la visualización iterativa y output.relativegap indican el intervalo como un porcentaje, lo que significa 100 veces el intervalo relativo medido. Si el mensaje de salida se refiere al intervalo relativo, este valor es el intervalo relativo medido, no un porcentaje.	1e-4
RootLPAlgorithm	Algoritmo para resolver programas lineales: 'dual-simplex': algoritmo dual simplex 'primal-simplex': algoritmo primal simplex	'dual-simplex'
RootLPMaxIterations	Entero no negativo que es el número máximo de iteraciones del algoritmo simplex para resolver el problema de programación lineal inicial.	max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)) En esta expresión, numberOfEqualities significa el número de filas de Aeq, numberOfInequalities significa el número de filas de A y numberOfVariables significa el número de elementos de f.

Ejemplo: options = optimoptions('intlinprog','MaxTime',120)

problem — Estructura que encapsula entradas y opciones

estructura

Estructura que encapsula las entradas y las opciones, especificada con los siguientes campos.

f	Vector que representa f'*x objetivo (necesario)
intcon	Vector que indica variables que toman valores enteros (necesario)
Aineq	Matriz en restricciones de desigualdad lineales Aineq*x ≤ bineq
bineq	Vector en restricciones de desigualdad lineales Aineq*x ≤ bineq
Aeq	Matriz en restricciones de igualdad lineales Aeq*x = beq
beq	Vector en restricciones de igualdad lineales Aeq*x = beq
lb	Vector de límites inferiores
ub	Vector de límites superiores
x0	Punto factible inicial
solver	'intlinprog' (necesario)
options	Opciones creadas utilizando optimoptions (necesario)

Debe especificar al menos estos campos en la estructura del problema. Otros campos son opcionales:

• f

• intcon

• solver

• options

Ejemplo: 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';

Tipos de datos: struct

Argumentos de salida

x — Solución

vector real

Solución, devuelta como un vector que minimiza f'*x sujeto a todos los límites, restricciones de enteros y restricciones lineales.

Cuando un problema no es factible o está desacotado, x es [].

fval — Valor objetivo

escalar real

Valor objetivo, devuelto como el valor escalar f'*x en la solución x.

Cuando un problema no es factible o está desacotado, fval es [].

exitflag — Condición de detención de algoritmo

valor entero

Condición de detención de algoritmo, devuelta como un entero que identifica la razón por la que el algoritmo se detuvo. A continuación, se enumeran los valores de exitflag y las razones correspondientes por las que intlinprog se detuvo.

3	La solución es factible con respecto a la tolerancia ConstraintTolerance relativa, pero no es factible en lo que respecta a la tolerancia absoluta.
2	intlinprog se detuvo prematuramente. Punto factible inicial encontrado.
1	intlinprog ha convergido a la solución x.
0	intlinprog se detuvo prematuramente. No se ha encontrado ningún punto factible inicial.
-1	intlinprog detenido por una función de salida o una función de gráfica.
-2	No se ha encontrado ningún punto factible.
-3	El problema de LP de raíz está desacotado.
-9	El solver ha perdido factibilidad.

El mensaje de salida puede proporcionar información más detallada sobre la razón por la que intlinprog se detuvo, como sobrepasar la tolerancia.

Los exitflag 3 y -9 están relacionados con soluciones que tienen infactibilidades amplias. Estas normalmente surgen de matrices de restricciones lineales que tienen un elevado número de condiciones, o de problemas que tienen un elevado número de componentes de solución. Para corregir estos problemas, intente escalar las matrices de coeficientes, eliminar las restricciones lineales redundantes o establecer límites más estrictos en las variables.

output — Resumen de un proceso de resolución

estructura

Resumen de un proceso de resolución, devuelto como una estructura que contiene información sobre el proceso de optimización.

relativegap	Diferencia de porcentaje relativa entre los límites superiores (U) e inferiores (L) de la función objetivo que calcula intlinprog en su algoritmo de ramificación y acotación. relativegap = 100*(U - L) / (abs(U) + 1) Si intcon = [], relativegap = []. Nota Aunque especifique RelativeGapTolerance como un número decimal, la visualización iterativa y output.relativegap indican el intervalo como un porcentaje, lo que significa 100 veces el intervalo relativo medido. Si el mensaje de salida se refiere al intervalo relativo, este valor es el intervalo relativo medido, no un porcentaje.
absolutegap	Diferencia entre los límites superiores e inferiores de la función objetivo que calcula intlinprog en su algoritmo de ramificación y acotación. Si intcon = [], absolutegap = [].
numfeaspoints	Número de puntos factibles enteros encontrados. Si intcon = [], numfeaspoints = []. Asimismo, si el problema relajado inicial no es factible, numfeaspoints = [].
numnodes	Número de nodos en el algoritmo de ramificación y acotación. Si se encontró la solución durante el preprocesamiento o durante los cortes iniciales, numnodes = 0. Si intcon = [], numnodes = [].
constrviolation	Vulneración de restricciones que es positiva para las restricciones vulneradas. constrviolation = max([0; norm(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-bi)])
message	Mensaje de salida.

Limitaciones

• Con frecuencia, algunos componentes que supuestamente son valores enteros de la solución x(intCon) no son exactamente enteros. intlinprog considera como enteros todos los valores de solución dentro de la IntegerTolerance de un entero.

  Para redondear todos los supuestos enteros para que sean enteros exactos, utilice la función round.

  x(intcon) = round(x(intcon));

  Precaución

  Las soluciones de redondeo pueden provocar que la solución se convierta en no factible. Compruebe la factibilidad después del redondeo:

  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 no exige que los componentes de la solución tengan valores enteros cuando sus valores absolutos sobrepasan 2.1e9. Cuando la solución tiene esos componentes, intlinprog le advierte. Si recibe esta advertencia, compruebe la solución para ver si los componentes que supuestamente tienen valores enteros de la solución están cerca de los enteros.

• intlinprog no permite que los componentes del problema, como los coeficientes de f, A o ub, sobrepasen 1e25 en valor absoluto. Si intenta ejecutar intlinprog con un problema de ese tipo, intlinprog genera un error.

Sugerencias

• Para especificar valores binarios, establezca que las variables sean enteros en intcon y proporcióneles límites inferiores de 0 y límites superiores de 1.

• Ahorre memoria especificando las matrices de restricciones lineales dispersas A y Aeq. Sin embargo, no puede utilizar matrices dispersas para b y beq.

• Si incluye un argumento x0, intlinprog utiliza este valor en la heurística 'rins' y en la heurística de inmersión guiada hasta que encuentra un punto factible entero mejor. Así, cuando proporciona x0, puede obtener buenos resultados estableciendo la opción 'Heuristics' en 'rins-diving' u otro ajuste que utiliza 'rins'.

• Para proporcionar índices lógicos para componentes enteros, es decir, un vector binario en el que 1 indica un entero, convierta al formato intcon utilizando find. Por ejemplo:

  logicalindices = [1,0,0,1,1,0,0];
  intcon = find(logicalindices)

  intcon =
  
       1     4     5

• intlinprog reemplaza a bintprog. Para actualizar código bintprog antiguo para utilizar intlinprog, realice los siguientes cambios:

  • Establezca intcon en 1:numVars, donde numVars es el número de variables del problema.

  • Establezca lb en zeros(numVars,1).

  • Establezca ub en ones(numVars,1).

  • Actualice todas las opciones relevantes. Utilice optimoptions para crear opciones para intlinprog.

  • Cambie la llamada a bintprog como sigue:

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

Funcionalidad alternativa

App

La tarea Optimize de Live Editor proporciona una interfaz visual para intlinprog.

Historial de versiones

Introducido en R2014a

R2019a: El valor predeterminado de BranchRule es 'reliability'

El valor predeterminado de la opción BranchRule es 'reliability' en lugar de 'maxpscost'. En pruebas, este valor proporcionó un rendimiento mejor en muchos problemas, tanto en los tiempos de resolución como en el número de nodos de ramificación explorados.

En unos pocos problemas, la regla de ramificación anterior tiene un rendimiento mejor. Para obtener el comportamiento anterior, establezca la opción BranchRule en 'maxpscost'.

Consulte también

linprog | mpsread | optimoptions | prob2struct | Optimize

Temas

• Aspectos básicos de la programación lineal de enteros mixtos: Basado en solvers
• Factory, Warehouse, Sales Allocation Model: Solver-Based
• Problema del viajante: Basado en solvers
• Solve Sudoku Puzzles via Integer Programming: Solver-Based
• Mixed-Integer Quadratic Programming Portfolio Optimization: Solver-Based
• Optimal Dispatch of Power Generators: Solver-Based
• Algoritmos de programación lineal de enteros mixtos (MILP)
• Tuning Integer Linear Programming
• Configuración de problema de optimización basada en solvers