Dissertation (Metadaten)
Titel:Reducing mixed-integer to zero-one programs
Autor:Marcel Büther
Fakultät:Wirtschafts- und Sozialwissenschaftliche Fakultät
DDC Sachgebiet:330 Wirtschaft
Datum der mdl. Prüfung:14.07.2008
Referent(in):Prof. Dr. Andreas Drexl
Korreferent(en) Korreferentin:PD Dr. Uwe Jensen
Beschreibung:During the last decades, there has been a lot of success in the operational research community in the development of efficient algorithms for several integer optimization programs. Unfortunately, these programs are often not sufficient to represent the environment and thus real-life applications appropriate. This challenge can only be solved by using additionally continuous variables. Then, for their optimization it is of course possible to develop always a new algorithm for each of them. But obviously, this is very expensive: On the one hand, based on the endless number of potentially occurring programs and on the other hand, based on the complexity of the problems themselves. Thus, instead of always developing a new approach, the basic idea of this thesis was to check, if it is admirable to reduce several mixed integer programs to integer ones for which approved approaches are available and that can be applied straightforward then.
Schlagworte:mixed-integer programming, reformulation, binary representation, binary knapsack problem, elastic generalized assignment problem, beam search, Lagrangian relaxation, local search