h1

000706540 001__ 706540
000706540 005__ 20230408005331.0
000706540 0247_ $$2HBZ$$aHT019492898
000706540 0247_ $$2Laufende Nummer$$a36585
000706540 0247_ $$2datacite_doi$$a10.18154/RWTH-2017-08718
000706540 037__ $$aRWTH-2017-08718
000706540 041__ $$aEnglish
000706540 082__ $$a510
000706540 1001_ $$0P:(DE-82)127510$$aDahms, Florian H. W.$$b0
000706540 245__ $$aDecomposition of Integer Programs with Matchability Structure$$cvorgelegt von Diplom-Mathematiker Florian Herbert Werner Dahms$$honline
000706540 246_3 $$aDekomposition von Ganzzahligen Programmen mit Matching Struktur$$yGerman
000706540 260__ $$aAachen$$bLehrstuhl für Operations Research$$c2017
000706540 260__ $$c2016
000706540 300__ $$a1 Online-Ressource (xii, 179 Seiten) : Illustrationen, Diagramme
000706540 3367_ $$02$$2EndNote$$aThesis
000706540 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000706540 3367_ $$2BibTeX$$aPHDTHESIS
000706540 3367_ $$2DRIVER$$adoctoralThesis
000706540 3367_ $$2DataCite$$aOutput Types/Dissertation
000706540 3367_ $$2ORCID$$aDISSERTATION
000706540 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University 2017
000706540 502__ $$aDissertation, RWTH Aachen University, 2016$$bDissertation$$cRWTH Aachen University$$d2016$$gFak01$$o2016-11-25
000706540 5203_ $$aDie Dissertation beschäftigt sich mit kombinatorischen Optimierungsproblemen, denen eine Matching Struktur zugrunde liegt. Als Beispiele werden in der Arbeit die folgenden Probleme betrachtet: Das Curriculum basierte Stundenplanungsproblem, das Multiple Knapsack Problem, das List Coloring Problem, ein Machine Scheduling Problem, sowie ein spezielles Eisenbahn Rangierproblem.Es wird gezeigt, wie mithilfe des partiellen Transversal Polytops größere ganzzahlige Programme in kleine Teilprobleme zerlegt werden können. Diese Zerlegung kann als Benders' Dekomposition verstanden werden und ist generisch auf viele Probleme anwendbar. Die Theorie um die partiellen Transversale wird genutzt um den Dekompositionsalgorithmus effizienter und numerisch stabiler zu machen. Das Curriculum basierte Stundenplanungsproblem wird als Beispielanwendung für diese Algorithmen betrachtet. Hierbei wird unter anderem gezeigt, dass sich Stundenplanungsprobleme, bei denen das zugrunde liegende Matching ein bipartites Hypergraphenmatching ist, mithilfe der in der Dissertation entwickelten Algorithmen mit zufrieden stellender Geschwindigkeit lösen lassen.Für Optimierungsprobleme die mithilfe einer Dantzig-Wolfe Dekomposition zerlegt werden können wird gezeigt, dass die polyhedrale Theorie um die partiellen Transversale genutzt werden kann, um nicht identische Subprobleme zu aggregieren.$$lger
000706540 520__ $$aThe topic of the thesis are combinatorial optimization problems which have a matching problem as substructure. The following problems do have such a structure and are investigated in the thesis: the curriculum based time tabling problem, the multiple knapsack problem, the list coloring problem, a machine scheduling problem and a special railway shunting problem.It is shown, how the partial transversal polytope can be helpful in decomposing large integer programs into smaller sub problems. This decomposition can be seen as a Benders' decomposition. The theory of partial transversals is used to make the algorithms more efficient and numerically stable. The curriculum based time tabling problem is taken as an example for these algorithms. Here it is shown that even if the matching problem is based on hyper graph matchings, they can be solved within an acceptable time span using the algorithms of the thesis.For optimization problems which can be decomposed using Dantzig-Wolfe decomposition, the theory of the partial transversal is used to show that even non identical subproblems can be aggregated.$$leng
000706540 588__ $$aDataset connected to Lobid/HBZ
000706540 591__ $$aGermany
000706540 653_7 $$aDantzig-Wolfe Decomposition
000706540 653_7 $$aKoenig-Hall Theorem
000706540 653_7 $$abenders decomposition
000706540 653_7 $$ainteger programming
000706540 653_7 $$amatchings
000706540 653_7 $$apolyhedra
000706540 653_7 $$atraversals
000706540 7001_ $$0P:(DE-82)IDM00097$$aKoster, Arie Marinus$$b1$$eThesis advisor
000706540 7001_ $$0P:(DE-82)709314$$aKrumke, Sven O.$$b2$$eThesis advisor
000706540 7001_ $$0P:(DE-82)IDM00416$$aLübbecke, Marco$$b3$$eThesis advisor
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.pdf$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540_source.zip$$yRestricted
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.gif?subformat=icon$$xicon$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.jpg?subformat=icon-1440$$xicon-1440$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.jpg?subformat=icon-640$$xicon-640$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000706540 8564_ $$uhttps://publications.rwth-aachen.de/record/706540/files/706540.pdf?subformat=pdfa$$xpdfa$$yOpenAccess
000706540 909CO $$ooai:publications.rwth-aachen.de:706540$$pVDB$$pdnbdelivery$$pdriver$$popen_access$$popenaire
000706540 9141_ $$y2016
000706540 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000706540 9201_ $$0I:(DE-82)113320_20140620$$k113320$$lLehr- und Forschungsgebiet Mathematik (Diskrete Optimierung)$$x0
000706540 9201_ $$0I:(DE-82)110000_20140620$$k110000$$lFachgruppe Mathematik$$x1
000706540 9201_ $$0I:(DE-82)813310_20140620$$k813310$$lLehrstuhl für Operations Research$$x2
000706540 961__ $$c2017-11-22T15:56:11.730441$$x2017-10-10T08:18:52.904037$$z2017-11-22T15:56:11.730441
000706540 9801_ $$aFullTexts
000706540 980__ $$aI:(DE-82)110000_20140620
000706540 980__ $$aI:(DE-82)113320_20140620
000706540 980__ $$aI:(DE-82)813310_20140620
000706540 980__ $$aUNRESTRICTED
000706540 980__ $$aVDB
000706540 980__ $$aphd