ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (1747)
- Doctoral Thesis (10)
- Habilitation (10)
- Article (5)
- In Proceedings (1)
Has Fulltext
- yes (1773) (remove)
Keywords
- integer programming (33)
- mixed integer programming (32)
- optimal control (29)
- KOBV (28)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (24)
- Bibliotheksverbund (20)
- Mixed Integer Programming (20)
- Integer Programming (17)
- mixed-integer programming (14)
- column generation (13)
Institute
- ZIB Allgemein (905)
- Mathematical Optimization (428)
- Numerical Mathematics (195)
- Visual and Data-centric Computing (91)
- Visual Data Analysis (87)
- Mathematical Optimization Methods (71)
- Mathematics of Transportation and Logistics (65)
- Computational Medicine (62)
- Digital Data and Information for Society, Science, and Culture (55)
- Applied Algorithmic Intelligence Methods (48)
01-40
{\begin{rawhtml} <a href="http://dx.doi.org/10.1007/s10479-007-0178-0"> Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0</a> \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.
06-29
SC-98-08
We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems.
SC-95-04
Die Business Unit PC in Augsburg ist die zentrale Produktionsstätte der Siemens--Nixdorf Informationssysteme (SNI) AG für Personal Computer sowie für einige Periphärgeräte. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es für ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engpässe im Produktionsbetrieb darstellen. Das Management suchte nach Möglichkeiten, den Produktionsfluß zu verbessern, ohne teure technische Änderungen am System vornehmen zu müssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums für Informationstechnik (die ehemals an der Universität Augsburg ansässig war) analysierte, unterstützt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ansätze, die hier dargestellt werden sollen, sind teilweise schon in Grötschel [Grö92] angesprochen worden.
SC-94-14
{\def\NP{\hbox{$\cal N\kern-.1667em\cal P$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be $\NP$-hard in the strong sense. We show that the storage assignment problem is $\NP$-hard for {\sl bounded sizes and capacities}, even if the sizes have values $1$ and~$2$ and the capacities value~$2$ only, a case we encountered in practice. Moreover, we prove that no polynomial time $\epsilon$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}
15-20
Current characterization methods of the so-called Bulk Heterojunction (BHJ), which is the main material of Organic Photovoltaic (OPV) solar cells, are limited to the analysis of global fabrication parameters. This reduces the efficiency of the BHJ design process, since it misses critical information about the local performance bottlenecks in the morphology of the material. In this paper, we propose a novel framework that fills this gap through visual characterization and exploration of local structure-performance correlations. We also propose a formula that correlates the structural features with the performance bottlenecks. Since research into BHJ materials is highly multidisciplinary, our framework enables a visual feedback strategy that allows scientists to build intuition about the best choices of fabrication parameters. We evaluate the usefulness of our proposed system by obtaining new BHJ characterizations. Furthermore, we show that our approach could substantially reduce the turnaround time.
17-16
The structure of Bulk-Heterojunction (BHJ) materials, the main component of organic photovoltaic solar cells, is very complex, and the relationship between structure and performance is still largely an open question. Overall, there is a wide spectrum of fabrication configurations resulting in different BHJ morphologies and correspondingly different performances. Current state- of-the-art methods for assessing the performance of BHJ morphologies are either based on global quantification of morphological features or simply on visual inspection of the morphology based on experimental imaging. This makes finding optimal BHJ structures very challenging. Moreover, finding the optimal fabrication parameters to get an optimal structure is still an open question. In this paper, we propose a visual analysis framework to help answer these questions through comparative visualization and parameter space exploration for local morphology features. With our approach, we enable scientists to explore multivariate correlations between local features and performance indicators of BHJ morphologies. Our framework is built on shape-based clustering of local cubical regions of the morphology that we call patches. This enables correlating the features of clusters with intuition-based performance indicators computed from geometrical and topological features of charge paths.
04-19
Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.
05-19
Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal. In this paper we try to remedy this situation by generalizing the SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50\% in the geometric mean. However, the total solving time increased by 15\%. on infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90\%, thereby reducing the solving time by 60\%.
05-42
The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.