TY - CHAP A1 - Kunt, Tim T1 - Solving the n-Queens Problem in Higher Dimensions T2 - Operations Research Proceedings 2024. OR 2024 N2 - How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15–70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. KW - Integer Programming KW - Maximum Independent Set KW - n-Queens Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-92575-7_29 SP - 205 EP - 211 ER - TY - THES A1 - Kunt, Tim T1 - The n-Queens Problem in Higher Dimensions N2 - How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We provide a comprehensive overview of theoretical results, bounds, solution methods, and the interconnectivity of the problem within topics of discrete optimization and combinatorics. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15-70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. We conclude with preliminary results on the number and density of the solutions. T3 - ZIB-Report - 24-05 KW - Integer Programming KW - Maximum Independent Set KW - n-Queens Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-96468 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways N2 - In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach. T3 - ZIB-Report - 12-21 KW - Vehicle Routing Problem KW - Duty Rostering KW - Integer Programming KW - Operations Research Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15498 SN - 1438-0064 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 - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways N2 - This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany. T3 - ZIB-Report - 11-42 KW - Toll Enforcement KW - Vehicle Routing Problem KW - Duty Roster Planning KW - Integer Programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14299 SN - 1438-0064 ER - TY - GEN A1 - Dittel, Agnes A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Polyhedral Aspects of Self-Avoiding Walks N2 - In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach. T3 - ZIB-Report - 11-11 KW - Polyhedral Combinatorics KW - Integer Programming KW - Self-Avoiding Path KW - Protein Folding Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12576 ER - TY - THES A1 - Achterberg, Tobias T1 - Constraint Integer Programming N2 - This thesis introduces the novel paradigm of "constraint integer programming" (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method. N2 - Diese Arbeit stellt einen integrierten Ansatz aus "Constraint Programming" (CP) und Gemischt-Ganzzahliger Programmierung ("Mixed Integer Programming", MIP) vor, den wir "Constraint Integer Programming" (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die "Domain Propagation", die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Ein weiterer Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der "Electronic Design Automation" darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode. KW - Ganzzahlige Programmierung KW - Constraint Programmierung KW - SAT KW - Chip-Verifikation KW - Mathematische Programmierung KW - Integer Programming KW - Constraint Programming KW - SAT KW - Chip Verification KW - Mathematical Programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11129 ER - TY - GEN A1 - Bley, Andreas T1 - An Integer Programming Algorithm for Routing Optimization in IP Networks N2 - Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm. T3 - ZIB-Report - 08-30 KW - Shortest Path Routing KW - Integer Programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10814 SN - 1438-0064 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 - 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 - 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 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Column Generation Approach to Airline Crew Scheduling N2 - The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH. T3 - ZIB-Report - 05-37 KW - Integer Programming KW - Airline Crew Scheduling KW - Branch and Generate Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8713 ER - TY - GEN A1 - Kröller, Alexander A1 - Wessäly, Roland T1 - Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks N2 - We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved. T3 - ZIB-Report - 03-49 KW - Survivable Network Design KW - Integer Programming KW - Hardware Configuration KW - Routing KW - Network Models KW - Network Planning KW - Resource Allocation KW - Surviva Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7714 ER - TY - GEN A1 - Geerdes, Hans-Florian A1 - Karl, Holger T1 - The Potential of Relaying in Cellular Networks N2 - Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable. T3 - ZIB-Report - 03-42 KW - Wireless ad hoc networks KW - Resource Allocation KW - Integer Programming KW - Routing KW - Scheduling KW - Operation Research KW - Network Performance Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7641 ER - TY - GEN A1 - Geerdes, Hans-Florian T1 - Assessing Capacity Improvements by Relaying in Cellular Networks N2 - Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\% on the average. T3 - ZIB-Report - 03-43 KW - Wireless ad hoc networks KW - Resource Allocation KW - Integer Programming KW - Routing KW - Scheduling KW - Operation Research KW - Network Performance Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7651 ER - 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 - Koster, Arie M.C.A. T1 - Re-Optimization of Signaling Transfer Points N2 - In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits. T3 - ZIB-Report - 00-18 KW - Telecommunications KW - Modeling KW - Integer Programming Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5863 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Conjunctive Cuts for Integer Programs N2 - This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view. T3 - ZIB-Report - SC-98-18 KW - Polyhedral Combinatorics KW - Integer Programming KW - Separation Algorithm Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3618 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - The Orientation Model for Frequency Assignment Problems N2 - Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem. T3 - ZIB-Report - TR-98-01 KW - Minimum-Cost Flow Problems KW - Cellular Radio Telephone Systems KW - Frequency Assignment Problem KW - Integer Programming Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5627 ER -