Document

Transcript

M´ etodos volum´ etrico y de Relax-and-Cut: Relaci´ on con los m´ etodos de haces Claudia Sagastiz´ abal mailto:[email protected] http://www.impa.br/~sagastiz 1 3 Problemas Optimizaci´ on Combinatoria – Steiner en Grafos Rectil´ıneos (SR) – Ordenamiento Lineal (LOP) – Viajante de Comercio (TSP)    max C(p)    p gj (p) ≤ 0 , j = 1, . . . , n,      p ∈ Q ⊂ IRm – p variable primal – C costo (linear o convexo) – gj restricciones “hard” – Q restricciones f´ aciles (puede ser discreto) 1.1 Problema de Steiner (ST ) G = (V, E) grafo no direccionado |T | v´ ertices terminales costos aristas ce ≥ 0 ? subgrafo S ⊂ G conexo que contenga a T , con m´ınimo Formulaci´ on “single commodity flow” costo X e∈S (Claus & Maculan 83, Wong 84) – Crear arcos (i, j) (j, i), costo cij = cji = ce ⇒ Gd = (V, Ed ) – Fijar fuente s ∈ T , v´ ertices restantes k ∈ T0 := T \{s}. – s ofrece “commodity” f k a cada k (proporci´ on fijk por arco (i, j)) – zij = 0 si arco 6∈ Steiner Tree. – Variables: A := {(z, f ) = (zij , fijk ) : (i, j) ∈ Ed , k ∈ T0 } – V´ ertices entrada I(i) := {e ∈ Ed : e = (j, i)} – V´ ertices salida O(i) := {e ∈ Ed : e = (i, j)} ce (ST )    min hc, zi   (z,f )∈A   P P   k k  f − f = 1 , k ∈ T0  sj js j∈O(s) j∈I(s)   P P  k k j∈O(k) fkj − j∈I(k) fjk = −1 , k ∈ T0 P P  k k  f −  j∈O(i) ij j∈I(i) fji = 0, i ∈ V \ {s, k}, k ∈ T0      zij ∈ {0, 1}, (i, j) ∈ Ed .      0 ≤ fijk ≤ zij , (i, j) ∈ Ed , k ∈ T0 (a1 ) (a2 ) (a3 ) (Int) (Hip). (ST )    max −hc, zi   (z,f )∈A   P P   k k  f − f  j∈O(s) sj j∈I(s) js = 1 , k ∈ T0   P P  k k f − f j∈O(k) kj j∈I(k) jk = −1 , k ∈ T0 P P  k k  f − f = 0, i ∈ V \ {s, k}, k ∈ T0  ij ji j∈O(i) j∈I(i)      zij ∈ {0, 1}, (i, j) ∈ Ed .      0 ≤ fijk ≤ zij , (i, j) ∈ Ed , k ∈ T0 p ↔ (z, f ) −hc, zi ↔ C(p) (a1 -a3 ) ↔ g(p) ≤ 0 (Int+Hip) ↔ p ∈ Q ⇒ (ST )                    (a1 ) (a2 ) (a3 ) (Int) (Hip). max C(p) p gj (p) ≤ 0 , j = 1, . . . , n, p ∈ Q ⊂ IRm 1.2 LOP N elementos costo de colocar elemento i antes de elemento j cij ? ordenar elementos en l´ınea con m´ınimo costo pij = 0 si i antes de j (LOP )    //////// min max −   p                   X cij pij (i,j):i6=j pij + pji = 1, ∀(i, j) ↔Q pij ∈ {0, 1}, ∀(i, j) ↔Q pij + pjk + pki ≤ 2, ∀(i, j, k) ↔ g(p) ≤ 0 1.3 TSP G = (V, E) de ciudades costo de pasar por la arista e ce ? m´ınimo costo de recorrido One-tree formulation (Held & Karp) (Comb inequalities Handle, T eeth) (T SP )    //////// min max −   p                   X X    pHi + pTj ≤    i≤s−1 j≤t + X ce pe X pe = 2 s-regular t-path inequalities e∈E ↔Q δ(j) p is a 1-tree ↔Q P P |H | + i i≤s−1 j≤t |Tj | − K(s, t) ↔ g(p) ≤ 0 2 Dualizando restricciones dif´ıciles      maxp C(p) Dos opciones p/dual: p∈Q     gj (p) ≤ 0, j ≤ n • n no muy grande: bundle cl´ asico ⇒ Volumen • n enorme:bundle din´ amico ⇒ Relax&Cut Referencias (http://www.impa.br/˜sagastiz): – The volume algorithm revisited. Relation with bundle methods, L. Bahiense, N. Maculan, C. Sagastiz´ abal. Math. Progr. 94(1) (2002) pp 41-69. – Dynamic Bundle Methods. Application to Combinatorial Optimization, A. Belloni, C. Sagastiz´ abal, preprint 2003. – Numerical Optimization. Theoretical and Practical Aspects J.F. Bonnans, J.Ch. Gilbert, C. Lemar´ echal, C. Sagastiz´ abal. Universitext. Springer-Verlag, Berlin, 2003. 2.1 Lagrangiano y funci´ on dual (P )    max C(p)    p p∈Q      gj (p) ≤ 0, j ≤ n↔ multiplicador x ≥ 0 Lagrangiano:  L(p, x) := C(p) − g(p), x = C(p) − (P ) ≡ X gj (p)xj j≤n max min L(p, x) {p∈Q} x≥0 Se, para x fijo, resolver max L(p, x) = {p∈Q} es “f´ acil”, entonces     max C(p) − x, g(p) p   p∈Q (P ) ≡ max min L(p, x) {p∈Q} x≥0 Problema dual: min max L(p, x) (D) x≥0 {p∈Q} ⇒ funci´ on dual f (x) := max L(p, x) = max {p∈Q} {p∈Q} (D) ≡  C(p) − x, g(p) min f (x) x≥0   2.2 Propiedades duales Dualidad d´ ebil  ∀p ∈ Q : g(p) ≤ 0   ∀x ≥ 0 C(p) ≤ f (x) ⇒ opt(P ) ≤ opt(D) Cuando hay igualdad (si convexidad + (QC)): salto de dualidad 0 Si no, resolver (D) 6≡ resolver (P):   max x ¯ = arg min f (x) p∈Q C(p) dados  Everett: p¯ resuelve  p¯ : f (¯ x) = C(¯ p) − x ¯, g(¯ p) g(p) ≤ g(¯ p) En general no se satisface g(¯ p) ≤ 0. Etapa de “recuperaci´ on primal” necesaria. 2.3 Funci´ on dual m´ aximo de funciones afines (lineales) en x: f (x) = max C(p) − x, g(p) {p∈Q}  f(x) C(p )- 3 3 C(p1)- C(p )- 2 2 – no diferenciable, donde hay m´ as de un p que maximiza (“activo”):  f (x) = C(p1 ) − x, g(p1 ) = C(p2 ) − x, g(p2 ) – subdiferencial  ∂f (x) = conv −g(px ) : px activo – Conocer el valor de f (x) ⇒ conocer un subgradiente f (x) = C(px ) − x, g(px )  y g := −g(px )  Para (LOP ) la evaluaci´ on de f (x), g(x) es f´ acil: f (x) =     max −   p              X cij pij − (i,j):i6=j pij + pji = 1, pij ∈ {0, 1}, X   xijk pij + pjk + pki − 2 i,j,k ∀(i, j) ∀(i, j) Para (ST ) tambi´ en: f (x) =  X X  k k k  max −hc, zi− (x − x )f  i j ij − hb, xi    (z,f )∈A k∈T0 (i,j)∈Ed       (b vector de 0, ±1) zij ∈ [0, 1], (i, j) ∈ Ed . 0 ≤ fijk ≤ zij , (i, j) ∈ Ed , k ∈ T0 (//// Int) (Hip). 3 M´ etodos de optimizaci´ on no diferenciable (OND) Caso sin restricciones min f (x) x f • Caja “negra” x • Especiales p/OND. g 3.1 ¿Por qu´ e m´ etodos especiales? M´ etodos tradicionales no funcionan Test de parada diferenciable: k∇f (xk )k ≤TOL abs 0 f (x) |∇f (xk )| 3.2 = |x| = 1 , ∀x 6= 0 CLAVES: • Generar direcciones de descenso dk : ∃t > 0 f (xk + tdk ) < f (xk ) • Definir criterios de parada • Estabilidad (num´ erica) 3.3 En busca de direcciones de descenso Esquema algor´ıtmico • Paso 1: Dado xk , – Test de parada: 0 ∈ ∂f (xk )? – Hallar dk , una direcci´ on de descenso en xk . • Paso 2: B´ usqueda lineal, con (xk , dk ) dados. tk := “arg min”t>0 f (xk + tdk ) • Paso 3: Descenso xk+1 := xk + tk dk k = k + 1. Volver a 1. Esquema algor´ıtmico de subgradientes • Paso 1: Dado xk , – Test de parada: 0 ∈ ∂f (xk )? – Hallar dk , una direcci´ on de descenso en xk . dk := −gk ∈ ∂f (xk ) gk (o − ) kgk k • Paso 2: B´ usqueda lineal, con (xk , dk ) dados. tk := “arg min”t>0 f (xk + tdk ) • Paso 3: Descenso xk+1 := xk + tk dk k = k + 1. Volver a 1. PERO... 3.4 ... problemas num´ ericos!!! • Test de parada IDEAL: ∂f (xk ) desconocido (solamente 1 subgradiente) • dk puede no ser direcci´ on de descenso: x2 x2 grad 0 x1 0 x1 s ⇒ la b´ usqueda lineal fracasa: 6 ∃t > 0 satisfaciendo f (xk − tgk ) < f (xk ) Puede probarse convergencia sin descenso y con BL “inteligente”. 3.5 En busca de criterios de parada implementables CLAVE: construir un modelo de f ¿C´ omo? guardando informaci´ on pasada  Dado el Haz de informaci´ on (yi , fi , gi ) i≤k calcular:   fˇk (x) := yk+1 max {fi 1≤i≤k + hgi , x − yi i} := arg min fˇk (x) fˇk (yk+1 ) −→ f (¯ x) =⇒ δk := f (yk ) − fˇk−1 (yk ) reducci´ on esperada, mide bien la distancia a f (¯ x) Test de parada implementable: δk ≤ δmin PERO... 3.5.1 Subsisten problemas fx1 fx3 v fx2 f2 min2 min3 • Inestabilidad: • Converge solamente si acumula todas las “piezas” (yi , fi , gi ) , i = 1, · · · , k → ∞!!! 4 Algoritmo de descenso: m´ etodo de haces Idea: aceptar “candidato” solamente si hay descenso. Genera una sucesi´ on {y c } y una subsucesi´ on {ˆ x} donde hay descenso. ¿C´ omo? Recordando el mejor punto x ˆ generado: En la k-´ esima iteraci´ on tiene – Centro de estabilidad x ˆ tal que f (ˆ x) ≤ f (ylc ) , l < k. – Modelo de f , fˇk test de parada evita oscilaciones – Norma p/medir la distancia a xk Dado y c , un candidato a centro de estabilidad, usar el test de descenso para decidir si habr´ a – Paso Serio: nuevo centro, x ˆk+1 = y c descenso – Paso Nulo: modelo no es suficientemente bueno, x ˆk+1 = x ˆk . PROPIEDADES: 1. Gracias al modelo, δk disponible ⇒ test de parada 2. Genera la subsucesi´ on de descenso {ˆ xk } rechazando candidatos y c “malos”⇒ estable 3. Modelo mejora en cada iteraci´ on (f (y c ), g(y c )). 4. Permite modificar fˇk para guardar hasta un m´ aximo de piezas ⇒ compresi´ on 4.1 Algoritmo proximal de haces • Dado el haz {fi , gi , yi )}, y x ˆ – Buscando una direcci´ on de descenso en x ˆ: Generaci´ on del candidato (P Q) c y := arg min fˇ(y) + 1 µky − x ˆk2 2 δ := f (ˆ x) − fˇ(y c ) Evaluaci´ on del candidato: . Test de parada implementable: . Si f (y c ) ≤ f (ˆ x) − mδ: Serio(descenso) . Si f (y c ) > f (ˆ x) − mδ: Nulo δ ≤ δmin • Gesti´ on del haz: Incorporar y c , f c , g c . Comprimir si necesario. • Loop: Si Nulo, volver. Si Descenso x ˆ := y c y volver. 4.2 Propiedades de los subproblemas (PQ) Modelo fˇk re-escrito, centrado en x ˆ fˇk (y) = max{fi + hgi , y − yi i = f (ˆ x) + max{−ei + hgi , y − x ˆi} i≤k i≤k ei son los errores de linearizaci´ on en x ˆ: (0 ≤) ei := f (ˆ x) − fi − hgi , x ˆ − yi i f vxk e e e 1 2 3 ⇒ gi ∈ ∂f (yi ) y gi ∈ ∂ei f (ˆ x). Subproblema (PQ)   min r + 1 µky − x 2 ˆ k y 2 miny fˇk (y) + 12 µky − x ˆk2 ↔  r ≥ −ei + hgi , y − x ˆi l  X X  2 1  αi gi k + µ ei αi  minαi 2 k i    α ∈ ∆k := {z ∈ [0, 1]k : iX zi = 1} . Resoluci´ on dual permite “warm starts”. X 1 y =x ˆ− ˆ g con ˆ g := α ¯i gi µ i c ˆ g ∈ ∂ˆe f (ˆ x) con ˆ e := X i y 1 δ = kˆ g k2 + ˆ e µ α ¯i ei Gesti´ on del haz:  ei , gi  ¯ A posteriori α Sup. α ¯i > 0∀i ∈ J. ¯ resuelve tambi´ en  X X  2 1  αi gi k + µ ei αi  minαi 2 k i    α ∈ ∆ := {z ∈ [0, 1]J¯ : i X zi = 1} . (solamente los activos) La soluci´ on no cambia si guardamos s´ olo los elementos activos: (ei , gi ) , i ∈ J¯ La soluci´ on no cambia si guardamos s´ olo la combinaci´ on convexa optima de los elementos activos: ´ (ˆ e, ˆ g) El haz de informaci´ on puede ser comprimido en hasta 2 ´ unicos elementos: (ˆ e, ˆ g ) y (ec , gc ) poor man 4.3 M´ etodo de haces “poor man” (BPM) • Dado el haz {(ˆ e, ˆ g ) y (e, g)} y x ˆ: – Generaci´ on del candidato: α ¯ soluci´ on de 1 kαg + (1 − α)ˆ g k2 + µαe + (1 − α)ˆ e α∈[0,1] 2 min 1 y =x ˆ− ˆ g con ˆ g + := α ¯g + (1 − α ¯)ˆ g µ c ˆ g + ∈ ∂ˆe+ f (ˆ x) con ˆ e+ := α ¯e + (1 − α ¯)ˆ e δ := µ1 kˆ g + k2 + ˆ e+ Evaluaci´ on del candidato: . Test de parada implementable: . Si f (y c ) ≤ f (ˆ x) − mδ: Serio x ˆ := y c . . Si f (y c ) ≥ f (ˆ x) − mδ: Nulo δ ≤ δmin • Gesti´ on del haz: {(ˆ e, ˆ g ) := (ˆ e+ , ˆ g + ) y (e, g) = (ec , g c ) Loop 5 M´ etodos volum´ etricos F. Barahona y R. Anbil. The volume algorithm: producing primal solutions with a subgradient method. Math. Program., 87(3):385–399, 2000. Para LP de tama˜ no grande      maxp C(p) p∈Q     gj (p) ≤ 0, j ≤ n ↔      maxp hc, pi p∈Q     Ap ≤ b (Subgradientes: −(Ap − b)) Combina resoluci´ on del problema dual, similar a BPM, con recuperaci´ on primal. 3 variantes analizadas: – Volume algorithm – Revised Volume algorithm – Bundle algorithm (poor man) 5.1 M´ etodo de Volumen (VA) • Dato primal: pˆ • Dados el haz {(ˆ e,ˆ g ) y (e,g)} y x ˆ: – Generaci´ on del candidato: α ¯ ∈ [0, 1] arbitrario yc = x ˆ− 1 ˆ g con ˆ g + := α ¯g + (1 − α ¯)ˆ g µ ˆ g + ∈ ∂ˆe+ f (ˆ x) con ˆ e+ := α ¯e + (1 − α ¯)ˆ e δ := µ1 kˆ g + k2 + ˆ e+ Evaluaci´ on del candidato: pˆ+ = α ¯pc + (1 − α ¯)ˆ p) . Test de parada implementable: . Si f (y c ) < f (ˆ x)−mδ: Serio x ˆ := y c . . Si no, paso Nulo δ ≤ δmin • Gesti´ on del haz: Updates ˆ g=ˆ g+ , g = gc , • Loop pˆ = pˆ+ 5.1.1 Caracter´ısticas VA Rol de pˆ? Restricci´ on relajada g(p) = Ap − b linear pˆ+ = α ¯ Aˆ p+ − b = α ¯ = α ¯ = ˆ+ −G pc   Apc − b   −g c + (1 − α ¯) + (1 − α ¯) + (1 − α ¯) pˆ   Aˆ p−b   ˆ −G PERO: el valor de z para el cual pˆ resuelve maxp C(p) − hz, Ap − bi = f (z) es desconocido! ¿qu´ e hacer? Calculando recursivamente zˆ+ := α ¯y c + (1 − α ¯)ˆ z (ˆ z0 = x ˆ0 ) y ε+ := α ¯(1 − α ¯) hˆ z − yc , g − ˆ g i + (1 − α ¯)ε se satisface que ˆ g + ∈ ∂ε+ f (ˆ z+) ˆ g + ∈ ∂ˆe+ f (ˆ x) yc = x ˆ− 1 ˆ g µ (VA) es un m´ etodo de ε-extrasubgradiente.... 5.2 Introduciendo un modelo Cantidades disponibles: x ˆ, f (ˆ x)   y c , f c , g c ∈ ∂f (y c )  zˆ,f (ˆ z ), ˆ g ∈ ∂ε f (ˆ z) ⇒ (ec , g c ∈ ∂ec f (ˆ x)) ok  ˆ tal que ˆ No conocer f (ˆ z ) impide calcular E g ∈ ∂Eˆ f (ˆ x) 2 posibilidades ˆ – aproximar f (ˆ z ) para definir E – eliminar zˆ BPM. RVA 5.3 Volumen “revisado” aproximar f (ˆ z ) usando el mejor valor, f (ˆ x):   ˆ = f (ˆ E x) − f (ˆ z ) + hˆ g, x ˆ − zˆi + ε   ≈ f (ˆ x) − f (ˆ x) + hˆ g, x ˆ − zˆi − ε ε − hˆ g, x ˆ − zˆi = f f ? ? x x e 2 E 1 e o, peor, 2 5.4 RVA • Dato primal: pˆ ˆ ˆ • Dados el haz {(E, g ) y (e, g)} y x ˆ: – Generaci´ on del candidato: α ¯ soluci´ on de 1 ˆ min kαg + (1 − α)ˆ g k2 + µαe + (1 − α)E α∈[0,1] 2 1 y =x ˆ− ˆ g con ˆ g + := α ¯g + (1 − α ¯)ˆ g µ c + ˆ g + ∈ ∂ˆe+ f (ˆ x) con ˆ e := α ¯e + (1 − α ¯)ˆ e δ := µ1 kˆ g + k2 + | ˆ g+ , x ˆ − zˆ | + ε Evaluaci´ on del candidato: pˆ+ = α ¯pc + (1 − α ¯)ˆ p) . Test de parada implementable: δ ≤ δmin . Si f (y c ) < f (ˆ x) − mδ: Serio x ˆ := y c . . Si no, paso Nulo • Gesti´ on del haz: Updates ˆ = (ˆ ˆ+ ) , (g, e) = (g c , ec ) , (ˆ g , E) g+ , E Loop pˆ = pˆ+ 5.4.1 Propiedades de RVA f ? x e 2 ˆ ≤ 0, y Aunque ˆ g ∈ ∂Eˆ f (ˆ x), E puede probarse convergencia de RVA en algunos casos Resultado Dual Sup. Q acotado y (P) tiene soluci´ on. – Si hay infinitos pasos serios, y t = µ1 forma una serie divergente y acotada, entonces {ˆ z } es minimizante. – Si hay infinitos pasos nulos y {t} est´ a inferiormente acotada, el ´ ultimo paso serio es una soluci´ on de (D) si {y c } tiene un ´ unico punto de acumulaci´ on – Resultado Primal Si A tiene rango completo, existe L = L(datos) tq k¯ p − pˆlast k ≤ Lδlast 6 Resultados num´ ericos • 50 de los 116 VLSI en SteinLib ftp://ftp.zib.de/pub/mp-testdata/steinlib Grupos dmxa, taq,alue,gap,msm,diw. • t=ν f c −lb kˆ g k2 ν ∈ (0, 2) • lb calculadas con heur´ısticas (“minimun spanning tree”) • Varios tests de parada Algoritmo general. Upper bound Hacer una iteraci´ on dual (VA, RVA, BPM). Calcular ub y pˆ Lower bound . Si paso serio o muchos nulos, heur´ısticas a partir de pˆ. Calcular lb y t. Test de parada . Si ub − lb < 1 STOP (idg) Si δ ≤ δmin , STOP Si (!!) (m´ ax it. CPU”), STOP. Loop. 6.0.2 Resultados primales y duales (RVA) Res.Primales Res.Duaes Grupo (%)OP T (%)P rDist (#)SubP b StopT CP UTime (s) dmxa 100.00 15.17 6896 (idg) 369.19 taq 100.00 12.33 268205 (idg) 9094.70 alue 100.00 14.68 2770 (idg) 412.71 gap 80.00 15.28 503330 (idg) 240.56 msm 83.33 19.18 557269 (idg) 15537.75 diw 81.82 15.38 23503 (idg) 15572.89 Resultados Primales y Duales: RVA mejor. CPU time: VA < RVA< BPM. RVA buen compromiso p/pbmas dif´ıciles 7 M´ etodos Relax & Cut      maxp C(p) p∈Q     gj (p) ≤ 0, j ≤ n • n ≈ 1010 ⇒ Relax&Cut (bundle din´ amico) o(N 3 ) restricciones pij + pjk + pki ≤ 2 (LOP): (TSP): # exponencial de “Comb inequalities” ⇒ c´ alculo de f (x) = max C(p) − hx, g(p)i = max C(p) − p∈Q p∈Q n X j=1 xj gj (p) Idea de R&C: relajar solamente algunas restricciones, p.ej, las m´ as violadas en c/iteraci´ on. (OC: “incorporar desigualdades”, “separar”) M´ etodo primal-dual: PRIMAL selecciona restriccione (agrega desigualdades) px


    
         
     f(x)    x x  actualiza "multiplicador"
DUAL g(x) px SEPARATION ORACLE J restricciones a dualizar 7.1 Informaci´ on dual disponible f (x) = maxp∈Q C(p) − En lugar de n X xj gj (p) j=1 tenemos, para J variando en cada iteraci´ on, max C(p) − p∈Q X xj gj (p) con |J| << n j∈J ??? En lugar de x, la proyecci´ on de x en IR|J| f (PJ (x)) = max C(p) − p∈Q = C(pP J  Subgradiente:s(PJ (x)) = − gj (pP J (x) )− X j∈J X j∈J xj gj (p) xj gj (pP ) , 0n−|J| (x) j∈J J  (x) ) ∈ ∂f (PJ (x)) s(PJ (x)) ∈ ∂f (PJ (x)) =⇒ s es subgradiente de f ◦ PJ y NO de f : f (y) ≥ f (PJ (x)) + hs(PJ (x)), y − PJ (x)i solamente si y = PJ (y) La pieza f (PJ (x)) + hs(PJ (x)), y − PJ (x)i del modelo fˇ puede cortar la funci´ on: Z 18 9 0 -3 -3 0 0 Y X 3 3 7.2 Si Elementos del haz 
 j ≤ n : gj pP (x) > 0 J ⊂J (∗) ⇒ f (y) ≥ f (PJ (x)) + hs(PJ (x)), y − PJ (x)i s´ olo entran en el haz y c cuyos pyc satisfacen (∗) Haz: ei , gi

y Como gi ∈ ∂f PJi (yi ) ,
fˇ no es un modelo para f ◦ PJ , sino un modelo para f + I≥0 x ˆ, J para todo 7.3 Dificultad adicional Subproblemas PQ:   1 2  min r + µky − x ˆ k y  2     r ≥ −e + hg , y − x ˆi i i   y≥0      y = P (y) J
1 y =x ˆ− ˆ g con ˆ g ∈ ∂ˆe f ◦ +I{xj ≥0,j∈J} (ˆ x) µ c 1 δ = kˆ g k2 + ˆ e µ ... Complica an´ alisis de convergencia. 8 M´ etodo din´ amico de haces x, f, J c f gc c y J, p y,c g, e QP c Sep. Or. pc I no vacio J=J I U I I vacio: Iniciar mecanismo de haces: • Evaluaci´ on del candidato: – Test de parada: δ ≤ δmin .   x c ˆ = y – Si f (y c ) ≤ f (ˆ x) − mδ: Serio  J := {j : y c ≥ εmach > 0} j – Si f (y c ) > f (ˆ x) − mδ: Nulo • Gesti´ on del haz: Incorporar ec , g c , comprimir si necesario. • Loop 8.1 Resultados de convergencia Sup. Sep-Or es capaz de identificar todas las restricciones activas: Para toda {pk , Jk } infinita, con Jk+1 ⊃ Jk ∪ SepOr(pk , Jk ) ∃K : Jk = J¯ para todo k ≥ K. Sep-Or satisface: J¯ ( {1, . . . , n} ⇐⇒   min f (x) toda soluci´ on  x ∈ IRn ¯ J,≥0 Teorema   min f (x) es soluci´ on  x ∈ IRn . ≥0 Si δmin = 0, el algoritmo cicla infinitas veces. – Si hay infinitos pasos serios, o bien f (ˆ x) & −∞, o bien f es limitada inferiormente. En este caso, •si {µ} acotada, {ˆ x} minimizante. •Si, adem´ as, µ ≥ µlow > 0, {ˆ x} converge a una soluci´ on. – Si hay infinitos pasos nulos, el ´ ultimo paso serio es una soluci´ on. 8.2 Resultados Num´ ericos Casos de LOLIB y TSPLIB (sim´ etricos) comparando con R&C subgradiente (SR&C): – CPU times siempre menores que SR&C. – LOP, duality gap 0 o menor que 0.02 en los 44 casos. SR&C tiene gaps de hasta 0.1: – TSP duality gaps variables. Instance Size Iter Optimal SM Gap(%) 3-cycle Time (ms) be75eec 50 5000 264940 264980 0.015 26780 215740.0 be75np 50 5000 790966 791386 0.053 20383 193290.0 be75oi 50 5000 118159 118247 0.074 38520 301540.0 be75tot 50 5000 1127387 1127494 0.009 17982 151600.0 stabu1 60 5000 422088 422754 0.158 39999 302470.0 stabu2 60 5000 627929 628317 0.062 39999 306750.0 stabu3 60 5000 642050 642791 0.115 39999 308460.0 Instance Size Iter Optimal BM Gap(%) 3-cycle Time (ms) be75eec 50 363 264940 264944 0.002 7874 68870.0 be75np 50 2000 790966 791127 0.020 21550 876500.0 be75oi 50 325 118159 118166 0.006 30558 82560.0 be75tot 50 418 1127387 1127403 0.001 4579 57120.0 stabu1 60 436 422088 422113 0.006 14282 133640.0 stabu2 60 904 627929 627949 0.003 18203 477520.0 stabu3 60 434 642050 642073 0.004 14818 148410.0 Instance Size Iter Optimal SM Path Gap(%) Time d198 198 5000 15780 15705 30 0.4727 75 pr226 226 5000 80369 80090 25 0.3465 87 pr264 264 5000 49135 48895 25 0.4886 119 rat575 575 5000 6773 6724 36 0.7277 534 rat783 783 5000 8806 8773 35 0.3796 1032 pcb1173 1173 5000 56892 56350 43 0.9529 1921 Instance Size Iter Optimal BM Path Gap(%) Time d198 198 2001 15780 15725 669 0.3463 441 pr226 226 2001 80369 80334 73 0.0430 130 pr264 264 2001 49135 48528 235 1.2345 332 rat575 575 1170 6773 6746 163 0.4057 822 rat783 783 1887 8806 8786 396 0.2302 2386 pcb1173 1173 1660 56892 56592 308 0.5276 5471