TY - GEN A1 - Koch, Thorsten T1 - ZIMPL User Guide N2 - {\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver. T3 - ZIB-Report - 01-20 KW - LP KW - IP KW - Modelling Language KW - Integer Programming Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6466 ER - TY - GEN A1 - Kaibel, Volker A1 - Koch, Thorsten T1 - Mathematik für den Volkssport N2 - "`Volkssport Sudoku"' titelt der Stern in seiner Ausgabe vom 24. Mai2006. In der Tat traut sich derzeit kaum noch eine Zeitung, ohne Sudoku zu erscheinen. Die Begeisterung am Lösen dieser Zahlenrätsel offenbart eine unvermutete Freude am algorithmischen Arbeiten. Mathematisch kann man Sudokus als lineare diophantische Gleichungssysteme mit Nichtnegativitätsbedingungen formulieren. Solche ganzzahligen linearen Programme sind die wichtigsten Modellierungswerkzeuge in zahlreichen Anwendungsgebieten wie z.B. der Optimierung von Telekommunikations- und Verkehrsnetzen. Moderne Verfahren zur Lösung dieser Optimierungsprobleme sind durch Sudokus allerdings deutlich weniger zu beeindrucken als Zeitungsleser. T3 - ZIB-Report - 06-28 KW - Sudoku KW - Integer Programming KW - General Public Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9225 ER - TY - GEN A1 - Froyland, Gary A1 - Koch, Thorsten A1 - Megow, Nicole A1 - Duane, Emily A1 - Wren, Howard T1 - Optimizing the Landside Operation of a Container Terminal N2 - This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most~8\% above a lower bound on optimal RMG utilization. T3 - ZIB-Report - 06-06 KW - Integer Programming KW - Container Terminal KW - Intermediate Storage Area KW - Landside operation KW - Yard crane scheduling KW - Storage space allocation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9004 ER - TY - GEN A1 - Koch, Thorsten T1 - Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds N2 - Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58. T3 - ZIB-Report - 05-51 KW - Integer Programming KW - Sudoku KW - IP KW - MIP KW - Zimpl KW - Modelling language Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8845 ER - TY - GEN A1 - Achterberg, Tobias A1 - Grötschel, Martin A1 - Koch, Thorsten T1 - Software for Teaching Modeling of Integer Programming Problems N2 - Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive. T3 - ZIB-Report - 06-23 KW - Integer Programming KW - Modelling KW - MIP-Solver KW - Algebraic Modelling Languages KW - Teaching Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9176 ER - TY - GEN A1 - Hoang, Nam-Dung A1 - Koch, Thorsten T1 - Steiner Tree Packing Revisited N2 - The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality. T3 - ZIB-Report - 12-02 KW - Steiner tree packing KW - Integer Programming KW - grid graphs Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14625 SN - 1438-0064 ER -