@misc{AchterbergKochMartin2005, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {MIPLIB 2003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8625}, number = {05-28}, year = {2005}, abstract = {This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach2004, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Optimization Models for Operative Planning in Drinking Water Networks}, doi = {10.1007/s11081-008-9040-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8237}, number = {04-48}, year = {2004}, abstract = {The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.}, language = {en} } @misc{OrlowskiWessaely2004, author = {Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {An Integer Programming Model for Multi-Layer Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8248}, number = {04-49}, year = {2004}, abstract = {We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.}, language = {en} } @misc{KroellerWessaely2003, author = {Kr{\"o}ller, Alexander and Wess{\"a}ly, Roland}, title = {Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7714}, number = {03-49}, year = {2003}, abstract = {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.}, language = {en} } @misc{BleyKochWessaely2004, author = {Bley, Andreas and Koch, Thorsten and Wess{\"a}ly, Roland}, title = {Large-scale hierarchical networks: How to compute an optimal architecture?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7799}, number = {04-04}, year = {2004}, abstract = {In this article, we present a mathematical model and an algorithm to support one of the central strategic planning decisions of network operators: How to organize a large number of locations into a hierarchical network? We propose a solution approach that is based on mixed-integer programming and Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved within 30 minutes to less than 1\\% off optimality.}, language = {en} } @misc{KochWessaely2004, author = {Koch, Thorsten and Wess{\"a}ly, Roland}, title = {Hierarchical Infrastructure Planning in Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8174}, number = {04-42}, year = {2004}, abstract = {In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur F{\"o}rderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.}, language = {en} } @misc{Achterberg2005, author = {Achterberg, Tobias}, title = {Conflict Analysis in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8537}, number = {05-19}, year = {2005}, abstract = {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\\%.}, language = {en} } @misc{AchterbergGroetschelKoch2006, author = {Achterberg, Tobias and Gr{\"o}tschel, Martin and Koch, Thorsten}, title = {Software for Teaching Modeling of Integer Programming Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9176}, number = {06-23}, year = {2006}, abstract = {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.}, language = {en} } @misc{BleyGroetschelWessaely1998, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3565}, number = {SC-98-13}, year = {1998}, abstract = {We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data.}, language = {en} } @misc{BertholdWitzig2020, author = {Berthold, Timo and Witzig, Jakob}, title = {Conflict Analysis for MINLP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78964}, year = {2020}, abstract = {The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.}, language = {en} }