@misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Provably Good Solutions for Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8155}, number = {04-40}, year = {2004}, abstract = {In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.}, language = {en} } @misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, year = {2004}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} } @misc{KaibelPeinhardtPfetsch2006, author = {Kaibel, Volker and Peinhardt, Matthias and Pfetsch, Marc}, title = {Orbitopal Fixing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9422}, number = {06-48}, year = {2006}, abstract = {The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.}, language = {en} } @misc{KaibelPfetsch2006, author = {Kaibel, Volker and Pfetsch, Marc}, title = {Packing and Partitioning Orbitopes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9104}, number = {06-17}, year = {2006}, abstract = {We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time.}, language = {en} } @misc{FroylandKochMegowetal.2006, author = {Froyland, Gary and Koch, Thorsten and Megow, Nicole and Duane, Emily and Wren, Howard}, title = {Optimizing the Landside Operation of a Container Terminal}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9004}, number = {06-06}, year = {2006}, abstract = {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.}, language = {en} } @misc{Koch2005, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8845}, number = {05-51}, year = {2005}, abstract = {Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58.}, language = {en} } @misc{MartinWeismantel1998, author = {Martin, Alexander and Weismantel, Robert}, title = {Conjunctive Cuts for Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3618}, number = {SC-98-18}, year = {1998}, abstract = {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.}, language = {en} } @misc{BrunsGubeladzeHenketal.1998, author = {Bruns, Winfried and Gubeladze, Joseph and Henk, Martin and Martin, Alexander and Weismantel, Robert}, title = {A counterexample to an integer analogue of Caratheodorys theorem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3718}, number = {SC-98-28}, year = {1998}, abstract = {For \$n\geq 6\$ we provide a counterexample to the conjecture that every integral vector of a \$n\$-dimensional integral polyhedral pointed cone \$C\$ can be written as a nonnegative integral combination of at most \$n\$ elements of the Hilbert basis of \$C\$. In fact, we show that in general at least \$\lfloor 7/6 \cdot n \rfloor\$ elements of the Hilbert basis are needed.}, 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} } @misc{WitzigBerthold2019, author = {Witzig, Jakob and Berthold, Timo}, title = {Conflict-Free Learning for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-030-58942-4_34}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75338}, year = {2019}, abstract = {Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.}, language = {en} } @misc{GroetschelHillerTuchscherer2007, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, year = {2007}, abstract = {In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.}, language = {en} } @misc{BertholdGamrathSalvagnin2019, author = {Berthold, Timo and Gamrath, Gerald and Salvagnin, Domenico}, title = {Exploiting Dual Degeneracy in Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73028}, year = {2019}, abstract = {Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 \% on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 \% on average.}, language = {en} } @misc{WitzigBertholdHeinz2019, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Computational Aspects of Infeasibility Analysis in Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74962}, year = {2019}, abstract = {The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.}, language = {en} } @misc{KosterZymolka2000, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6047}, number = {00-36}, year = {2000}, abstract = {In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.}, language = {en} } @misc{KochMartinVoss2000, author = {Koch, Thorsten and Martin, Alexander and Voß, Stefan}, title = {SteinLib: An Updated Library on Steiner Tree Problems in Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6056}, number = {00-37}, year = {2000}, abstract = {In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances.}, language = {en} } @misc{KosterZymolka2003, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Polyhedral Investigations on Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7324}, number = {03-10}, year = {2003}, abstract = {Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.}, language = {en} } @misc{EisenblaetterKosterWallbaumetal.2002, author = {Eisenbl{\"a}tter, Andreas and Koster, Arie M.C.A. and Wallbaum, Randolf and Wess{\"a}ly, Roland}, title = {Load Balancing in Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7179}, number = {02-50}, year = {2002}, abstract = {Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.}, language = {en} } @misc{ZymolkaKosterWessaely2002, author = {Zymolka, Adrian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {Transparent optical network design with sparse wavelength conversion}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7017}, number = {02-34}, year = {2002}, abstract = {We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, year = {1998}, abstract = {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.}, language = {en} } @misc{AscheuerFischettiGroetschel1999, author = {Ascheuer, Norbert and Fischetti, Matteo and Gr{\"o}tschel, Martin}, title = {Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4191}, number = {SC-99-31}, year = {1999}, abstract = {Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions.}, language = {en} } @misc{MarchandMartinWeismanteletal.1999, author = {Marchand, Hugues and Martin, Alexander and Weismantel, Robert and Wolsey, Laurence}, title = {Cutting Planes in Integer and Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4339}, number = {SC-99-44}, year = {1999}, abstract = {This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.}, language = {en} } @misc{Helmberg1999, author = {Helmberg, Christoph}, title = {The m-Cost ATSP}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4374}, number = {SC-99-48}, year = {1999}, abstract = {Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node \$i\$ to node \$j\$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for \$m\ge 3\$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for \$m\ge 2\$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for \$m\ge 2\$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.}, language = {en} } @misc{BorndoerferLoebelWeider2004, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, year = {2004}, abstract = {This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.}, language = {en} } @misc{Groetschel1999, author = {Gr{\"o}tschel, Martin}, title = {My Favorite Theorem: Characterizations of Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4053}, number = {SC-99-17}, year = {1999}, abstract = {This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.}, language = {en} }