@techreport{GnegelFuegenschuh2019, author = {Gnegel, Fabian and F{\"u}genschuh, Armin}, title = {An iterative graph expansion approach for the scheduling and routing of airplanes}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4806}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48069}, year = {2019}, abstract = {A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. The task of optimally scheduling the airplanes and tour groups belongs to the class of vehicle routing problems with pickup and delivery and time-windows. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in order to model this problem as a mixed integer linear program. Most of the benchmark problems however could not be solved within a time limit of three hours, which was overcome by formulating the problem for a simplified (time-free) graph and the use of an incumbent callback to check for feasibility in the original graph. While this approach led to very good results for instances, where few time-free solutions were infeasible for the original problem, some instances remained unsolved. In order to overcome this problem we derive two new exact formulations that include time as variables. Although these formulations by themselves are not better than the approach from the literature, they allow for an effective construction of graphs which can be interpreted as intermediate graphs between the graph of airports and the expanded graph with vertices for each visit. Using similar relaxation techniques to the time-free approach and constructing these graphs based on solutions of the relaxations guarantees that only critical airports are expanded. A computational study was performed in order to compare the new formulations to the methods from the literature. Within a time limit of 3 hours the new approach was able to find proven optimal solutions for all previously unsolved benchmark instances. Furthermore the average computation time of all benchmark instances was reduced by 90 percent.}, subject = {Mixed Integer Linear Programming; Operational Research; Vehicle Routing Problem; Time-Dependent Airplane Routing; Dynamic Graph Expansion; Routing; Mehrdepotproblem; Expandierender Graph}, language = {en} } @techreport{GnegelFuegenschuhHageletal.2019, author = {Gnegel, Fabian and F{\"u}genschuh, Armin and Hagel, Michael and Leyffer, Sven and Stiemer, Marcus}, title = {A solution framework for linear PDE-constrained mixed-integer problems}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5045}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50453}, year = {2019}, abstract = {We present a general numerical solution method for control problems with PDE-defined state variables over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs (and if necessary a linearization scheme) to derive constraints for a mixed-integer linear program (MILP) leads to systems that are too large to be solved with state-of-the-art solvers for MILPs, especially if we desire an accurate approximation of the state variables. Our framework comprises two techniques to mitigate the rise of computation times with increasing discretization level parameters: First, the linear system is solved for a basis of the control space in a preprocessing step. Second, certain constraints are just imposed on demand via the IBM ILOG CPLEX feature of a lazy constraint callback. These techniques are compared with an approach where the relations obtained by the discretization of the continuous constraints are directly included in the MILP. We demonstrate our approach on two examples: modeling of the spread of wildfire and the mitigation of water contamination. In both examples the computational results demonstrate that the solution time is significantly reduced by our methods. In particular, the dependence of the computation time on the size of the spatial discretization of the PDE is significantly reduced.}, subject = {Mixed-integer linear programming; Partial differential equations; Finite-element methods; Convection-diffusion equation; Global optimal control; Gemischt-ganzzahlige lineare Programmierung; Globale Optimalsteuerung; Konvektions-Diffusions-Gleichung; Finite-Elemente-Methode; Partielle Differentialgleichungen; Optimale Kontrolle; Finite-Elemente-Methode; Lineare Optimierung; Konvektions-Diffusionsgleichung}, language = {en} }