Upload
makya
View
104
Download
3
Embed Size (px)
DESCRIPTION
Programación entera y grafos. Algunos de problemas definidos sobre grafos, son ILP / son LP con solución entera: flujo a costo mínimo y sus casos particulares: pb del trasporte, flujo máximo, camino más corto - PowerPoint PPT Presentation
Citation preview
Programación entera y grafos
• Algunos de problemas definidos sobre grafos, son ILP / son LP con solución entera: flujo a costo mínimo y sus casos particulares: pb del trasporte, flujo máximo, camino más corto
• Problemas de matching/covering: problemas de tipo afectación de recursos, que si bien no tienen una matriz de restricciones TUM, admiten un algoritmo de resolución en tiempo polinomial dependiendo de M (cant. vértices) y N (cant. de aristas)
• Def.: sea un grafo no dirigido G=(V,E) y un subconjunto S E, el grado de un vértice i respecto a S dS(i)= nro de aristas de S incidentes a i.
• Def: Sea M E, M es un “matching” de G si dM(i)1 i V.
• NOTA: todo grafo contiene trivialmente un matching vacío. En lo que sigue suponemos G conexo.
• Def: Matching máximo (MM): un matching M* es MM si M*=max{M, /M es matching}
• Def: Matching de peso máximo: sea cpj el peso asignado a la arista ej, y sea w(M) el peso del matching M/ w(M)=ejM ej, M* es un matching de peso máximo si w(M*) w(M) M
• Def: dado b=(b1..bm) / bi Z+M es un b-matching si dM(i)bi
• Matching de peso máximo como ILP:
Max cx /
Ax b, x binario y A matriz de incidencia nodos-arcos.
• Def: C E es un “covering” de G=(V,E) si dc(i) 1 i V.
• Cover mínimo y b-cover se definen en forma similar a matching
• Covering de peso mínimo como ILP:
Min cx /
Ax b, x binario y A matriz de incidencia nodos-arcos.
G Mínimo cover C* Máximo matching M*
• Teo: Sea C* un mínimo cover, si a todo vértice i /dC*(i) >1 le extraemos dC*(i)-1 arcos incidentes, el resultado es un conjunto de arcos que es un máximo matching M*
• Teo: Sea M* un matching máximo, si a todo vértice i /dM*(i) =0 le agregamos 1 arco incidente, el resultado es un conjunto de arcos que es un cover mínimo C*
• Def: Camino alternativo relativo a M es un camino tal que sus arcos alternan entre M y E\M
• Def: nodo expuesto relativo a M es un nodo v / dM(i)=0
• Def: Camino aumentativo: es un camino alternativo conectando dos vértices i y k expuestos relativos a M (dM(i)=dM(k)=0 )
• NOTA: un camino aumentativo debe tener un nro impar de arcos:
• Ejemplo:
M={e2}, camino aumentativo={e1,e2,e3}
M’={e1,e3} no hay camino aumentativo
• Teo: Un matching M es máximo sii no existe camino aumentativo relativo a M
• Teo: G es un grafo bipartito sii no tiene ciclos impares
i k
e2
e1
e3
Algoritmo para encontrar M* en grafos bipartitos:• Etiquetas de nodos (a,b), donde a={E,O} (par,impar)
• Inicialización: M matching arbitrario, todos los nodos de V sin etiquetar y no visitados
1- (test optimalidad): hay nodos expuestos no etiquetados? No: fin. Si hay, elegir un nodo expuesto no etiquetado r, etiquetarlo con (E,-)
2- (crecimiento de árbol alternativo) elegir un nodo i etiquetado pero no visitado, si es par, etiquetar todos sus vecinos no etiquetados con (O,i) y poner i como nodo visitado. Ir a 3. Si el nodo i es impar y expuesto, ir a 4, de lo contrario etiquetar todos sus vecinos no etiquetados con (E,i) y poner i como nodo visitado.
3- Si existen nodos etiquetados, no visitados ir a 2, de lo contrario ir a 1.
4- (identificación de camino aumentativo) Usando la segunda componente de la etiqueta, identificar el camino aumentativo de r a i. Eliminar todas sus etiquetas y actualizar el matching , ir a 1.
• Teo: el algoritmo anterior encuentra un matching de cardinalidad máxima en un grafo bipartito.
• El algoritmo falla si el grafo no es bipartito:
• Si bien hay dos caminos alternativos entre 1 y 4, (caminos aumentativos de largo impar), el algoritmo anterior no los encuentra por la forma de etiquetar.
1
2
3 4(E,-)
(O,1)
(O,1)
• Teo: Sea B una matriz básica para una solución básica del problema de 1-matching máximo: Ax1, cada componente de xB=B-1.b es 0,1 o 1/2
• Teo: La envoltura convexa de {x/ Ax 1, x binario}, donde A es la matriz de incidencia de G, está dada por las restricciones Ax 1 y una restricción del tipo xj K (para los elementos pertenecientes a los ciclos impares)