ࡱ> +-*bjbjUU =??   @_aaaaaaLaav__0wg"cK0,aa : Ttulo Column Generation over Set Partitioning Formulations: Theory and Practice Abstract This thesis presents theoretical and practical contributions on the use of column generation over set partitioning formulations. On the theoretical side, the set packing and set partitioning polytopes associated with a binary n-row matrix having all possible 2^n-1 columns are analyzed. We show the precise relation between those polytopes: with very few exceptions, every facet-inducing inequality for the former polytope is also facet-inducing for the latter polytope, and vice-versa. Moreover, we characterize the multipliers that induce Chvtal-Gomory rank 1 clique facets and give several families of multipliers that yield other facets for arbitrarily large dimensions. On the practical side, we present a novel branch-and-price algorithm over a set partitioning formulation for the Minimum Latency Problem (MLP), a variant of the Traveling Salesman Problem. The proposed algorithm strongly relies on new features for the ng-path relaxation, the current best-performing path relaxation employed by many exact algorithms for routing problems. Such new features are not built over any strong assumption on the MLP and can be potentially used in several other problems. Computational experiments over TSPLIB instances are reported, showing that several instances not solved by the current state-of-the-art method can now be solved. Keywords: Set Partitioning, Column Generation, Rank 1 Cuts, Polyhedral Combinatorics, Routing, ng-paths. Resumo Esta tese apresenta resultados tericos e prticos a respeito do uso de gerao de colunas a partir de formulaes de particionamento de conjuntos. Na parte terica, so estudados os poliedros de particionamento e empacotamento de conjuntos associados a uma matriz binria com n linhas e 2^n-1 colunas. Um forte relao entre esses poliedros provada: com algumas poucas excees, as inequaes que induzem facetas desses poliedros so iguais. Alm disso, caracterizam-se os multiplicadores que induzem as inequaes de clique que podem ser obtidas por uma nica aplicao do procedimento de arredondamento de Chvtal-Gomory (cortes de posto 1) , bem como apresentam-se famlias de multiplicadores que induzem facetas para dimenses arbitrrias (no necessariamente cliques). Na parte prtica, apresentado um algoritmo branch-and-price para o Problema da Latncia Mnima (PLM), uma variante do Problema do Caixeiro Viajante. O algoritmo proposto utiliza uma formulao de particionamento de conjuntos e novas ideias para melhorar o desempenho da relaxao de caminho conhecida como ng-path. Essas novas ideias no so baseadas em nenhuma hiptese forte em relao ao PLM, tendo o potencial de serem aplicadas em outros problemas. Experimentos computacionais mostram que o algoritmo proposto supera o estado da arte, sendo capaz de resolver vrias instncias nunca antes resolvidas. Palavras-chave: Particionamento de Conjuntos, Gerao de Colunas, Cortes de posto 1, Combinatria Polidrica, Roteamento, ng-paths.  S]  =MDK h|6]h| h|5\ ST] rs$a$;0P:p'/ =!n"n#n$n% Dpn  666666666666666 666666666666666666666666666 6666666666 666666666666 6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~$OJPJQJ^J_HmHnHsHtHN`N 'Normal*$1$ CJ^J_HaJmH nHsH tHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List JJ '0Heading $xCJOJQJ^JaJ88 '0 Text Body d $/$ '0List<""< '0Caption  $xx6]*2* '0Index $PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]   L<:MdWh|' @ @@UnknownG*Ax Times New Roman5Symbol3" Ariali xP!Liberation SerifTimes New RomanODroid Sans Fallback9FreeSansS& xP!Liberation SansArialACambria Math" b b qnn0$P '!xxTtulo HelioHelioOh+'0x  4 @ LX`hpTtulo HelioNormal_WordconvHelio2Microsoft Office Outlook@Ik@Ub@"c ՜.+,0 hp|   Ttulo Title  !#$%&'(),Root Entry F n"c.1Table WordDocumentYSummaryInformation(DocumentSummaryInformation8"CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q