Merge respuestas Finales docx

Vista previa del material en texto

En términos de complejidad ¿cuándo se dice que un problema es difícil? Mencione
un ejemplo
A la vez es un problema complejo, si por complejidad nos referimos a la computacional. Un
problema se cataloga como inherentemente difícil si su solución requiere de una cantidad
significativa de recursos computacionales, sin importar el algoritmo utilizado . El problema
de la mochila forma parte de una lista histórica de problemas NP Completos elaborada por
Richard Karp en 1972 2 . En el caso del problema de la mochila, si contáramos con 4
productos, para saber cuál es la mejor solución podríamos probar las 24=16 posibilidades.
El 2 se desprende del hecho de que cada decisión es incluir o no al producto y el 4 de la
cantidad de productos. 16 posibilidades es un número manejable, sin embargo, si la
cantidad de elementos por ejemplo ascendiera a 20, tendríamos que analizar nada más y
nada menos que 220=1048576 posibilidades
Si el problema de distribución se puede resolver de manera exacta como un problema
de programación lineal continua ¿por qué se utilizan heurísticas de construcción para
ese problema?
Porque en la mayoría de los casos no se puede transportar partes fraccionarias de
productos, es decir, el uso más conocido es para variables enteras. Por este motivo se
utilizan heurísticas, ya que su resolución en programación lineal entera es un problema
difícil. Muchas veces se requiere una solución aproximada, que se acerque lo suficiente a la
exacta, pero sin perder demasiado tiempo en procesamiento.
¿Es el problema de Asignación un problema difícil? ¿Por qué?.
El problema de Asignación ¿es un problema difícil? ¿se puede resolver de manera
exacta aplicando el método Simplex, sin tener que aplicar Branch & Bound u otro
método para que las variables tengan valor entero?
Asignación es un problema difícil, porque es un problema combinatorio donde el software
tiene que evaluar cada posibilidad antes de dar con un resultado. En el caso de haber
muchas combinaciones esto puede ser muy costoso. Sin embargo, su relajación lineal se
resuelve en tiempo polinomial y da una solución entera. Recordar que el problema de
asignación es un problema de distribución o transporte con orígenes y destinos de 1.
De los dos planteos de modelización más conocidos para el viajante (plantear todas
las restricciones que evitan subtours, también llamado MZT y el que agrega las
restricciones de Ui) ¿cuál es el mejor en términos de resolución del problema? ¿por
qué piensa que ese es el mejor?
El número exponencial de restricciones hace impráctico resolverlo directamente por el
método de Ui. Una opción es agregar únicamente las restricciones para evitar subtours en
los casos en los cuales arma subtour y no en todos los casos. Este último es mejor cuando
el problema del viajante tiene muchas ciudades, es decir, muchas ecuaciones del problema
en sí. En cambio el método de las Ui es muy práctico cuando hay pocas ciudades ya que no
aumenta considerablemente el número de ecuaciones y resulta más práctico la resolución.
** Si bien la formulación de subtours tiene demasiadas restricciones (si queremos evitar
TODOS los subtours) y por eso se agregan únicamente las restricciones de los subtours
que se hayan formado (luego de resolverlo sin esas restricciones), la formulación con UI
(también llamado modelo MZT del viajante) tiene un poliedro que incluye al de la
formulación por subtours, por eso está más alejado de la cápsula convexa entera y desde el
punto de vista de resolución es mejor el de subtours.
Para resolver un problema de Programación Lineal Entera, uno de los procedimientos
que se pueden utilizar es Branch & Bound ¿Cómo se puede acelerar la resolución por
Branch & Bound para que termine antes?
La eficiencia de este método depende fundamentalmente del procedimiento de expansión
de nodos, o de la estimación de los nodos padres e hijos. Es mejor elegir un método de
expansión que provea que no se solapen los subconjuntos para ahorrarnos problemas de
duplicación de ramas.
También se pueden agregar restricciones redundantes del modelo original para acelerar el
proceso y que el método de Branch & Bound elimine de la evaluación ramas redundantes
que no llegarán a ningún resultado.
El problema de conjuntos a cubrir ¿es un problema difícil?. Definir brevemente el
problema e indicar por qué es un problema difícil o por qué no lo es.
Es un problema NP Completo (está en la lista de los 21 problemas NP Completos de Karp).
Dado un conjunto de elementos (llamado universo ) y conjuntos cuya unión
comprende el universo, el set cover problem consiste en identificar el menor número de
conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea
y los conjuntos .
Claramente, la unión de todos los conjuntos de contiene todos los elementos de . Sin
embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con
menor número de elementos:
¿Es el problema de Distribución o Transporte un problema difícil? ¿Por qué?.
Si en un problema de coloreo de grafos coloreáramos cada nodo con un color
diferente la solución es muy fácil de obtener. Entonces, ¿por qué el problema de
coloreo de grafos es un problema
difícil?
Porque el problema de coloreo de grafos busca colorear al grafo con la mínima cantidad de
colores. Si vamos pintando cada nodo de un color teniendo en cuenta de que no haya
adyacentes con el mismo color, estaríamos utilizando una heurística, la cual no
necesariamente
nos puede llevar al mínimo de colores. Esto termina siendo un problema difícil pues
dependiendo del grafo puede haber varias combinaciones posibles y no hay forma de
obtener
este mínimo de colores con algún método de programación lineal.
¿Para qué utiliza el método Branch and Bound la mejor solución entera encontrada
hasta el momento?
Para resolver un problema de Programación Lineal Entera, uno de los
procedimientos que se pueden utilizar es Branch & Bound
El metodo B&B empieza resolviendo el problema como si las variables fueran continuas.
Luego verifica si dieron valor entero las variables que tenían que dar enteras (en este caso
vemos que no) y toma la primera variable que debería ser entera y no lo es (en
este caso X1) para aplicarle el paso de “branching”.
El resultado de la solución encontrada por plc ya que la real debera estar mas o menos
cerca de la solucion encontrada
La solución que encontrás debe ser válida (es decir, las variables que requieren ser enteras,
deben serlo). Genéricamente, lo que se hace es utilizar cotas
¿Cómo se puede acelerar la resolución por Branch & Bound para que termine antes?
Se la utiliza como cota inferior como condición de corte para otros branches que quedan por
explorar. Por ejemplo si encontramos un Z óptimo entero que es 4 y nos queda algún
branch
por explorar, si este tiene un Z menor al mejor encontrado hasta el momento y la restricción
del branch de la variable correspondiente hace que el funcional disminuya, es imposible que
de mejor que el que ya encontramos, por ende ese branch se corta. En caso de poder
mejorar o si ya en sí el Z es mayor al mejor encontrado, seguimos explorando.
Si en el problema de la mochila se permitiera colocar fracciones de objetos en lugar
de exigir que los objetos se coloquen enteros ¿sería el problema igualmente difícil?
¿por qué?
El problema es difícil porque la solución continua no me sirve para determinar qué objetos
deben entrar o no, en especial con el objeto crítico (el primero que no entra y convendría
que
entrara). Si el problema fuera continuo la complejidad sería mucho menor, porque la
solución continua me sirve (sirve que entre una fracción de un objeto)
¿Cuándo se considera que un problema es “difícil”?. Justifique en base a lo visto en
las clases teórico prácticas acerca de complejidad.
A la vez es un problema complejo, si por complejidad nos referimos a la computacional. Un
problema se cataloga como inherentemente difícil si su solución requiere de una cantidad
significativa de recursos computacionales, sin importar el algoritmo utilizadoPara resolver un modelo de Programación Lineal Entera ¿podemos usar el método
simplex? ¿qué diferencias hay entre resolver un modelo de Programación Lineal
Entera y un modelo de Programación Lineal Continua?
El método simplex no sirve para resolver problemas de programación lineal entera, solo
sirve para continua. Se pueden utilizar métodos los cuales utilizan dentro de si al método de
simplex, como es el Branch & Bound, que resuelve un problema con restricciones
agregadas enteras varias veces hasta obtener una solución óptima entera.
La principal diferencia es el tipo de variable.
Otra respuesta
No ya que en el metodo simplex voy recorriendo el poliedro de soluciones moviendome
por las restricciones, en el caso de tener una solucion entera que no pertenezca a los
vertices del poliedro, no podre hallar la solucion.
La diferencia seria que en el problema de plc se que la solucion se encuentra en alguno
(uno o mas) de los vertices del poliedro de soluciones en caso de existir y en los
problemas de PLE no tengo esa certeza
Estamos resolviendo un problema de Programación Lineal Entera y no sabemos si es
fácil o difícil. Indique cómo encararía el problema aprovechando los diferentes temas
vistos en la materia
Resolveria por simplex y despues haria branch and bound??
Primero hay que modelizar el problema en papel, clasificando las variables en continuas,
enteras y binarias (subconjunto de enteras). El segundo paso es pasar el modelo a Simplex
por ejemplo que es un método de resolución de PLC. Si en PLC el problema da entero,
quiere decir que acabamos de resolver la relajación lineal del problema y nos dio entero. Si
no da entero, se aplica el método branch and bound o cualquier otro que lo que hacen es
buscar la cápsula convexa entera del problema contínuo, hasta dar con una solución. Hallar
la cápsula convexa puede tomar mucho tiempo y si así pasa, se puede optar por utilizar una
heurística para encontrar una solución aproximada del problema en vez de la solución
exacta óptima.
Si existen procedimientos como Branch and Bound, Branch and Cut y otros, que
resuelven de manera exacta un problema de programación lineal entera ¿por qué
algunos problemas se resuelven de manera aproximada con un algoritmo heurístico?
Esto se debe a que en muchos casos, los problemas de programación lineal entera, utilizan
igualdades, entonces se requieren de muchas iteraciones para poder conseguir una
solución óptima. Además en los métodos descritos anteriormente, se debe pasar por varias
resoluciones(tablas de simplex) para poder lograr la solución exacta.
Además, la cantidad de ramas a recorrer es demasiado extensa y llevaria demasiado
tiempo
El problema de la mochila ¿es un problema difícil?. Definir brevemente el problema e
indicar por qué es un problema difícil o por qué no lo es.
A la vez es un problema complejo, si por complejidad nos referimos a la computacional. Un
problema se cataloga como inherentemente difícil si su solución requiere de una cantidad
significativa de recursos computacionales, sin importar el algoritmo utilizado . El problema
de la mochila forma parte de una lista histórica de problemas NP Completos elaborada por
Richard Karp en 1972 2 . En el caso del problema de la mochila, si contáramos con 4
productos, para saber cuál es la mejor solución podríamos probar las 24=16 posibilidades.
El 2 se desprende del hecho de que cada decisión es incluir o no al producto y el 4 de la
cantidad de productos. 16 posibilidades es un número manejable, sin embargo, si la
cantidad de elementos por ejemplo ascendiera a 20, tendríamos que analizar nada más y
nada menos que 220=1048576 posibilidades.
Otra respuesta encontrada:
El problema de la mochila consiste de elegir una cantidad de elementos que tienen una
capacidad y un beneficio. La mochila tiene una capacidad máxima que pone límite a los
elementos a cargar. El problema consiste determinar qué objetos ingresar en la mochila con
el objetivo de maximizar el beneficio que otorgan los elementos. Es un problema
NP Completo debido a que para obtener la solución óptima es necesario analizar todas las
combinaciones de elementos. Este problema es de programación lineal entera, su relajación
lineal carece de sentido ya que uno cargaría la mochila con todos los elementos enteros
posibles y el elemento crítico, que es el que entra sólo una fracción, se ingresa esa fracción
y listo.
Los problemas que están en NP ¿son siempre más difíciles que los que están en P?.
Responder en términos de complejidad
Primero que nada, P está incluido en NP, así que algunos problemas que están en P
también están en NP. Los problemas que están en NP y no en P (por el momento se cree
que es así) son problemas de orden de complejidad exponencial, es decir, la naturaleza
(usualmente combinatoria) del problema hace que al agregar un elemento, la cantidad de
entradas o restricciones del problema crezca exponencialmente.
Dentro de los problemas de cobertura de conjuntos hay tres tipos de problema:
conjuntos a cubrir, partición de conjuntos y packing. Los problemas de packing
siempre tienen solución factible, en cambio los problemas de conjuntos a cubrir y de
partición pueden dar incompatible ¿por qué?.
El problema de packing es buscar cubrir elementos tratando de maximizar la cantidad de
elementos sin importar si están cubiertos por más de un conjunto y este problema siempre
tiene solución compatible. En cambio el problema de conjuntos a cubrir tiene que cumplirse
que si o si se cubran todos los elementos. Este problema se realiza incompatible si existe
un
elemento que no pertenece a ningún conjunto, entonces será imposible cubrir todos los
elementos con conjuntos, porque no existe ningún conjunto que contenga al elemento. El
problema de partición es inclusive más restrictivo que la cobertura de conjuntos, porque no
sólo pide que deben estar cubiertos todos los elementos, sino que además exige que los
elementos deben ser cubiertos únicamente por un conjunto. Por ejemplo si tengo:
c1 = {A, B} c2 = {B, C} , en cobertura es un sistema compatible y la respuesta es c1 y c2, en
cambio en partición es incompatible porque para cubrir A, B y C tengo que incluir c1 y c2,
pero B se solapa en la solución.
Además del método simplex, hay varios métodos para resolver problemas de
programación lineal continua. Uno de ellos es el método del elipsoide, que no se
aplica en la práctica pero tiene un gran valor teórico ¿por qué tiene un gran valor
teórico?
El valor que tiene el método del elipsoide es que demuestra que el problema de la
programación lineal continua es un problema de orden polinomial (orden n^100, horrible,
pero sigue siendo polinomial). Por lo tanto, se demuestra que PLC pertenece al conjunto de
problemas en P.
Otra respuesta:
Aunque este algoritmo actualmente se considera poco práctico, por el alto grado
polinómico de su complejidad computacional , significó un descubrimiento sumamente
importante en el área, y un punto de partida para el desarrollo de algoritmos más
sofisticados y eficientes. Tiene un gran valor teórico dado que demostró que la
programación lineal es un problema que está en P.
En la prueba de heurísticas se suelen utilizar ejemplos de problemas extraídos de
bibliotecas de problemas, en muchos casos ya resueltos exactamente. Un ejemplo es
el de las bibliotecas TSPLIB en el caso de los problemas del viajante ¿qué ventajas
tiene probar con esos casos en lugar de hacerlo con ejemplos elaborados por el autor
de la heurística?
La ventaja que tiene es que uno puede construir una heurística que funciona muy bien para
un caso particular, pero no funciona bien en muchas otras instancias del problema. Por eso
es que se utilizan bibliotecas de instancias, para que uno pueda probar una heurística
contra diversas instancias y no una única. (El clásico problema de overfitting).
Puede ser que la heurística funcione bien con un ejemplo elaborado por el autor pero luego
no generalice bien para cualquier otro ejemplo. Utilizando ejemplos de la biblioteca se
puede tener una mejoridea de la efectividad de la heurística, y también permite comparar
los resultados con los de otras heurísticas para así poder determinar aún mejor qué tan
buena es la heurística a probar.
Si tenemos dos ejemplos de dos problemas diferentes ¿cómo podríamos determinar
si alguno de los dos es un problema difícil y si uno es más difícil que el otro? ¿qué
definición utilizarías para decir que un problema es difícil?
Para definir si un problema es más difícil que otro se puede utilizar el teorema de la
reducción. Supongamos que tenemos dos problemas distintos, uno en NP y otro en P. Si
uno está en P, quiere decir que se conoce un algoritmo que resuelve el problema en tiempo
polinomial. Si de alguna forma se consigue modelar el problema de NP como un problema
de P, quiere decir que lo hemos reducido, es decir, hemos expresado el problema de NP
como un problema de P, entonces se dice que el problema de NP no es “difícil” y también
pertenece a P. Si tenemos dos problemas, P1 y P2 ambos de complejidad NP, y logramos
reducir el problema P1 y convertirlo en P2 EN TIEMPO POLINOMIAL, se dice que P2 no es
más fácil que P1.
Supongamos que tenemos un problema de coloreo de grafos con 5 nodos. Al
resolverlo de manera exacta obtenemos que podemos usar un mínimo de 3 colores
para colorearlo. Sin embargo, se obtienen varias soluciones alternativas (una con los
colores 1, 2 y 3; otra con los colores 2, 3 y 4, etc.). ¿Qué condiciones agregaríamos al
modelo para evitar esas soluciones alternativas?
En la resolución heurística del problema de la mochila, ¿para qué se usan las cotas?.
Se utilizan cotas para medir que tan buena es nuestra heurística. Si sabemos que el óptimo
es X y nuestra heurística nos está dando un resultado de X^4, se sospecha que la heurística
no es para nada buena.
C1 Respecto a complejidad ¿Puede un problema estar en P y en NP
simultáneamente?
¿Por qué sí o por qué no?
Hay dos hipótesis: P = NP y P =/= NP. En el primer caso evidentemente, un problema que
está en P está en NP ya que son el mismo conjunto. En el segundo caso un problema en P
también está al mismo tiempo en NP, ya que el hecho de que un problema esté en P
significa que se puede resolver en un tiempo polinomial y el hecho de que un problema esté
en NP significa que se puede resolver en un tiempo no polinomial, sino más bien
exponencial, lo cual consiste en una cota superior que abarca a los polinomios. Entonces,
un problema que esté en P va a estar siempre en NP sea cual sea la hipótesis.
¿Cómo influye en la resolución de problemas que no se pueda determinar si P es
distinto o igual que NP (en términos de complejidad de problemas)?
El problema es que existen muchos problemas en NP de los cuales no se conoce si existe
un mejor algoritmo que solucione el problema en tiempo polinomial. Es decir, no hay certeza
si los problemas se pueden resolver en tiempo polinomial y por ello es que existe un premio
de 1 millón de dólares para la persona que demuestre que si P = NP o P != NP.
1) Si se encuentra un algoritmo que resuelve, digamos, el problema del viajante en tiempo
polinomial, esto demuestra que P = NP, porque lo único que habría que hacer es reducir
otros problemas de NP a un viajante y resolverlos en tiempo polinomial.
2) Si se demuestra que no existe ningún algoritmo que resuelva algún problema en NP en
tiempo polinomial, habría certeza de que es imposible encontrar una solución en tiempo
polinomial y se sabría que la solución exacta es difícil de hallar o que la utilización de
heurísticas es útil.
En el problema de coloreo de grafos, si se resuelve suponiendo que las variables
pueden tomar valores no enteros (es decir, se lo resuelve como un problema
continuo) ¿se puede usar esa solución como base para resolver el problema en el
cual las variables son enteras? Indique las limitaciones de la solución continua (si las
tiene).
No, no tiene ningún sentido la solución obtenida. Tendría algún sentido si la solución dijera
que algunos nodos hay que pintarlos de un color específico, pero el problema es que la
solución indicará que a los nodos hay que pintarlos un 20% con un color, un 30% con otro
color y un 50% con un tercer color. La solución continua no tiene ningún sentido en el
problema real.
¿En que afecta a la resolución de modelos de programación lineal entera que no se
haya podido probar aún si P = NP?
La categoría P está compuesta por los problemas para los cuales existe un algoritmo (un
programa) con el cual una computadora en un tiempo “razonable” lo puede resolver.
La categoría NP consiste de los problemas en donde una computadora puede decidir en
tiempo “razonable” si una solución es la correcta o no.
Si P fuera igual a NP, eso querría decir que todos los problemas de esta última clase tienen
escondido una suerte de “atajo” que les permitiría a las computadoras llegar por el camino
más corto a encontrar la solución perfecta en un tiempo polinomial.
La mayoría de problemas de PLE, son NP, con lo cual además de que no podemos utilizar
simplex para ellos, podríamos encontrar una solución exacta, en tiempo polinomial.
Si en el problema de la mochila se permite colocar fracciones de objetos en lugar de
exigir que los objetos se coloquen enteros¿sería el problema igual de difícil? ¿por
que?
Al pasar el problema de la mochila de variables enteras a continuas, es decir que
tendriamos objetos que se pueden fraccionar, el problema dejaria de ser “dificil”. La solucion
seria tan sencilla como ordenar los objetos por beneficio y guardar lo objetos de mayor a
menor, donde cuando no entre un objeto entero, simplemente se guarda una fraccion de el.
La complejidad del problema de la mochila recae en tener que evaluar distintas
combinatorias de distintos objetos (enteros).
Si en un problema de coloreo de grafos se colorea cada nodo con un color diferente,
la solución es muy fácil de obtener. Entonces ¿Por qué el problema de coloreo de
grafos es un problema difícil?
El objetivo del problema de coloreo es MINIMIZAR la cantidad de colores a utilizar. Si se
colorea un nodo de cada color, es una solucion factible, pero se toma como una cota, o
solucion inicial para poder aproximar a la siguiente solucion mas cercana a la exacta.
Si el problema de distribución se puede resolver de manera exacta como un
problema de programación lineal continua ¿por qué se utilizan heurísticas de
construcción para ese problema?
Rta (Chequear respuesta):
La idea de usar heurísticas en el problema de distribución es llegar de manera simple a una
primera solución válida (en algunos casos, como la segunda y la tercera heurística que
veremos, se trata de que esa solución sea también una buena solución) Como todas las
restricciones del problema son igualdades, si lo resolvemos por el método simplex tenemos
que agregar una variable artificial por cada una, con lo que tendrían que pasar varias hasta
que encontremos una solución válida. En problemas de tamaño mayor es peor. Así que se
usa una modificación del método partiendo de una primera solución válida
¿Cómo definirías que un problema de programación lineal es un problema difícil?
Un problema se cataloga como inherentemente dificil si su solucion requiere de una
cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado.
Si tenemos dos ejemplos de dos problemas diferentes ¿cómo podríamos determinar
si alguno de los dos es un problema difícil y si uno es más difícil que el otro? ¿qué
definición utilizarías para decir que un problema es difícil?
Para determinar si un problemas es más difícil que otro podríamos aplicar reducción, de
esta forma si es posible convertir un problema A en otro problema B entonces B no es más
fácil que A sino que estarían los dos en el mismo nivel de dificultad. Si no es posible
transformar uno en el otro entonces uno es mas difícil.
Para decir que un problema es difícil conviene analizar su complejidad computacional. Un
problema es difícil cuando su solución requiere de una cantidad significativa de recursos
computacionales sin importar el algoritmo usado.● ¿Cuándo un problema está en P? ¿Cuándo un problema está en NP? Mencione
ejemplos de problemas en P y en NP.
De las heurísticas que conoce para el problema del viajante ¿cuál le parece que da
mejores resultados y por qué?.
Hay 4 grupos de heuristicas de contriccion para el probelama del viajante: Heuristicas que
van formando el tour (Nearest Neighbor); Heuristicas que generan multiples fragmentos
(Multiple Fragment); Heuristicas que cierran el tour en cada paso (Nearest Addition); y
Heuristicas basadas en arboles.
Nearest Neighbor Tiene el probalema de que al tomar siempre desiciones basadas en la
localidad y no al problema en su conjunto, con lo cual, en los ultimos casos se ve forzado a
tener que tomar malas desiciones que empeoran el resultado.
¿Por qué el algoritmo simplex se ha mantenido vigente tanto tiempo a pesar de
que no obtiene de una manera rápida la solución óptima de los modelos de
programación lineal continua?
El método simplex no es un algoritmo que en el peor de los casos termine en un tiempo
polinomial (porque recorrería todos los vértices). Sin embargo, la probabilidad de que en un
problema real se de el peor caso es bajísima, así que en la práctica funciona muy bien.
¿Qué diferentes criterios se pueden usar para clasificar una
formulación como "buena"?, ¿cuál fue el criterio adoptado en clase
(teórico-prácticas)?: según el criterio adoptado en clase, ¿qué características tiene
una formulación de programación lineal continua para ser buena?, ¿qué
características tiene una
formulación de programación lineal entera para ser buena?
Los criterios son:
• Un buen modelo de PLC tiene pocas restricciones y variables.
• Un buen modelo de PLE tiene un poliedro cercano a la cápsula convexa.
En tu opinión, el problema de la mochila que vimos en clase
¿es fácil o difícil? ¿por qué considerás que es así?. Si se
permitiera fraccionar los ítems para ponerlos en la mochila (es
decir, que no sea necesario poner un ítem entero sino que se
pueda poner parte del ítem), ¿cambiaría la complejidad del
problema? ¿por qué?
Sí, el problema es difícil porque no se conoce un algoritmo
que en tiempo polinomial pueda resolverlo, cuando los ítems tienen que entrar en
cantidades enteras. Si pudieran entrar en cantidades continuas es trivial, mete enteros
los de mejor relación beneficio/peso y cuando no le alcanza para meter uno entero, mete
una fracción de ese producto que no entra entero.
¿Cómo encaramos un problema si no sabemos si es facil o dificil?
En primer lugar, si no tiene variables enteras no es un problema difícil.
Si tiene variables enteras hay que empezar por caracterizar y tratar de ver si es semejante
a alguno de los problemas combinatorios conocidos (viajante, mochila, cobertura de
conjuntos, etc.). Si se puede plantear como uno de esos problemas, es difícil.
Sino, hay que resolverlo con algún algoritmo de resolución de problemas enteros y si
tarda demasiado tiempo y no finaliza, con una heurística
Para resolver un modelo de Programación Lineal Entera ¿podemos usar el
método simplex? ¿qué diferencias hay entre resolver un modelo de Programación
Lineal Entera y un modelo de Programación Lineal Continua?
El método Simplex se utiliza para resolver problemas de Programación Lineal Contínua
por lo tanto no te garantiza que la solución óptima encontrada sea entera.
Te puede llegar a servir para encontrar el óptimo si el óptimo del problema contínuo y el
del entero coinciden, sea por casualidad o porque las características del problema lo
garantizan, como ocurre en el Problema de Distribución.
En otros casos, lo podés llegar a usar como parte de un método de resolución que
necesite obtener soluciones parciales (por ejemplo, Branch and Bound).
El problema de conjuntos a cubrir ¿es un problema difícil?
Definir brevemente el problema e indicar porque es un
problema difícil o porque no lo es.
Es un problema difícil ya que si la cantidad de elementos del conjunto es grande, las
combinaciones posibles de subconjuntos son muchas. Como lo dice el nombre se trata de
un problema donde tengo elementos en uno más conjuntos, y se desea seleccionar los
subconjuntos de manera de cubrir todos los elementos con solapamiento o la mayor
cantidad posible sin solapamientos.
De los 2 planteos de modelización más conocidos para el viajante (plantear todas
las restricciones que evitan subtours, también llamado MZT y el que agrega las
restricciones de Ui) ¿Cuál es el mejor en términos de resolución del problema?
¿Por qué piensa que ese es el mejor?
El planteo mediante las restricciones de Ui es mejor ya que con una sola restricción evito
los subtours, en cambio con MZT, tengo que establecer una restricción para cada subtour
posible. Para casos donde la cantidad de nodos es grande, necesito un número muy
grande de restricciones lo que complica el armado del modelo.
En las preguntas 2 y 3 te aclaro que el planteo con las Ui tiene muchas menos
restricciones en problemas grandes (como bien decís) pero desde el punto de vista de
resolución (en lo referente a teoría de complejidad de algoritmos) el planteo MZT da una
cápsula convexa que está más cerca de la cápsula convexa entera del problema que el
planteo con las Ui. Es decir, según el criterio de planteo con menos restricciones es mejor
el de las Ui, pero según el criterio de resolución es mejor el MZT
En las clases teórico prácticas se vieron dos maneras de hacer el modelo para el
problema del viajante: una usando variables Ui y la otra armando las restricciones
(combinando las Yij) que evitan todos los posibles subtours. ¿Según qué criterio el
modelo de las Ui es el mejor de los dos y según qué criterio el modelo de evitar
subtours es el mejor de los dos?
El armado de las restricciones combinando las Yij para evitar los subtours puede ser un
mejor cuando se puede observar a simple vista cual o cuales son los subtours que se
podrían formar y la cantidad de restricciones a escribir es pequeña. En cambio usando las
variables Ui, se puede utilizar para un número más grande de problemas del viajante
usando solo una restricción.
El planteo MZT da una cápsula convexa que está más cerca de la cápsula convexa entera
del problema que el planteo con las Ui. Es decir, según el criterio de planteo con menos
restricciones es mejor el de las Ui, pero según el criterio de resolución es mejor el MZT
El problema de asignación ¿es un problema difícil?
No, no es un problema dificil ya que puedo resolverlo utilizando programacion lineal
continua y la solución obtenida sera factible? ( siempre que sea el caso de asignacion
clasica y no el de asignacion cuadratica ).
En el problema de coloreo de grafos, si se resuelve suponiendo que las
variables pueden tomar valores no enteros (es decir, se lo resuelve como un
problema continuo) ¿se puede usar esa solución como base para resolver el
problema en el cual las variables son enteras? Indique las limitaciones de la
solución continua (si las tiene).
No ya que la solucion podria incluir pintar un pais la mitad de un color y la mitad de otro, y
algun pais limitrofe estar pintado de los mismos 2 colores, dando asi una solucion
inconsistente en terminos de lo que queremos calcular, pero sera factible para el modelo ya
que la sumatoria de ambos colores sera igual a 1 pero no se cumplira que un pais este
pintado de un solo color y que Xij + Xkj <= wj
Xij = 1 el vértice i se colorea con color j
wj si se utiliza el color j
¿En qué afecta a la resolución de modelos de programación lineal entera
que no se haya podido probar aún si P es igual o distinto que NP?
Afecta en el hecho de generar incertidumbre acerca de si existe algun algoritmo que
resuelva dicho problema en tiempo polinomial, lo que tal vez podria obligarnos a utilizar un
Heuristica que no nos garantiza que la solucion sea optima.
Nos afecta en que tenemos incertidumbre acerca de si podemos encontrar algún
algoritmo capaz de resolverlo en tiempo polinomial o no
Si el problema de distribución se puede resolver de manera exacta como
un problema de programación lineal continua ¿porqué se utilizan heurísticas
de construcción para ese problema?
Porque, como vimos, todas las restricciones del problema son
igualdades, y si lo resolvemos por el método simplex tenemos que
agregar una variable artificial por cada una, con lo que tendrían que
pasar varias tablas hasta que encontremos una solución válida. En
problemas de tamaño mayor es peor. Así que se usa una
modificación del método partiendo de una primera solución válida
Para resolver un problema de Programación Lineal Entera, uno de los
procedimientos que se pueden utilizar es Branch & Bound ¿Cómo se puede
acelerar la resolución por Branch & Bound para que termine antes?
Para optimizar en el caso de tener soluciones alternativas lo que se puede hacer es
encuentro una solucion y le agrego un % y su una rama no es mayor a la sol+ % no la
analizo para no perder tiempo analizando soluciones similares.
¿Para qué utiliza el método Branch and Bound la mejor solución entera
encontrada hasta el momento?
Esta solución se usa para el paso de cota ("bound"), en el cual se eliminan de la lista de
problemas a explorar todas las ramas que no se han explorado por completo y tengan un
funcional peor que la cota (es decir, que la mencionada solución entera).
Para resolver un modelo de Programación Lineal Entera ¿podemos usar el
método simplex? ¿qué diferencias hay entre resolver un modelo de
Programación Lineal Entera y un modelo de Programación Lineal Continua?
No ya que en el metodo simplex voy recorriendo el poliedro de soluciones moviendome por
las restricciones, en el caso de tener una solucion entera que no pertenezca a los vertices
del poliedro, no podre hallar la solucion.
¿Cómo se define la complejidad de un problema?
Complejidad: se define según la relación entre la cantidad de instrucciones computadas y el
tamaño de la instancia. Una instancia es cada una de las posibles entradas del problema
En el caso del problema del viajante ¿por qué generalmente se resuelve usando
heurísticas?
El problema del viajante es un problema de complejidad NP-HARD, es decir, no se conoce
un algoritmo de tiempo polinomial que pueda resolverlo exactamente. Por esto se utilizan
heurísticas para obtener soluciones aproximadas en tiempo razonables.
¿Qué tipos de planos de corte conoce para aplicar en el algoritmo de Branch and
Cut? ¿Para resolver qué tipos de problemas se usan algoritmos de planos de corte?
Los tipos de algoritmos de plano de corte utilizados pueden ser los específicos para realizar
cortes en ciertos problemas específicos como el viajante, mochila, etc. Y se puede aplicar
un plano de corte de tipo general porque pueden utilizarse para cualquier PLE.
Se utilizan para resolver problemas de Programación Lineal Entera
¿En qué consiste Branch & Cut? ¿qué tipos de problemas se resuelven aplicando
Branch and Cut?
Branch & Cut es un método de optimización combinatoria para resolver problemas de
programación lineal entera, donde alguna o todas las incógnitas son enteras. Branch and
Cut es un híbrido entre el método Branch and Bound y algoritmos de planos de corte.
Mencione diferencias y similitudes entre Branch and Bound y Branch and Cut.
El enfoque Branch and Bound intenta reducir la cantidad de pasos en un esquema de
enumeración exhaustiva. Constituye un esquema de “División y Conquista” que intenta
resolver el problema original dividiéndolo en subproblemas más pequeños, para los cuales
se computan cotas inferiores y superiores de valor óptimo. En un problema de minimización,
si la cota inferior sobre un nodo A del árbol de enumeración es mayor que la cota superior
de algún otro nodo B, entonces A puede ser descartada. Este paso se conoce con el
nombre de poda (prunning). Idealmente el procedimiento termina cuando todos los nodos
del árbol de enumeración son podados o resueltos.
Aunque este enfoque no genera buenos resultados en la práctica, forma parte de uno de los
conceptos básicos que hacen al método Branch and Cut. El mismo surge como un híbrido
de los métodos Branch and Bound y los métodos de plano de corte. Si luego de resolver la
relajación lineal de un subproblema, entonces se busca una desigualdad válida por el
óptimo de la relajación. Si se encuentran desigualdades violadas (cortes), se agregan a la
formulación y se resuelve el problema lineal nuevamente. Si no se encuentra ningún corte,
se continúa con el proceso de Branching
Para resolver el problema de la mochila de manera heurística se puede ordenar a los
objetos según el valor del índice Beneficio/Volumen. ¿qué inconvenientes puede
tener usar ese criterio para resolver el problema?
La heurística de la mochila tiende a funcionar en la mayoría de los casos, pero existen
casos patológicos
// Definiendo a:
● Z como el valor de la solución óptima.
● Z’ como el valor de la solución obtenida aplicando la heurística.
● Z’/Z índice de performance de la heurística
// Se puede demostrar que existen casos en el cual el índice de performance de la
heurística sea tan cercano a cero como se quiera
// Sea el siguiente problema de la mochila
# Capacidad de la mochila c=k
Item Beneficio Peso Relacion
A 1 + d 1 1 + d
b k k 1
Aplicando el algoritmo elegimos el producto A y en consecuencia nuestro funcional sería
igual a 1 ( Peso de A). Sin embargo, el valor de la solución óptima es k
En este caso, el índice de performance de la heurística será 1+d / k . Evidentemente para
casos elevados de k, el índice tiende a eso
Final 1 – Clase Teórica 16
C1 ¿Es útil como cota para el problema de coloreo de grafos la resolución de la
relajación lineal (es decir, haciendo que todas las variables sean continuas)? ¿por
qué?
En particular para el problema del coloreo de grafos no resulta útil la relajación lineal,
ya que la solución devuelta será siempre de 2 colores (utiliza la mitad de uno y la mitad
del otro para cada nodo).
C2 ¿Cuándo se dice que un problema está en NP? Un problema de programación
lineal
continua ¿está en NP?
Un problema de decisión está en NP si una máquina de Turing no determinística puede
resolverlo en un tiempo polinomial. A su vez, una máquina determinística debería poder
verificar que una solución propuesta es válida en tiempo polinomial.
Un problema de programación lineal continua está en P. Ergo, está en NP.
Final 2 – 3/8/2017
C1 Es necesario resolver varios problemas del viajante, de 3, 4, 10, 30, 100 y 5000
ciudades respectivamente, ¿cómo encararía cada uno? ¿Lo haría en todos los casos
de la misma manera o en alguno/s lo haría diferente? ¿por qué?
Siempre va a depender de lo que priorice la persona que pretende resolver el problema:
una solución exacta sin importar el tiempo que demore o una solución aproximada en un
tiempo razonable.
Más allá de esto, yo encararía los problemas de hasta 30 ciudades con un modelo de
P.L.E, dado que al pasárselo a un software tipo GLPK o LINDO obtengo una solución
exacta en un tiempo dentro de todo razonable. En cambio, para los problemas de más de
30 ciudades aplicaría una heurística de construcción (vecino más próximo, por ej.) y
luego una de mejoramiento (K-Intercambios, por ej.), para así obtener una solución
aproximada pero en un tiempo más que razonable.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de
asignación cuadrática
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de la asignación cuadrática consiste en determinar qué fábricas se
instalarán en qué ciudades de manera tal que el costo total de comunicación entre las
fábricas sea mínimo. Dicho costo depende de la frecuencia de comunicación y la
distancia entre las fábricas.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones
cotidianas de la realidad.
Algunas aplicaciones del problema del viajante son: recorrido de una persona por
distintas ciudades o lugares de manera tal que la distancia total sea mínima, fabricación
de circuitoselectrónicos, proveer almuerzos calientes a personas incapacitadas para
caminar.
Algunas aplicaciones del problema de la asignación cuadrática son: disposición de
tiendas en los centros comerciales de manera tal que el público recorra lo menos
posible, diseño de terminales en aeropuertos de manera tal que aquellos que realizan un
trasbordo recorran lo menos posible, diseño de teclados de computadoras de manera tal
que el desplazamiento con los dedos sea el menor posible, diseño de circuitos eléctricos
de manera tal que se minimice la distancia entre ciertos chips.
Final 3 – 27/7/2017
C1 ¿Cuál fue el aporte del método del elipsoide para resolver modelos de
programación lineal continua?
El método del elipsoide da una forma teóricamente satisfactoria de reconocer si un
sistema de desigualdades tiene solución.
Este algoritmo no pudo ser aplicado en la práctica, pero tiene un gran valor teórico ya
que demuestra que la programación lineal está en P.
C2 Detalle los pasos a seguir para resolver un problema de programación lineal
entera
utilizando planos de cortes Gomory (no es necesario indicar cómo se obtienen los
cortes)
Algoritmo de planos de corte Gomory:
1 – Se resuelve la relajación lineal del problema
2 – Si la solución es entera FIN
Si no Identificar una variable fraccionaria y agregarla al plano de corte Gomory
3 – Volver a 1
Final 4 – 20/7/2017
C1 El problema del viajante con ventanas de tiempo agrega la restricción de "horarios
de atención" en cada ciudad, indique y justifique a que clase(s) de complejidad
pertenece.
Considerando que el problema clásico del viajante de comercio (TSP) y que éste
(TSPTW) es una variante que complejiza la toma de decisiones y reduce las
posibilidades de las ciudades a visitar, concluyo que pertenece a la clase NP-Hard, al
igual que el TSP.
C2 Compare simplex con el método de punto interior de Karmarkar. Indique pros y
contras de cada uno.
El método de Karmarkar nos asegura que, si se encuentra el centro del poliedro, termina
en tiempo polinomial. Pero, si no se halla dicho centro, el algoritmo puede encontrar
una solución factible o no (más allá de la compatibilidad del problema). A su vez, no
nos ofrece soluciones alternativas.
En cambio, el método Simplex en promedio es polinomial (en la práctica), aunque en el
peor caso es exponencial (en la teoría). A pesar de esto, siempre devuelve una solución
(y nos permite detectar los 4 casos particulares, en caso de que los haya).
FINAL 5 – 13/7/2017
C1 En el caso de un modelo de programación lineal continua que maximiza beneficios
¿hay alguna variación en el poliedro de soluciones si la función objetivo pasara a ser
minimizar costos?
No hay ninguna variación en el poliedro de soluciones, aunque sí la habrá en el punto
óptimo. A su vez, un problema de maximización que resultaba en un poliedro abierto,
tendrá solución si se tratase de un problema de minimización.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de
distribución o transporte.
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
El viajante es NP-Hard , mientras que el problema de distribución está en P porque se
puede resolver con PLC. Ambas tienen importantes aplicaciones en situaciones de la
realidad.
En el problema de distribución o transporte puedo utilizar variables continuas y el
problema devolverá una solución entera (demostrado por teorema), mientras que esto no
es factible en el problema del viajante.
FINAL 6 – 6/7/2017
C1 ¿Qué es un plano de corte? ¿En qué caso la solución óptima de la relajación de un
PL Entero es también una solución óptima del PL Entero?
Un plano de corte es una desigualdad válida, no es parte de la formulación actual, no es
satisfecha por la solución óptima de la relajación lineal actual (la corta) y tiene un
algoritmo para encontrarlo.
Los métodos de planos de corte consisten en hacer el poliedro como si las variables
fueran continuas y luego recortarle los “bordes” para tratar de que quede el poliedro de
soluciones enteras. Por lo general, este trabajo no se hace en todo el poliedro, sino en las
inmediaciones de la solución óptima.
La solución óptima de la relajación lineal de un problema de PLE coincide con la
solución óptima del problema de PLE en sí cuando…
C2 Indique diferencias y similitudes entre el problema de distribución y el problema
de
asignación cuadrática.
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
El problema de la asignación cuadrática consiste en determinar qué fábricas se
instalarán en qué ciudades de manera tal que el costo total de comunicación entre las
fábricas sea mínimo. Dicho costo depende de la frecuencia de comunicación y la
distancia entre las fábricas.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones de la
realidad.
En el problema de distribución o transporte puedo utilizar variables continuas y el
problema devolverá una solución entera (demostrado por teorema), mientras que esto no
es factible en el problema de la asignación cuadrática.
FINAL 7 – 23/2/2017
C1 En términos de complejidad ¿cuándo un algoritmo es de clase NP y cuándo es de
clase NP Completo?
Un algoritmo es de clase NP cuando es no determinista polinómico. Es decir, se puede
resolver de manera polinomial en una máquina de Turing no determinista (a su vez, se
puede comprar en tiempo polinomial si una solución propuesta es válida o no).
En cambio, un algoritmo es de clase NP-Completo cuando se trata de un problema NP
específico con la particularidad de que si existe un algoritmo de clase P para resolverlo,
entonces cualquier problema NP puede resolverse con un algoritmo de clase P.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de la
mochila.
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de la mochila consiste en determinar qué objetos meter en la mochila sin
superar su límite de peso, de manera tal que el beneficio de los objetos guardados sea
máximo.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones de la
realidad.
En ninguno de los dos problemas es factible la relajación lineal, aunque en el caso de la
mochila puede ser utilizada como cota para medir si una heurística es buena o no.
FINAL 8 – 16/2/2017
C1 Indique diferencias entre planos de corte generales y específicos.
Los planos de corte generales sólo se basan en la condición de la integrabilidad de las
variables, pueden ser utilizados para cualquier PLE y son muy débiles. Ejemplos de
estos son los planos de corte Gomory.
En cambio, los planos de corte específicos son particulares para cada problema de PLE
y resultan más robustos. Ejemplos de estos son las desigualdades de cubrimiento
extendida y ajustada y para conjuntos independientes.
C2 ¿En qué se parecen y en qué se diferencian el problema de distribución y el
problema de asignación?
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
El problema de asignación consiste en determinar qué personas realizan cada uno de los
trabajos, de manera tal que la ganancia total por la realización de los trabajos con las
personas determinadas sea máxima. Es un caso particular del problema de transporte,
donde todas las ofertas y demandas son igual a 1.
Ambos problemas son NP-Hardy tienen importantes aplicaciones en situaciones de la
realidad.
Tanto en el problema de distribución o transporte como en el de asignación puedo
utilizar variables continuas y el problema devolverá una solución entera (demostrado
por teorema).
FINAL 9 – 9/2/2017
C1 Indique diferencias entre el algoritmo Branch and Bound y planos de corte.
El método de Branch and Bound consiste en ir armando un árbol de soluciones, de
manera tal que a cada nodo del árbol le corresponde un subproblema, mientras que el
problema original se encuentra en la raíz. En cada nodo del árbol se calcula una cota del
óptimo restringido a ese espacio de soluciones.
Lo interesante aquí es que, si llegamos a una cota que es peor que la mejor solución
obtenida hasta el momento, ya podemos dejar de explorar esa rama del árbol. La cota de
cada nodo se obtiene resolviendo la relajación lineal del subproblema en cuestión.
Un nodo no tiene sucesores cuando el subproblema no es factible, cuando se llega a una
solución no entera peor que la mejor solución o cuando se llega a una solución entera.
En cambio, los métodos de planos de corte consisten en hacer el poliedro como si las
variables pudieran tomar valores continuos y luego “recortarle” los bordes para tratar de
que quede el poliedro de soluciones enteras. Esto se suele hacer en las inmediaciones de
la solución óptima, no en todo el poliedro.
C2 ¿Por qué el problema del viajante es un problema difícil? ¿Todos los problemas
del
viajante son igualmente difíciles?
Un problema en general se categoriza como difícil si su solución requiere de una
cantidad significativa de recursos computaciones, más allá del algoritmo utilizado.
En particular, el problema del viajante pertenece a esta categoría (es NP-Hard).
Cualquier algoritmo conocido para su resolución lleva un número exponencial de pasos.
La cantidad de caminos posibles a realizar es n!, donde n es la cantidad de ciudades del
problema.
No todos los problemas del viajante son igual de difíciles: algunos resultan más triviales
que otros, por las distintas conexiones entre las ciudades.
FINAL 10 – 22/12/2016
C1 En planos de corte ¿qué es la cápsula convexa? ¿qué es una faceta?
La cápsula convexa es el recinto más chico que contiene a todas las soluciones factibles.
Se lo puede formular utilizando solo facetas.
Una faceta es una desigualdad válida cuya intersección con el poliedro tiene dimensión
igual a la dimensión del poliedro menos uno.
C2 En una de las formulaciones del problema del viajante se agregan variables Ui
¿para
qué se agregan? ¿cuál es el significado de esas variables? ¿son enteras o
continuas?
Las variables Ui (son enteras, aunque no se las defina de tal forma) se agregan para
evitar subtours. Se define Ui como el número de secuencia en el cual la i-ésima ciudad
es visitada. El rango de i es desde 1 hasta n. Notar que el 0 queda afuera, ya que es la
ciudad de origen a la cual hay que regresar.
FINAL 11 – 15/12/2016
C1 Mencione y explique brevemente cotas que se pueden usar para resolver el
problema de la mochila con heurísticas.
En la resolución heurística del problema de la mochila, las cotas se utilizan para medir
qué tan buena es nuestra heurística. Si sabemos que el óptimo es X y nuestra heurística
nos está dando un resultado de X4, se sospecha que no es para nada buena.
A continuación, algunas cotas que se pueden utilizar:
- Relajación Lineal. Implica permitirle tomar valor continuo a las variables.
- Dantzig. Aplica una condición de integralidad.
- Martello & Toth. Establece la integridad del elemento crítico.
C2¿Cuándo termina el algoritmo Branch and Bound? ¿puede terminar sin encontrar
el
óptimo entero?
El algoritmo termina cuando se terminan de explorar todas las ramas del árbol generado.
Es importante tener en cuenta que un nodo no tiene sucesores cuando:
- El subproblema no es factible
- El subproblema tiene una solución no entera peor a la mejor solución encontrada
hasta el momento
- El suproblema tiene una solución entera
Puede terminar sin encontrar el óptimo entero en caso de llegar a todas ramas
Incompatibles.