TY - JOUR A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming JF - Journal of Computational Mathematics N2 - The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. Y1 - 2019 U6 - https://doi.org/10.4208/jcm.1905-m2019-0055 VL - 37 SP - 866 EP - 888 ER - TY - JOUR A1 - Harrod, Steven A1 - Schlechte, Thomas T1 - A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations JF - Transportation Research Part E: Logistics and Transportation Review N2 - Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, RCHF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and RCHF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall. Y1 - 2013 U6 - https://doi.org/10.1016/j.tre.2013.04.003 VL - 54 SP - 50 EP - 66 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - Models for Fare Planning in Public Transport JF - Discrete Applied Mathematics Y1 - 2012 U6 - https://doi.org/10.1016/j.dam.2012.02.027 VL - 160 IS - 18 SP - 2591 EP - 2605 ER - TY - JOUR A1 - Dür, Mirjam A1 - Fügenschuh, Armin A1 - Huhn, Petra A1 - Klamroth, Kathrin A1 - Saliba, Sleman A1 - Tammer, Christiane T1 - EURO Summer Institute 2006 in Wittenberg JF - OR News Y1 - 2006 VL - 28 SP - 71 EP - 72 ER - TY - JOUR A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - On cut-based inequalities for capacitated network design polyhedra JF - Networks Y1 - 2011 UR - http://onlinelibrary.wiley.com/doi/10.1002/net.20395/abstract VL - 57 IS - 2 SP - 141 EP - 156 ER - TY - JOUR A1 - Frank, A. A1 - Chi Lau, L. A1 - Szabó, Jácint T1 - A note on degree-constrained subgraphs JF - Discrete Mathematics Y1 - 2008 VL - 308 IS - 12 SP - 2647 EP - 2648 PB - Elsevier ER - TY - JOUR A1 - Hoppmann-Baum, Kai T1 - On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows JF - Networks N2 - Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time. Y1 - 2021 U6 - https://doi.org/10.1002/net.22060 ER - TY - JOUR A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann-Baum, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas JF - Optimization and Engineering N2 - Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s11081-020-09559-y VL - 22 SP - 687 EP - 734 PB - Springer Nature ET - 2 ER - TY - JOUR A1 - Rössig, Ansgar A1 - Petkovic, Milena T1 - Advances in Verification of ReLU Neural Networks JF - Journal of Global Optimization N2 - We consider the problem of verifying linear properties of neural networks. Despite their success in many classification and prediction tasks, neural networks may return unexpected results for certain inputs. This is highly problematic with respect to the application of neural networks for safety-critical tasks, e.g. in autonomous driving. We provide an overview of algorithmic approaches that aim to provide formal guarantees on the behavior of neural networks. Moreover, we present new theoretical results with respect to the approximation of ReLU neural networks. On the other hand, we implement a solver for verification of ReLU neural networks which combines mixed integer programming (MIP) with specialized branching and approximation techniques. To evaluate its performance, we conduct an extensive computational study. For that we use test instances based on the ACAS Xu System and the MNIST handwritten digit data set. Our solver is publicly available and able to solve the verification problem for instances which do not have independent bounds for each input neuron. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00949-1 PB - Springer ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Linear Programming using Limited-Precision Oracles JF - Mathematical Programming N2 - Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-019-01444-6 VL - 183 IS - 1-2 SP - 525 EP - 554 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of cycle inequalities in periodic timetabling JF - Discrete Optimization N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. Y1 - 2020 U6 - https://doi.org/10.1016/j.disopt.2019.100552 IS - 35 SP - 100552 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Lindner, Niels A1 - Roth, Sarah T1 - A Concurrent Approach to the Periodic Event Scheduling Problem JF - Journal of Rail Transport Planning & Management N2 - We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib. Y1 - 2020 U6 - https://doi.org/10.1016/j.jrtpm.2019.100175 SN - 2210-9706 IS - 15 SP - 100175 ER - TY - JOUR A1 - Gotzes, Uwe T1 - Ein neuer Ansatz zur Optimierung des Bilanzausgleichs in einem Gasmarktgebiet JF - Zeitschrift für Energiewirtschaft N2 - Im BDEW/VKU/GEODE-Leitfaden Krisenvorsorge Gas ist zu lesen, dass als oberster Grundsatz zur Vermeidung von Versorgungsengpässen in Gasversorgungssystemen gilt, möglichst laufend einen Bilanzausgleich in allen Teilen des Netzes zu erreichen. Wir entwickeln Modelle zur Optimierung des laufenden Bilanzausgleichs. Als Gasversorgungssystem betrachten wir modellhaft die Fernleitungsnetze eines Marktgebiets. Als Teile des Gasversorgungssystems fassen wir vereinfachend die jeweiligen Netze der Fernleitungsnetzbetreiber auf. Die Optimierung erfolgt in zwei Schritten. Im ersten Schritt wird der optimale Einsatz netzbezogener Maßnahmen ermittelt. Beispiele für netzbezogene Maßnahmen sind die Nutzung von Netzpuffer und Mengenverlagerungen mit anderen Infrastrukturbetreibern. Falls sich die Bilanzen durch netzbezogene Maßnahmen nicht vollständig ausgleichen lassen, werden Fehlmengen angesetzt, die so gleichmäßig wie möglich auf die Teile des Netzes verteilt werden. Im zweiten Schritt werden die verbliebenen Fehlmengen, welche in der Regel durch marktbezogene Maßnahmen bereinigt werden, regulierungskonform auf möglichst große Teile des Gasversorgungssystems verteilt. Im Ergebnis erhalten wir ein transparentes, gerechtes, flexibel parametrier- und erweiterbares Verfahren, welches zyklisch im Dispatchingprozess eingesetzt werden kann, um die Integrität der Netze zu unterstützen. Dies wird an Beispielen verdeutlicht. Y1 - 2019 U6 - https://doi.org/10.1007/s12398-019-00257-6 ER - TY - JOUR A1 - Pulaj, Jonad T1 - Cutting planes for families implying Frankl's conjecture JF - Mathematics of Computation N2 - We find previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen's Theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of Morris from 2006. Y1 - 2019 U6 - https://doi.org/10.1090/mcom/3461 ER - TY - JOUR A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Fiand, Frederik A1 - Cao, Karl-Kiên A1 - Gils, Hans Christian A1 - Wetzel, Manuel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Khabi, Dmitry T1 - BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele JF - OR-News : das Magazin der GOR Y1 - 2019 IS - 66 SP - 6 EP - 8 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of handouts for rolling stock rotations JF - Journal of Rail Transport Planning & Management N2 - A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach. Y1 - 2019 U6 - https://doi.org/10.1016/j.jrtpm.2019.02.001 IS - 10 SP - 1 EP - 8 ER - TY - JOUR A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms JF - SIAM Journal on Optimization N2 - One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly. Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72767 VL - 30 IS - 2 SP - 1339 EP - 1365 ER - TY - JOUR A1 - Bernal, David E. A1 - Vigerske, Stefan A1 - Trespalacios, Francisco A1 - Grossmann, Ignacio E. T1 - Improving the performance of DICOPT in convex MINLP problems using a feasibility pump JF - Optimization Methods and Software N2 - The solver DICOPT is based on an outer-approximation algorithm used for solving mixed- integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, there are certain problems that are diffcult to solve with this algorithm. One of these problems is when the nonlinear constraints are so restrictive that the nonlinear subproblems produced by the algorithm are infeasible. This problem is addressed in this paper with a feasibility pump algorithm, which modifies the objective function in order to efficiently find feasible solutions. It has been implemented as a preprocessing algorithm for DICOPT. Computational comparisons with previous versions of DICOPT and other MINLP solvers on a set of convex MINLPs demonstrate the effectiveness of the proposed algorithm in terms of solution quality and solving time. Y1 - 2017 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Pauwels, Edouard T1 - An unexpected connection between Bayes A-optimal designs and the group lasso JF - Statistical Papers N2 - We show that the A-optimal design optimization problem over m design points in R^n is equivalent to minimizing a quadratic function plus a group lasso sparsity inducing term over n x m real matrices. This observation allows to describe several new algorithms for A-optimal design based on splitting and block coordinate decomposition. These techniques are well known and proved powerful to treat large scale problems in machine learning and signal processing communities. The proposed algorithms come with rigorous convergence guarantees and convergence rate estimate stemming from the optimization literature. Performances are illustrated on synthetic benchmarks and compared to existing methods for solving the optimal design problem. Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73059 VL - 60 IS - 2 SP - 215 EP - 234 ER - TY - JOUR A1 - Chen, Ying A1 - Chua, Wee Song A1 - Koch, Thorsten T1 - Forecasting day-ahead high-resolution natural-gas demand and supply in Germany JF - Applied Energy N2 - Forecasting natural gas demand and supply is essential for an efficient operation of the German gas distribution system and a basis for the operational decisions of the transmission system operators. The German gas market is moving towards more short-term planning, in particular, day-ahead contracts. This increases the difficulty that the operators in the dispatching centre are facing, as well as the necessity of accurate forecasts. This paper presents a novel predictive model that provides day-ahead forecasts of the high resolution gas flow by developing a Functional AutoRegressive model with eXogenous variables (FARX). The predictive model allows the dynamic patterns of hourly gas flows to be described in a wide range of historical profiles, while also taking the relevant determinants data into account. By taking into account a richer set of information, FARX provides stronger performance in real data analysis, with both accuracy and high computational efficiency. Compared to several alternative models in out-of-sample forecasts, the proposed model can improve forecast accuracy by at least 12% and up to 5-fold for one node, 3% to 2-fold and 2-fold to 4-fold for the other two nodes. The results show that lagged 1-day gas flow and nominations are important predictors, and with their presence in the forecast model, temperature becomes insignificant for short-term predictions. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2018.06.137 IS - Volume 228 SP - 1091 EP - 1110 ER - TY - JOUR A1 - Berthold, Timo A1 - Farmer, James A1 - Heinz, Stefan A1 - Perregaard, Michael T1 - Parallelization of the FICO Xpress Optimizer JF - Optimization Methods and Software N2 - Computing hardware has mostly thrashed out the physical limits for speeding up individual computing cores. Consequently, the main line of progress for new hardware is growing the number of computing cores within a single CPU. This makes the study of efficient parallelization schemes for computation-intensive algorithms more and more important. A natural precondition to achieving reasonable speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for software that is used in industrial applications. In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. MIP solvers like Xpress are expected to be deterministic. This inevitably results in synchronization latencies which render the goal of a satisfying workload a challenge in itself. We address this challenge by following a partial information approach and separating the concepts of simultaneous tasks and independent threads from each other. Our computational results indicate that this leads to a much higher CPU workload and thereby to an improved, almost linear, scaling on modern high-performance CPUs. As an added value, the solution path that Xpress takes is not only deterministic in a fixed environment, but also, to a certain extent, thread-independent. This paper is an extended version of Berthold et al. [Parallelization of the FICO Xpress-Optimizer, in Mathematical Software – ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommere, eds., Springer International Publishing, Berlin, 2016, pp. 251–258] containing more detailed technical descriptions, illustrative examples and updated computational results. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1333612 VL - 33 IS - 3 SP - 518 EP - 529 ER - TY - JOUR A1 - Tawfik, Christine A1 - Limbourg, Sabine T1 - A Bilevel Model for Network Design and Pricing Based on a Level-of-Service Assessment JF - Transportation Science N2 - Within a wide view to stimulate intermodal transport, this paper is devoted to the examination of the intrinsically related problems of designing freight carrying services and determining their associated prices as observed by the shipper firms. A path-based multicommodity formulation is developed for a medium-term planning horizon, from the perspective of an intermodal operator. In the quest of incorporating nonprice attributes, two approaches are proposed to depict a realistic assessment of the service quality. First, frequency delay constraints are added to the upper level problem. Second, based on a random utility model, behavioural concepts are integrated in the expression of the lower level as a logistics costs minimization problem. Exact tests are invoked on real-world instances, demonstrating the capability of the presented approaches of reaching reasonable results within acceptable computation times and optimality gaps. The broader level-of-service perspective imposes additional costs on the service providers, although to a lesser extent on long-distance freight corridors, as indicated by the computed market share and net profit. Further experiments are conducted to test the impact of certain transport management instruments (e.g. subsidies and service capacities) on the modal split, as well as to assess the intermodality’s future based on a scenario analysis methodology. Y1 - 2019 U6 - https://doi.org/10.1287/trsc.2019.0906 VL - 53 IS - 6 SP - 1609 EP - 1626 PB - Informs CY - Transportation Science ER - TY - JOUR A1 - Munguia, Lluis-Miquel A1 - Oxberry, Geoffrey A1 - Rajan, Deepak A1 - Shinano, Yuji T1 - Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs JF - Computational Optimization and Applications N2 - PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores. Y1 - 2019 U6 - https://doi.org/10.1007/s10589-019-00074-0 ER - TY - JOUR A1 - Achterberg, Tobias A1 - Bixby, Robert E. A1 - Gu, Zonghao A1 - Rothberg, Edward A1 - Weninger, Dieter T1 - Presolve Reductions in Mixed Integer Programming JF - INFORMS Journal on Computing N2 - Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature. Y1 - 2019 ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices JF - Parallel Computing N2 - • Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances. Y1 - 2022 U6 - https://doi.org/10.1016/j.parco.2021.102874 VL - 109 SP - 102874 ER - TY - JOUR A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming JF - Mathematical Programming Computation N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. Y1 - 2018 ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Hijazi, Hassan A1 - Coffrin, Carleton T1 - Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching JF - INFORMS Journal on Computing N2 - This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions and presents a strengthened version of the Convex Quadratic relaxation of the Optimal Transmission Switching problem. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent convex relaxations introduced for the Optimal Transmission Switching problem in Power Systems. Using the proposed improvements, along with bound propagation, on 23 medium-size test cases in the PGLib benchmark library with a relaxation gap of more than 1%, we reduce the gap to less than 1% on 5 instances. The tightened model has promising computational results when compared to state-of-the-art formulations. Y1 - 2019 U6 - https://doi.org/https://doi.org/10.1287/ijoc.2019.0900 VL - 32 IS - 3 SP - 682 EP - 696 PB - INFORMS Institute for Operations Research and the Management Sciences CY - 5521 Research Park Drive, Suite 200, Catonsville, MD 21228 USA ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-driven fix-and-propagate heuristics for mixed integer programming JF - Mathematical Programming Computation N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time. Y1 - 2019 U6 - https://doi.org/10.1007/s12532-019-00159-1 VL - 11 IS - 4 SP - 675 EP - 702 PB - Springer CY - Berlin Heidelberg ER - TY - JOUR A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Conflict-Driven Heuristics for Mixed Integer Programming JF - INFORMS Journal on Computing N2 - Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l. Y1 - 2020 U6 - https://doi.org/10.1287/ijoc.2020.0973 VL - 33 IS - 2 SP - 706 EP - 720 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Gamrath, Gerald A1 - Achterberg, Tobias A1 - Bastubbe, Michael A1 - Berthold, Timo A1 - Christophel, Philipp M. A1 - Jarck, Kati A1 - Koch, Thorsten A1 - Linderoth, Jeff A1 - Lübbecke, Marco A1 - Mittelmann, Hans A1 - Ozyurt, Derya A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Shinano, Yuji T1 - MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library JF - Mathematical Programming Computation N2 - We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data. Y1 - 2021 U6 - https://doi.org/10.1007/s12532-020-00194-3 VL - 13 IS - 3 SP - 443 EP - 490 ER - TY - JOUR A1 - Sun, Yahui A1 - Rehfeldt, Daniel A1 - Brazil, Marcus A1 - Thomas, Doreen A1 - Halgamuge, Saman T1 - A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks JF - IEEE/ACM Transactions on Networking Y1 - 2020 U6 - https://doi.org/10.1109/TNET.2020.2971770 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Hoen, Alexander T1 - PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support JF - INFORMS Journal on Computing N2 - Presolving has become an essential component of modern mixed integer program (MIP) solvers, both in terms of computational performance and numerical robustness. In this paper, we present PaPILO, a new C++ header-only library that provides a large set of presolving routines for MIP and linear programming problems from the literature. The creation of PaPILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. PaPILO’s parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, PaPILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel’s Threading Building Blocks library aids PaPILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO’s capabilities and insights into important design choices. Y1 - 2023 U6 - https://doi.org/10.1287/ijoc.2022.0171 VL - 35 IS - 6 SP - 1329 EP - 1341 ER - TY - JOUR A1 - Chen, Ying A1 - Xu, Xiuqin A1 - Koch, Thorsten T1 - Day-ahead high-resolution forecasting of natural gas demand and supply in Germany with a hybrid model JF - Applied Energy N2 - As the natural gas market is moving towards short-term planning, accurate and robust short-term forecasts of the demand and supply of natural gas is of fundamental importance for a stable energy supply, a natural gas control schedule, and transport operation on a daily basis. We propose a hybrid forecast model, Functional AutoRegressive and Convolutional Neural Network model, based on state-of-the-art statistical modeling and artificial neural networks. We conduct short-term forecasting of the hourly natural gas flows of 92 distribution nodes in the German high-pressure gas pipeline network, showing that the proposed model provides nice and stable accuracy for different types of nodes. It outperforms all the alternative models, with an improved relative accuracy up to twofold for plant nodes and up to fourfold for municipal nodes. For the border nodes with rather flat gas flows, it has an accuracy that is comparable to the best performing alternative model. KW - Natural gas flow forecasting KW - Neural network KW - Hybrid model KW - Functional autoregressive Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2019.114486 VL - 262 IS - 114486 ER - TY - JOUR A1 - Tesch, Alexander T1 - A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem JF - Journal of Scheduling N2 - We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997). Y1 - 2020 ER - TY - JOUR A1 - Streubel, Tom A1 - Tischendorf, Caren A1 - Griewank, Andreas T1 - Piecewise Polynomial Taylor Expansions - The Generalization of Faà di Bruno's Formula JF - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 N2 - We present an extension of Taylor's Theorem for the piecewise polynomial expansion of non-smooth evaluation procedures involving absolute value operations. Evaluation procedures are computer programs of mathematical functions in closed form expression and allow a different treatment of smooth operations or calls to the absolute value function. The well known classical Theorem of Taylor defines polynomial approximations of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential- or differential-algebraic equations, for the construction of solvers for continuous non-linear optimization of finite dimensional objective functions and for root solving of non-linear systems of equations. The long term goal is the stabilization and acceleration of already known methods and the derivation of new methods by incorporating piecewise polynomial Taylor expansions. The herein provided proof of the higher order approximation quality of the new generalized expansions is constructive and allows efficiently designed algorithms for the execution and computation of the piecewise polynomial expansions. As a demonstration towards the ultimate goal we will derive a prototype of a {\$}{\$}k{\$}{\$}k-step method on the basis of polynomial interpolation and the proposed generalized expansions. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-55240-4_3 IS - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 SP - 63 EP - 82 PB - Springer International Publishing ER - TY - JOUR A1 - Duarte, Belmiro A1 - Sagnol, Guillaume T1 - Approximate and exact optimal designs for 2^k factorial experiments for generalized linear models via second order cone programming JF - Statistical Papers N2 - Model-based optimal designs of experiments (M-bODE) for nonlinear models are typically hard to compute. The literature on the computation of M-bODE for nonlinear models when the covariates are categorical variables, i.e. factorial experiments, is scarce. We propose second order cone programming (SOCP) and Mixed Integer Second Order Programming (MISOCP) formulations to find, respectively, approximate and exact A- and D-optimal designs for 2𝑘 factorial experiments for Generalized Linear Models (GLMs). First, locally optimal (approximate and exact) designs for GLMs are addressed using the formulation of Sagnol (J Stat Plan Inference 141(5):1684–1708, 2011). Next, we consider the scenario where the parameters are uncertain, and new formulations are proposed to find Bayesian optimal designs using the A- and log det D-optimality criteria. A quasi Monte-Carlo sampling procedure based on the Hammersley sequence is used for computing the expectation in the parametric region of interest. We demonstrate the application of the algorithm with the logistic, probit and complementary log–log models and consider full and fractional factorial designs. Y1 - 2020 U6 - https://doi.org/10.1007/s00362-018-01075-7 VL - 61 SP - 2737 EP - 2767 ER - TY - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions JF - Optimization Methods and Software N2 - Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains. Y1 - 2020 U6 - https://doi.org/10.1080/10556788.2020.1817448 PB - Taylor & Francis ER - TY - JOUR A1 - Ramin, Elham A1 - Bestuzheva, Ksenia A1 - Gargalo, Carina A1 - Ramin, Danial A1 - Schneider, Carina A1 - Ramin, Pedram A1 - Flores-Alsina, Xavier A1 - Andersen, Maj M. A1 - Gernaey, Krist V. T1 - Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya JF - Science of the Total Environment N2 - Industrial parks have a high potential for recycling and reusing resources such as water across companies by creating symbiosis networks. In this study, we introduce a mathematical optimization framework for the design of water network integration in industrial parks formulated as a large-scale standard mixed-integer non-linear programming (MINLP) problem. The novelty of our approach relies on i) developing a multi-level incremental optimization framework for water network synthesis, ii) including prior knowledge of demand growth and projected water scarcity to evaluate the significance of water-saving solutions, iii) incorporating a comprehensive formulation of water network synthesis problem including multiple pollutants and different treatment units and iv) performing a multi-objective optimization of the network including freshwater savings and relative cost of the network. The significance of the proposed optimization framework is illustrated by applying it to an existing industrial park in a water-scarce region in Kenya. Firstly, we illustrated the benefits of including prior knowledge to prevent an over-design of the network at the early stages. In the case study, we achieved a more flexible and expandable water network with 36% lower unit cost at the early stage and 15% lower unit cost at later stages for the overall maximum freshwater savings of 25%. Secondly, multi-objective analysis suggests an optimum freshwater savings of 14% to reduce the unit cost of network by half. Moreover, the significance of symbiosis networks is highlighted by showing that intra-company connections can only achieve a maximum freshwater savings of 17% with significantly higher unit cost (+45%). Finally, we showed that the values of symbiosis connectivity index in the Pareto front correspond to higher freshwater savings, indicating the significant role of the symbiosis network in the industrial park under study. This is the first study, where all the above elements have been taken into account simultaneously for the design of a water reuse network. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.scitotenv.2020.141706 VL - 751 ER - TY - JOUR A1 - Serrano, Felipe A1 - Schwarz, Robert A1 - Gleixner, Ambros T1 - On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm JF - Journal of Global Optimization N2 - Recently, Kronqvist et al. (J Global Optim 64(2):249–272, 2016) rediscovered the supporting hyperplane algorithm of Veinott (Oper Res 15(1):147–152, 1967) and demonstrated its computational benefits for solving convex mixed integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm (J Soc Ind Appl Math 8(4):703–712, 1960) applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by a class of general, not necessarily convex nor differentiable, functions. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00906-y VL - 78 SP - 161 EP - 179 ER - TY - JOUR A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Dynamic routing at different layers in IP-over-WDM networks – Maximizing energy savings JF - Optical Switching and Networking, Special Issue on Green Communications Y1 - 2011 UR - http://opus.kobv.de/zib/volltexte/2010/1230/ ER - TY - JOUR A1 - Schwartz, Stephan T1 - An overview of graph covering and partitioning JF - Discrete Mathematics N2 - While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1016/j.disc.2022.112884 VL - 345 IS - 8 ER - TY - JOUR A1 - Dell’Amico, M. A1 - Hadjidimitriou, Natalia Selini A1 - Koch, Thorsten A1 - Petkovic, Milena T1 - Forecasting Natural Gas Flows in Large Networks JF - Machine Learning, Optimization, and Big Data. MOD 2017. N2 - Natural gas is the cleanest fossil fuel since it emits the lowest amount of other remains after being burned. Over the years, natural gas usage has increased significantly. Accurate forecasting is crucial for maintaining gas supplies, transportation and network stability. This paper presents two methodologies to identify the optimal configuration o parameters of a Neural Network (NN) to forecast the next 24 h of gas flow for each node of a large gas network. In particular the first one applies a Design Of Experiments (DOE) to obtain a quick initial solution. An orthogonal design, consisting of 18 experiments selected among a total of 4.374 combinations of seven parameters (training algorithm, transfer function, regularization, learning rate, lags, and epochs), is used. The best result is selected as initial solution of an extended experiment for which the Simulated Annealing is run to find the optimal design among 89.100 possible combinations of parameters. The second technique is based on the application of Genetic Algorithm for the selection of the optimal parameters of a recurrent neural network for time series forecast. GA was applied with binary representation of potential solutions, where subsets of bits in the bit string represent different values for several parameters of the recurrent neural network. We tested these methods on three municipal nodes, using one year and half of hourly gas flow to train the network and 60 days for testing. Our results clearly show that the presented methodologies bring promising results in terms of optimal configuration of parameters and forecast error. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1007/978-3-319-72926-8_14 VL - Lecture Notes in Computer Science IS - vol 10710 SP - 158 EP - 171 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - The Cone of Flow Matrices: Approximation Hierarchies and Applications JF - Networks N2 - Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone generated by the matrices $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where $\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over $\mathcal{K}$. This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix $X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s. Then, we provide two convergent approximation hierarchies, one of them based on a completely positive representation of~K. We illustrate this approach by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities. Y1 - 2018 U6 - https://doi.org/10.1002/net.21820 VL - 72 IS - 1 SP - 128 EP - 150 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem JF - SIAM Journal on Optimization N2 - Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced. Y1 - 2019 U6 - https://doi.org/10.1137/17M1145963 VL - 29 IS - 1 SP - 369 EP - 398 PB - Society for Industrial and Applied Mathematics ER - TY - JOUR A1 - Peitz, Sebastian A1 - Gräler, Manuel A1 - Henke, Christian A1 - Hessel-von Molo, Mirko A1 - Dellnitz, Michael A1 - Trächtler, Ansgar T1 - Multiobjective Model Predictive Control of an Industrial Laundry JF - Procedia Technology N2 - In a wide range of applications, it is desirable to optimally control a system with respect to concurrent, potentially competing goals. This gives rise to a multiobjective optimal control problem where, instead of computing a single optimal solution, the set of optimal compromises, the so-called Pareto set, has to be approximated. When it is not possible to compute the entire control trajectory in advance, for instance due to uncertainties or unforeseeable events, model predictive control methods can be applied to control the system during operation in real time. In this article, we present an algorithm for the solution of multiobjective model predictive control problems. In an offline scenario, it can be used to compute the entire set of optimal compromises whereas in a real time scenario, one optimal compromise is computed according to an operator’s preference. The results are illustrated using the example of an industrial laundry. A logistics model of the laundry is developed and then utilized in the optimization routine. Results are presented for an offline as well as an online scenario Y1 - 2016 IS - 26 SP - 483 EP - 490 ER - TY - JOUR A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - Hall’s and Kőnig’s theorem in graphs and hypergraphs JF - Discrete Mathematics N2 - We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs. Y1 - 2018 U6 - https://doi.org/10.1016/j.disc.2018.06.013 VL - 341 IS - 10 SP - 2753 EP - 2761 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Nardin, Antonella A1 - Pulaj, Jonad T1 - Integrating LP-guided variable fixing with MIP heuristics in the robust design of hybrid wired-wireless FTTx access networks JF - Applied Soft Computing N2 - This study investigates how to model and solve the problem of optimally designing FTTx telecommunications access networks integrating wired and wireless technologies, while taking into account the uncertainty of wireless signal propagation. We propose an original robust optimization model for the related robust 3-architecture Connected Facility Location problem, which includes additional variables and constraints to model wireless signal coverage represented through signal-to-interference ratios. Since the resulting robust problem can prove very challenging even for a modern state-of-the art optimization solver, we propose to solve it by an original primal heuristic that combines a probabilistic variable fixing procedure, guided by peculiar Linear Programming relaxations, with a Mixed Integer Programming heuristic, based on an exact very large neighborhood search. A numerical study carried out on a set of realistic instances show that our heuristic can find solutions of much higher quality than a state-of-the-art solver. Y1 - 2017 U6 - https://doi.org/10.1016/j.asoc.2017.07.018 VL - 61 SP - 1074 EP - 1087 ER - TY - JOUR A1 - Furini, Fabio A1 - Traversi, Emiliano A1 - Belotti, Pietro A1 - Frangioni, Antonio A1 - Gleixner, Ambros A1 - Gould, Nick A1 - Liberti, Leo A1 - Lodi, Andrea A1 - Misener, Ruth A1 - Mittelmann, Hans A1 - Sahinidis, Nikolaos V. A1 - Vigerske, Stefan A1 - Wiegele, Angelika T1 - QPLIB: A Library of Quadratic Programming Instances JF - Mathematical Programming Computation N2 - This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very diverse class of problems, comprising sub-classes of problems ranging from trivial to undecidable. This diversity is reflected in the variety of solution methods for QP, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents. Y1 - 2019 U6 - https://doi.org/10.1007/s12532-018-0147-4 VL - 11 IS - 2 SP - 237 EP - 265 ER - TY - JOUR A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin A1 - Gottwald, Robert Lion A1 - Grösser, Stefan T1 - Using white-box nonlinear optimization methods in system dynamics policy improvement JF - System Dynamics Review N2 - We present a new strategy for the direct optimization of the values of policy functions. This approach is particularly well suited to model actors with a global perspective on the system and relies heavily on modern mathematical white-box optimization methods. We demonstrate our strategy on two classical models: market growth and World2. Each model is first transformed into an optimization problem by defining how the actor can influence the models' dynamics and by choosing objective functions to measure improvements. To improve comparability between different runs, we also introduce a comparison measure for possible interventions. We solve the optimization problems, discuss the resulting policies and compare them to the existing results from the literature. In particular, we present a run of the World2 model which significantly improves the published “towards a global equilibrium” run with equal cost of intervention. Y1 - 2017 U6 - https://doi.org/10.1002/sdr.1583 VL - 33 IS - 2 SP - 138 EP - 168 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Barner, Christoph A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Mathes A1 - Spies, Claudia A1 - Wernecke, Klaus T1 - Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations JF - European Journal of Operational Research N2 - The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations. Y1 - 2018 U6 - https://doi.org/10.1016/j.ejor.2018.05.022 VL - 271 IS - 2 SP - 420 EP - 435 ER -