SPOILER_Modelos_y_Optimizaci_n_I___71_14

Vista previa del material en texto

Modelos y Optimización I
Resumen de Problemas Tipo
Última modificación: Noviembre 2020
Colaboradores
Mauro Parafati - mparafati@fi.uba.ar
Nicolas Aguerre - naguerre@fi.uba.ar
Santiago Klein - sklein@fi.uba.ar
Taiel Colavecchia - tcolavecchia@fi.uba.ar
Yuhong Huang - yhuang@fi.uba.ar
Problemas de decisión Modelos y Optimización I - FIUBA
Índice
1. Hipótesis generales 2
2. Problemas Tipo 3
2.1. Producción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Problema del viajante (TSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3. Problema de distribución o transporte . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4. Cobertura de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5. Secuenciamiento de tareas (Scheduling) . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6. Satisfacibilidad booleana (SAT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7. Problema de la mochila (Knapsack) . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.8. Coloreo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Agregados 14
3.1. Mezcla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2. Armado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3. Multiperíodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4. Esquema modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5. Programación de metas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6. Restricciones lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.7. Costos variables por intervalo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.8. Curva cóncava seccionalmente lineal . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1
Problemas de decisión Modelos y Optimización I - FIUBA
1. Hipótesis generales
Inflación.
Proporcionalidad de gastos e/o ingresos.
Aditividad de gastos e/o ingresos.
Certeza de gastos e/o ingresos.
Certeza sobre restricciones.
Divisibilidad. Enteros vs fraccionarios.
Suficiencia de tiempo para producir/hacer todo lo que indique el modelo.
Indistinguibilidad entre productos
2
Problemas de decisión Modelos y Optimización I - FIUBA
2. Problemas Tipo
2.1. Producción
En general se tendrá que producir un cierto producto con costos, mano de obra, tiempos o
materia prima limitantes, para luego venderlo obteniendo ingresos.
2.1.1. Objetivo
Normalmente, será maximizar los ingresos por ventas, o la ganancia neta (ingresos− costos)
o minimizar los costos.
2.1.2. Hipótesis
Sobre stock inicial y final de productos y/o materias primas.
Sobre restricciones de demanda minima y maxima.
Sobre desperdicios de recursos.
2.1.3. Posibles variantes
Múltiples centros de producción. Se modela utilizando módulos para cada centro.
3
Problemas de decisión Modelos y Optimización I - FIUBA
2.2. Problema del viajante (TSP)
Se tiene una situacion en el cual un viajante debe recorrer un conjunto de ciudades para luego
volver al punto de partida; el problema del viajante consiste en hallar la forma mas eficiente de
visitar todas las ciudades y volver al punto de origen, sin repetir ninguna (excepto el propio punto
de partida).
Formalmente: dado un grafo G = (V,E), determinar (si es que existe) el minimo ciclo
hamiltoniano (es decir, un ciclo que pase por todos los vértices sin repetir ninguno, excepto el
punto de partida).
2.2.1. Objetivo
Siempre se debe definir el orden de recorrido relacionado al costo o longitud (sea temporal o
espacial) del ciclo.
2.2.2. Hipótesis
La partida y llegada son en el mismo punto.
Que se pase una única vez por todos los vértices del grafo.
A menos que haya restricciones que indiquen lo contrario, se puede hacer un camino entre
cualquier par de vértices.
2.2.3. Variables
Se hace el recorrido del vertice de i a j: (i, j ∈ {1, ..., N}) Yi,j bivalente, indica si se tomó el
camino de i a j (i 6= j).
Secuencias de recorrido (MTZ): Ui ≥ 0 indica en qué momento de la secuencia se visitó al
vértice i > 0.
2.2.4. Restricciones
Sólo se llega a cada vértice por un camino: (∀i)∑
j 6=i
Yj,i = 1
Sólo se sale de cada vértice por un camino: (∀i)∑
j 6=i
Yi,j = 1
Definimos el orden secuencial en todo el grafo, para evitar subtours (MTZ): (∀i, j, i 6= j)
Ui − Uj +N ∗ Yi,j ≤ N − 1
2.2.5. Funcional
Z :=
∑
i 6=j
Ci,j ∗ Yi,j →MIN
4
Problemas de decisión Modelos y Optimización I - FIUBA
2.2.6. Posibles variantes
Se requiere un camino semi-hamiltoniano (recorrer sin repetir todos los vértices del grafo, sin
repetir ninguno por lo que se finaliza en un vértice diferente al que se comenzó), simplemente
se debe agregar un vértice al grafo que conecte con todo el resto (en principio con costo y/o
distancia 0).
Múltiples aristas: Yi,j =
∑
t∈Transporte Yi,j,t donde se prende además sólo la variable que
indica si se utiliza la arista t entre los vértices i y j.
5
Problemas de decisión Modelos y Optimización I - FIUBA
2.3. Problema de distribución o transporte
Se tiene un grafo bipartito, donde tenemos O orígenes y D destinos. Cada origen tiene un
suministro que se puede mover a través de las aristas, que deben satisfacer una demanda de cada
destino.
2.3.1. IMPORTANTE
En el caso de que las capacidades sean valores enteros la suma de los suministros y demandas
deben valer lo mismo. De no ser así, se debe agregar un origen/destino ficticio para lograr que la
suma sea igual, los costos asociados a este vértice nuevo deben ser 0.
2.3.2. Objetivo
El objetivo es determinar la cantidad de unidades de producto que cada origen envía a cada
destino, para minimizar los costos de transporte totales en un cierto período de tiempo.
2.3.3. Hipótesis
Producto homogéneo (estamos hablando del mismo producto en orígenes y destinos).
Costos lineales.
Los origenes no tienen preferencia sobre a qué destino enviar productos.
Los destinos aceptan recibir producto de cualquier origen, sin preferencias.
2.3.4. Variables
Se definen variables Xi,j que indican la cantidad de unidades que el origen i envia al centro
j.
2.3.5. Restricciones
Para cada origen, se distribuye toda la oferta en todos los destinos∑
j∈D
Xi,j = ofertai
Para cada destino, se satisface toda la oferta proveniente de los origenes∑
i∈O
Xi,j = demandaj
2.3.6. Funcional
Z :=
∑
i∈O
∑
j∈D
Ci,j ∗Xi,j →MIN
con Ci,j el valor del costo de del transporte de i a j.
6
Problemas de decisión Modelos y Optimización I - FIUBA
2.3.7. Posibles variantes
Problema del transbordo. Destinos intermedios (se envía del origen a los transbordos y
de los transbordos al destino final). Para los origenes, los transbordos son destinos. Para los
destinos, los transbordos son origenes.
Capacidades máximas. Se debe tener en cuenta que habrá una restricción para cada
Xi,j ≤ capacidadi,j
Asignación. Todas las ofertas y demandas son iguales a 1. Por lo tanto, se resuelve como
un problema de variables continuas y de igual manera el resultado es que todas las variables
toman valor entero (cero o uno).
• Asignación cuadrática Los costos son ahora dependientes de pares de asignaciones:
Cij,kl : es el costo por asignar i a j, y k a l. Por lo tanto se definirá la variable Yij,kl que
indica si se hicieron ambas asignaciones (ver restricción lógica and). Se debe modificar
el funcional: ∑
i∈O
∑
j∈D
∑
k∈O
∑
l∈D
Yij,kl ∗ Cij,kl
7
Problemas de decisión Modelos y Optimización I - FIUBA
2.4. Cobertura de conjuntos
Se tiene un conjunto S = {1, 2, 3, 4...n} de elementos a cubrir.
Se tiene un conjunto de subconjuntos de S L = {(1, 2); (2); ...}
2.4.1. Objetivo
Se desea elegir elementos de L tales que (segun el tipo de problema):
1. Cobertura: Se cubran todos los elementos de S con solapamiento (O sea, pueden haber
elementos repetidos).
2. Partición: Se cubran todos los elementos de S sin solapamiento.3. Packing: Se cubra la maxima cantidad de elementos de S que se pueda sin solapamiento.
(Normalmente se plantea cuando el problema de partición no tiene solución factible)
2.4.2. Variables
Para Cobertura y Particion: Se tienen variables bivalentes Yi, que son 1 si se incluye el
subconjunto i ∈ {1, 2..|J |} y 0 sino.
Para packing, se deben agregar variables bivalentes Ve, e ∈ S que indican si se cubre el
elemento e.
2.4.3. Restricciones
Para Cobertura, se plantea para cada elemento e de S que debe estar AL MENOS una vez
(o sea, se debe incluir al menos un subconjunto que incluya a e):
∑
i∈{1,2..|J|}|e∈Si Yi ≥ 1.
Para Particion, se plantea para cada elemento e de S que debe estar EXACTAMENTE una
vez (o sea, se debe incluir al menos un subconjunto que incluya a e):
∑
i∈{1,2..|J|}|e∈Si Yi = 1
Para Packing, se plantea para cada elemento e de S, que se puede incluir a lo sumo un
subconjunto que lo contenga:
∑
i∈{1,2..|J|}|e∈Si Yi = Ve
2.4.4. Funcional
1. Para Cobertura y Partición se plantea minimizar la cantidad de subconjuntos incluídos.
Z :=
|L|∑
i=1
Yi →MIN
2. Para Packing, se plantea maximizar la cantidad de elementos del conjunto original incluídos.
Z :=
∑
e∈S
Ve →MAX
8
Problemas de decisión Modelos y Optimización I - FIUBA
2.5. Secuenciamiento de tareas (Scheduling)
Se tiene un conjunto T de tareas a realizar, donde cada tarea debe pasar de forma ordenada
por una cierta cantidad de procesos.
2.5.1. Objetivo
Se desea determinar el orden de realizar las tareas para que tarde lo menos posible a finalizar
todas las tareas.
2.5.2. Hipótesis
Se puede realizar una única tarea a la vez en cada proceso.
Cada proceso trabaja en una determinada tarea desde que la comienza hasta que la finaliza.
No se pierde tiempo cambiando las tareas que realiza un determinado proceso.
Los tiempos de cada tarea son independientes del órden en que se realizan/trabajan.
2.5.3. Variables
Se definen las variables It,p como el instante de tiempo en el que comienza la tarea t en el
proceso p.
Se definen las variables Ft,p como el instante en el que finaliza la tarea t en el proceso p.
Se define la variable FINAL que tendrá el valor más tardío en el que se finalizó la última
tarea entre todos los procesos.
Se definen variables bivalentes Yanulapij que se anula que la tarea i se realice antes que j
para el proceso p.
2.5.4. Restricciones
Relación entre comienzo y final de una tarea en un proceso:
Ft,p = It,p + tiempot,p
donde tiempot,p es el tiempo que tarda la tarea t en el proceso p.
Las tareas deben atravesar los procesos en orden:
Ft,p ≤ It,p+1,∀p
Para que se pueda realizar una unica tarea a la vez en cada proceso:
Fti,p ≤ Itj,p +M ∗ Yanulapij
Ftj,p ≤ Iti,p +M ∗ Yanulapji
Yanulaij + Yanulaji = 1
Para todo par de tareas i, j, y para cada uno de los procesos p.
Todas las tareas finalizan antes del tiempo final: Ft,p ≤ FINAL.
2.5.5. Funcional
Se plantea minimizar el tiempo en el cual finaliza la última tarea.
Z := FINAL→MIN
9
Problemas de decisión Modelos y Optimización I - FIUBA
2.6. Satisfacibilidad booleana (SAT)
Se tiene un conjunto de cláusulas booleanas compuestas por operaciones logicas entre variables
bivalentes Xi
2.6.1. Objetivo
Determinar si existe una asignación de valores de las variables Xi tal que todas las cláusulas
booleanas son verdaderas.
2.6.2. Variables
Se definen las variables Xi como binarias o bivalentes (1 significa sí, y 0 significa no).
Se define la variable bivalente Y que vale 1 si el problema tiene solución y vale 0 si no la
tiene.
2.6.3. Restricciones
Transformar las cláusulas booleanas a restricciones lineales siguiendo los métodos de la sección
Restricciones lógicas con la variable Y valiendo el or o and entre las variables que formen cada
cláusula.
2.6.4. Funcional
Queremos que Y valga 1 siempre que se pueda (que el problema tenga solución):
Z := Y →MAX
10
Problemas de decisión Modelos y Optimización I - FIUBA
2.7. Problema de la mochila (Knapsack)
Se tiene una mochila con cierta capacidad. Se tiene ademas un conjunto de elementos, donde
cada elemento tiene asociado un espacio que ocupa en la mochila y un valor.
2.7.1. Objetivo
Determinar cuales elementos guardar en la mochila, tal que la suma de los valores de los mismos
sea maxima.
2.7.2. Hipótesis
La cantidad de objetos que se pueden poner en la mochila no está limitada (mientras que
no se supere la capacidad maxima por espacio).
El valor y el espacio del elemento no varian.
2.7.3. Variables
Se definen las variables bivalentes Xi que indican si se guarda el elemento i en la mochila o
no.
2.7.4. Restricciones
El espacio total de los objetos no puede superar a la capacidad máxima de la mochila:∑n
i=1 wi ∗Xi ≤ c.
Donde cada wi indica el espacio que ocupa cada elemento i y c es la capacidad máxima de
la mochila.
2.7.5. Funcional
Z :=
n∑
i=1
vi ∗Xi →MAX
Donde vi representa el valor del elemento i.
2.7.6. Posibles variantes
Multiples elementos. Se tiene una cantidad determinada de elementos de cada tipo, por
lo que el modelo varía en que ahora las variables Xi son enteras (no bivalentes) e indican
cuántos elementos de ese tipo se guardan en la mochila. Estas se deben restringir porXi ≤ bi,
donde cada bi indica cuál es la disponibilidad del elemento i.
No acotado. Se puede utilizar la cantidad de veces que se quiera cada elemento, esto lleva
al caso igual al de Multiples elementos pero sin restringir las variables Xi.
Suma de subconjuntos. En esta variante, el valor de cada elemento es igual al espacio
que ocupa en la mochila.
Problema del cambio. Es un caso particular en el cual se exige cumplir exactamente la
restriccion de capacidad (o sea, la suma de los espacios que ocupan los elementos que se
guardan en la mochila debe ser exactamente c. El funcional en este caso resulta
Z :=
∑
i
Xi →MIN
11
Problemas de decisión Modelos y Optimización I - FIUBA
Múltiples mochilas. Se debe multiplicar la cantidad de variables por la cantidad de mo-
chilas disponibles: Xim indica que se agrego el elemento i a la mochila m. Luego para cada
mochila se agrega la restricción sobre su capacidad.
12
Problemas de decisión Modelos y Optimización I - FIUBA
2.8. Coloreo de grafos
Dado un grafo no dirigido G = (V,E), siendo V el conjunto de vertices y E el conjunto de
aristas, un coloreo valido de G se corresponde a una particion de V en k conjuntos independientes
(es decir, no hay dos vértices unidos por una arista dentro del mismo conjunto).
2.8.1. Objetivo
Dado G, encontrar el minimo k tal que G tiene un k-coloreo valido. (Este k se llama número
cromático).
2.8.2. Variables
Se definen las variables bivalentes Xi,j , que valen 1 si el vertice i se colorea con el color j.
Tambien se definen las variables bivalentes Wj , que valen 1 si el color j se usa en al menos
1 vertice.
2.8.3. Restricciones
Cada vértice debe estar coloreado con exactamente un color:
∑n
j=1 Xi,j = 1 ∀i ∈ V
Los dos vértices son ayacentes no pueden terner mismo color: Xi,j + xkj ≤ wj si [i, j] ∈
E ∀j = 1, ..., n
Si un vértice usa el color j, implica que wj debe valer i: Xi,j , wj ∈ {0, 1} ∀i ∈ V ∀j = 1, ..., n
2.8.4. Funcional
Minimizamos la cantidad de colores:
Z :=
n∑
j=1
Wj →MIN
2.8.5. Otras formas de modelarlo
Modelo por conjuntos independientes. Colorear es determinar a qué conjunto indepen-
diente pertenece cada vértice, cada conjunto luego se colorea con un mismo color.
Modelo por conjuntos independientes maximales. Para reducir la cantidad de va-
riables solo se modelan los conjuntos independientes maximales. Se permite que un vértice
pertenezca a más de un conjunto.
2.8.6. Problema de la simetría
Para eliminar la simetría en las soluciones se plantea la siguiente restricción:
n∑
i=1
Xi,j ≥
n∑
i=1
Xi,j+1, ∀j = 1, ..., n− 1
13
Problemas de decisión Modelos y Optimización I - FIUBA
3. Agregados
3.1. Mezcla
Formalmente. La cantidad final producida es igual a la suma de las cantidades utilizadas de
cada componente.
Se tiene que realizar algún tipo de producto conla mezcla de distintos componentes con (a
veces) limitaciones sobre las proporciones de cada uno.
3.1.1. Hipótesis
¿La mezcla se puede realizar utilizando únicamente un componente?
¿La composición particular de la mezcla afecta el resultado o el valor del resultado?
3.1.2. Variables
Ci,j : Cantidad de del componente i utilizadas para producir el producto j.
Pj : Cantidad del producto j a producir.
3.1.3. Restricciones
La suma de los componentes son el producto total:∑
i∈comp
Ci,j = Pj
Si se tiene límite de proporción sobre algún componente i para un producto j:
Pj ∗ propMini,j ≤ Ci,j ≤ propMaxi,j ∗ Pj
14
Problemas de decisión Modelos y Optimización I - FIUBA
3.2. Armado
Formalmente. Es posible discriminar en el producto final los elementos que lo componenen.
Los productos finales están compuestos por cantidades conocidas de productos intermedios o
materias primas.
3.2.1. Hipótesis
¿Se puede armar un determinado producto sin algún componente?
La cantidad de cada componente utilizada es proporcional a la cantidad de productos finales
armados.
3.2.2. Variables
Ci,j : Cantidad de unidades del componente i dedicadas a armar productos j.
Pj : Cantidad de unidades del producto j a armar.
3.2.3. Restricciones
Ci,j = cantidadi,j ∗ Pj , ∀i ∈ componentes, j ∈ productos∑
j Ci,j ≤ disponibilidadi, ∀i ∈ componentes
15
Problemas de decisión Modelos y Optimización I - FIUBA
3.3. Multiperíodo
Se pueden identificar múltiples períodos entre los cuales varía algún dato (ya sean demandas,
costos, etc.) y se puede almacenar stock entre dichos períodos.
3.3.1. Hipótesis
Se puede almacenar stock de ...
¿Existe stock inicial (SI)?
¿Se debe dejar stock final el último período (SFNperiodos)?
Los productos que se tengan en stock son indistinguibles de los nuevos productos.
¿Los productos se pueden mantener en stock tanto tiempo como se quiera sin alterar su
validez?
3.3.2. Variables
Pi Cantidad de unidades del producto a producir en el mes i.
Vi Cantidad de unidades del producto a vender en el mes i
SFi Stock de unidades al final del mes i.
3.3.3. Restricciones
Relación de vínculo entre los períodos (balance de unidades):
P0 + SI = V0 + SF0
Pi + SFi−1 = Vi + SFi ∀i = 1, ..., Nperiodos
16
Problemas de decisión Modelos y Optimización I - FIUBA
3.4. Esquema modular
Se debe realizar una apertura de variables para vincular las “entradas” y “salidas” de cada par
de módulos relacionados.
3.4.1. Hipótesis
Si no hay defectos, los valores de la entrada y salida de cada módulo son iguales.
3.4.2. Variables
Ei: variables de entradad de un módulo.
Si: variables de salida de un módulo.
3.4.3. Restricciones
1. Si no hay desperdicios: ∑
i
Ei =
∑
i
Si
2. En el caso que el desperdicio no se utilice:∑
i
Ei = (1− propDesperdicio)
∑
i
Si
3. En el caso de que el desperdicio "loopee"sobre el módulo:∑
i
Ei =
∑
i
Si
17
Problemas de decisión Modelos y Optimización I - FIUBA
3.5. Programación de metas
Se tiene una variable C, y se quiere utilizar la diferencia del valor de dicha variable respecto
de un valor umbral constante umbralC, distinguiendo si la diferencia es positiva o negativa.
3.5.1. Hipótesis
Si hay interés, este puede ser pagado:
• Por adelantado: Se debe incluir en la ecuación de balance para el período de trabajo.
• Vencidos: NO se deben incluir en la ecuación de balance
3.5.2. Variables
C: La variable respecto de la cual se quiere hacer la programacion de metas.
ExcesoC: Exceso de la variable respecto del umbral.
DefectoC: Defecto de la variable respecto del umbral.
3.5.3. Restricciones
C − umbralC = ExcesoC −DefectoC
Normalmente C se abrirá como:
C = inicialC + ingresoC − egresoC
18
Problemas de decisión Modelos y Optimización I - FIUBA
3.6. Restricciones lógicas
Variables Yi bivalentes.
3.6.1. “Si entonces”
Si Y1 entonces Y2 (equivalente: si no Y2 entonces no Y1):
Y1 ≤ Y2
Si Y1 entonces X ≤MAX (sino libre):
X ≤MAX ∗ Y1 +M ∗ (1− Y1)
Si Y1 entonces X ≥ min (sino libre):
X ≥ min ∗ Y1 −M ∗ (1− Y1)
3.6.2. AND
YAND = AND
n
i=1Yi
n ∗ YAND ≤
n∑
i=1
Yi ≤ (n− 1) + YAND
3.6.3. OR
YOR = OR
n
i=1Yi
YOR ≤
n∑
i=1
Yi ≤ n ∗ YOR
19
Problemas de decisión Modelos y Optimización I - FIUBA
3.7. Costos variables por intervalo
Se da cuando el valor asociado a una variable incrementa igualmente para la cantidad total
total de la misma.
3.7.1. Variables
Se tiene la variable X puede estar en distintos rangos [0, v1], (v1, v2], .. ,(vn−1, vn]. Se agregara
una variable YXi para determinar que rango este la variable X.
3.7.2. Restricciones
X =
n∑
i=1
Xi
X1 ≤ v1 ∗ YX1
(v1 +m) ∗ YX2 ≤ X2 ≤ v2 ∗ YX2
...
(vi−1 +m) ∗ YXi ≤ Xi ≤ vi ∗ YXi
...
(vn−1 +m) ∗ YXn ≤ Xn ≤ vn ∗ YXn
n∑
i=1
YXi = 1
20
Problemas de decisión Modelos y Optimización I - FIUBA
3.8. Curva cóncava seccionalmente lineal
Se da cuando el valor asociado a una variable incrementa para cada intervalo de la cantidad
que haya de la misma.
3.8.1. Variables
Se tiene la variable A que puede tener un valor determinado según los intervalos dados por:
[0, v1], (v1, v2], .. ,(vn−1, vn]. Se agregará entonces una apertura de la variable A para cada valor
posible: Ai La cantidad de A en el intervalo i. (cada una de estas puede valer: mini ≤ Ai ≤MAXi)
Y variables indicadoras para verificar que hay cantidades de A que completan hasta cada intervalo:
Yi La variable Ai−1 alcanzó su valor máximo. (para el caso inicial es si hay alguna cantidad de A)
3.8.2. Restricciones
A =
n∑
i=1
Ai
v1 ∗ Y1 ≤ A1 ≤ v1
(v2 − v1) ∗ Y2 ≤ A2 ≤ (v2 − v1) ∗ Y1
...
(vi − vi−1) ∗ Yi ≤ Xi ≤ (vi − vi−1) ∗ Yi−1
...
An ≤M ∗ Yn−1
21
	Hipótesis generales
	Problemas Tipo
	Producción
	Problema del viajante (TSP)
	Problema de distribución o transporte
	Cobertura de conjuntos
	Secuenciamiento de tareas (Scheduling)
	Satisfacibilidad booleana (SAT)
	Problema de la mochila (Knapsack)
	Coloreo de grafos
	Agregados
	Mezcla
	Armado
	Multiperíodo
	Esquema modular
	Programación de metas
	Restricciones lógicas
	Costos variables por intervalo
	Curva cóncava seccionalmente lineal