Moreover, we introduce a new class of facet-defining inequalities that

Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

We deal with the optimization of the production of branched sheet metal products. New forming techniques for sheet metal give rise to a wide variety of possible profiles and possible ways of production. In particular, we show how the problem of producing a given profile geometry can be modeled as a discrete optimization problem. We provide a theoretical analysis of the model in order to improve its solution time. In this context we give the complete convex hull description of some substructures of the underlying polyhedron. Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

G = (*V, E*) with non-negative edge weights*w*_{e} ∈ ℝ_{+} and letN,*N* ≥ 1, be a list of node sets. The weighted routing problem consists in finding mutually disjoint edge sets*S*_{1},...,*S*_{N} such that, for each*k* ∈ {1, ...,*N*}, the subgraph (*V*(*S*_{k}),*S*_{k}) contains an [*s, t*]-path for all*s, t ∈ T*_{k} and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We describe our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to switchbox routing problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.},
author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert},
booktitle = {Integer Programming and Combinatorial Optimization},
editor = {G. Rinaldi, L.A. Wolsey},
faupublication = {no},
keywords = {Routing in VLSI-design; Steiner tree; Steiner tree packing; Cutting Plane Algorithm},
pages = {447 - 463},
peerreviewed = {unknown},
series = {Proceedings of the 3rd IPCO Conference},
title = {{Routing} in {Grid} {Graphs} by {Cutting} {Planes}},
year = {1993}
}
@article{faucris.120541564,
abstract = {In many rural counties pupils on their way to school are a large, if not the largest group of customers for public mass transit. Hence an effective optimization of public mass transit in these regions must include the traffic caused by pupils. Besides a change in the schedules of the buses and the starting times of the trips, the school starting time may become an integral part of the planning process. We discuss the legal framework for this optimization problem in German states and counties and present a multi-objective mixed-integer linear programming formulation for the simultaneous specification of school and trip starting times. For its solution, we develop a two stage decomposition heuristic and apply it to practical data sets from three different rural German counties.},
author = {Fügenschuh, Armin-René and Martin, Alexander},
faupublication = {no},
journal = {Annals of Operations Research},
keywords = {Mixed-integer programming; Multicriteria optimization; Multiple traveling salesman problem; Time windows},
pages = {119 -- 216},
peerreviewed = {Yes},
title = {{A} {Multicriterial} {Approach} for {Optimizing} {Bus} {Schedules} and {School} {Starting} {Times}},
volume = {147},
year = {2006}
}
@misc{faucris.108959004,
abstract = {In this paper we analyze a uniform price electricity spot market that is
followed by redispatch in the case of network congestion. We assume
that the transmission system operator is incentivized to minimize
redispatch cost and compare a cost-based redispatch to a market-based
redispatch mechanism. For networks with at least three nodes we show
that in contrast to cost-based redispatch, in the case of market-based
redispatch the cost-minimizing allocation may not be short-run
efficient. As we demonstrate, the possibility of the transmission system
operator to reduce market-based redispatch cost at the expense of a
reduced welfare may be driven by the electricity supply side or the
electricity demand side. Based on these results, we propose a new hybrid
approach where the transmission system operator implements the
efficient (instead of the cost minimizing) dispatch and uses
market-based redispatch compensations},
author = {Grimm, Veronika and Martin, Alexander and Sölch, Christian and Weibelzahl, Martin and Zöttl, Gregor},
doi = {10.2139/ssrn.3120403},
faupublication = {yes},
keywords = {Electricity Markets; Redispatch; Congestion Management; Computational Equilibrium Models},
peerreviewed = {automatic},
title = {{Market}-based {Redispatch} {May} {Result} in {Inefficient} {Dispatch}},
url = {https://ssrn.com/abstract=3120403},
year = {2018}
}
@article{faucris.121671044,
abstract = {A new evaluation scheme for universal mobile telecommunications system (UMTS) radio networks is introduced. The approach takes the complex coupling of coverage and capacity through interference into account. Cell load estimates, otherwise obtained through Monte-Carlo simulation, can now be approximated without time-consuming iterative simulations on user snapshots. The two cornerstones are the generalization of interference coupling matrices from user snapshots to average load and the emulation of load control by an analytical scaling scheme. Building on the new evaluation scheme, two novel radio network optimization algorithms are presented: an efficient local search procedure and a mixed integer program that aims at designing the coupling matrix. Computational experiments for optimizing antenna tilts show that our new approaches outperform traditional snapshot models.},
author = {Eisenblätter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and Martin, Alexander and Wessäly, Roland},
doi = {10.1007/s00186-005-0002-z},
faupublication = {no},
journal = {Mathematical Methods of Operations Research},
keywords = {Network design; Network planning; UMTS radio interface},
pages = {1 - 29},
peerreviewed = {Yes},
title = {{UMTS} {Radio} {Network} {Evaluation} and {Optimization} beyond {Snapshots}},
volume = {63},
year = {2006}
}
@article{faucris.106485104,
abstract = {We study the existence and uniqueness of equilibria for perfectly competitive markets in capacitated transport networks. The model under consideration is rather general so that it captures basic aspects of related models in, e.g., gas or electricity networks. We formulate the market equilibrium model as a mixed complementarity problem and show the equivalence to a welfare maximization problem. Using the latter we prove uniqueness of the resulting equilibrium for piecewise linear and symmetric transport costs under additional mild assumptions. Moreover, we show the necessity of these assumptions by illustrating examples that possess multiple solutions if our assumptions are violated.

}, author = {Krebs, Vanessa and Schmidt, Martin}, doi = {10.1016/j.orp.2018.05.002}, faupublication = {yes}, journal = {Operations Research Perspectives}, keywords = {Market Equilibria; Networks; Transport Costs; Uniqueness; Perfect Competition}, pages = {169-173}, peerreviewed = {Yes}, title = {{Uniqueness} of {Market} {Equilibria} on {Networks} with {Transport} {Costs}}, url = {http://www.sciencedirect.com/science/article/pii/S2214716018300319}, volume = {5}, year = {2018} } @article{faucris.108899824, author = {Martin, Alexander and et al.}, author_hint = {A.~Martin, R.~Weismantel}, faupublication = {no}, pages = {185 -- 204}, peerreviewed = {Yes}, support_note = {Author relations incomplete. You may find additional data in field 'author_hint'}, title = {{Packing} {Paths} and {Steiner} {Trees}: {Routing} of {Electronic} {Circuits}}, volume = {6}, year = {1993} } @misc{faucris.217929705, abstract = {For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. To the best of our knowledge, the approaches for the RRF presented in the literature are restricted to continuous optimization problems. In this work, we first analyze relations between the RRF of a MIP and its continuous linear programming relaxation. In particular, we derive conditions under which a MIP and its continuous relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied and computed for a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the concept of the RRF to MIPs including “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In this extended setting, we again analyze relations between the RRF for a MIP and its continuous relaxation. Afterward, we present methods for computing the RRF for continuous linear as well as mixed-integer problems with safe constraints and variables. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 library for the calculation of the RR}, author = {Liers, Frauke and Schewe, Lars and Thürauf, Johannes}, faupublication = {yes}, keywords = {Robust Optimization; Mixed-integer programming; Uncertainty sets; Robust feasibility}, peerreviewed = {automatic}, title = {{Radius} of {Robust} {Feasibility} for {Mixed}-{Integer} {Problems}}, url = {http://www.optimization-online.org/DB_HTML/2019/05/7219.html}, year = {2019} } @incollection{faucris.122314984, abstract = {
*ed transmissions system operators* or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.

This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.

}, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, doi = {10.1016/j.ejor.2018.02.035}, faupublication = {yes}, journal = {European Journal of Operational Research}, keywords = {OR in energy; Natural gas network optimization; Entry-exit model; Transport network capacity; Large-scale mixed-integer nonlinear programming}, pages = {797-808}, peerreviewed = {Yes}, title = {{A} {System} to {Evaluate} {Gas} {Network} {Capacities}: {Concepts} and {Implementation}}, volume = {270}, year = {2018} } @article{faucris.204162733, abstract = {In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is use}, author = {Schewe, Lars and Schmidt, Martin and Thürauf, Johannes}, doi = {10.1007/s10288-019-00411-3}, faupublication = {yes}, journal = {4OR-A Quarterly Journal of Operations Research}, keywords = {Gas networks; Booking; Entry-exit system; Convexity; Flow models}, peerreviewed = {Yes}, title = {{Structural} {Properties} of {Feasible} {Bookings} in the {European} {Entry}-{Exit} {Gas} {Market} {System}}, url = {http://www.optimization-online.org/DB_HTML/2018/09/6831.html}, year = {2019} } @article{faucris.123414324, author = {Gottschalk, Corinna and Koster, Arie and Liers, Frauke and Peis, Britta and Schmand, Daniel and Wierz, Andreas}, doi = {10.1007/s10107-017-1170-3}, faupublication = {yes}, journal = {Mathematical Programming}, keywords = {05C21 Flows in graphs, 90C05 Linear programming, 90C59 Approximation methods and heuristics, 90C46 Optimality conditions, duality}, peerreviewed = {Yes}, title = {{Robust} flows over time: models and complexity results}, year = {2017} } @incollection{faucris.115682204, abstract = {Semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection. Using the spectral bundle method it is possible to exploit structural properties of the underlying problem and to apply, even to sparse large scale instances, cutting plane methods, probably the most successful technique in linear programming. We set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities presented in the recent study [2] of the facial structure of the associated polytope. Extensive numerical experiments show that the semidefinite branch-and-cut approach outperforms the classical simplex approach on a clear majority of the sparse large scale test instances. On instances from compiler design the simplex approach is faster.}, author = {Armbruster, Michael and Helmberg, Christoph and Fügenschuh, Marzena and Martin, Alexander}, booktitle = {Integer Programming and Combinatorial Optimization}, editor = {A. Lodi, A. Panconesi, G. Renaldi}, faupublication = {no}, keywords = {Branch and cut algorithms; Cutting plane algorithms; Polyhedral combinatorics; Semidefinite programs}, pages = {112 -- 124}, peerreviewed = {Yes}, series = {Proceedings of the IPCO 2008 Conference, LNCS 5035}, title = {{A} {Comparative} {Study} of {Linear} and {Semidefinite} {Branch}-and-{Cut} {Methods} for {Solving} the {Minimum} {Graph} {Bisection} {Problem}}, year = {2008} } @book{faucris.122269004, address = {Philadelphia}, editor = {Koch, Thorsten and Hiller, Benjamin and Pfetsch, Marc E. and Schewe, Lars}, faupublication = {yes}, isbn = {978-1-611973-68-6}, peerreviewed = {automatic}, publisher = {SIAM}, series = {SIAM-MOS Series on Optimization}, title = {{Evaluating} {Gas} {Network} {Capacities}}, year = {2015} } @incollection{faucris.123596704, abstract = {In order to optimize branched sheet metal profiles consisting of several chambers, decisions concerning topology and geometry have to be made. This leads to a problem entailing discrete and nonlinear features. We describe an integrated approach combining both aspects. The underlying idea is to use a branch-and-bound algorithm. In each node of the branch-and-bound tree, a nonlinear optimization problem has to be solved. We describe how the branch-and-bound tree is constructed, i.e., how the topology decision can be classified in a meaningful way. Moreover, we explain how to approach the nonlinear optimization problem arising in the nodes of the tree. We conclude by presenting a numerical example.}, author = {Göllner, Thea and Günther, Ute and Hess, Wolfgang and Martin, Alexander and Ulbrich, Stefan}, booktitle = {PAMM, Proceedings of Applied Mathematics and Mechanics}, faupublication = {yes}, pages = {713 -- 714}, peerreviewed = {No}, title = {{Topology} and {Geometry} {Optimization} of {Branched} {Sheet} {Metal} {Products}}, volume = {11}, year = {2011} } @article{faucris.124196424, abstract = {We introduce a mixed integer linear modeling approach for the optimization of dynamic transport networks based on the piecewise linearization of nonlinear constraints and we show how to apply this method by two examples, transient gas and water supply network optimization. We state the mixed integer linear programs for both cases and provide numerical evidence for their suitability.}, author = {Geißler, Björn and Kolb, Oliver and Lang, Jens and Leugering, Günter and Martin, Alexander and Morsi, Antonio}, doi = {10.1007/s00186-011-0354-5}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, keywords = {Mixed integer linear programming;Piecewise linear approximation;Gas network optimization;Water network optimization}, pages = {339-362}, peerreviewed = {Yes}, title = {{Mixed} integer linear models for the optimization of dynamical transport networks}, volume = {73}, year = {2011} } @masterthesis{faucris.123956624, author = {Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, school = {Friedrich-Alexander-Universität Erlangen-Nürnberg}, title = {{Über} {Aspekte} des {Designs} symmetrischer {Verschlüsselungsverfahren} mit einer {Anwendung} auf ein neues {Kryptosystem}}, year = {2008} } @incollection{faucris.108434084, abstract = {Oriented matroids are a combinatorial abstraction of finite sets of points in ℝ^{ n }. They have been used to study various problems in discrete and computational geometry (for more material on oriented matroids, see [1,2]). A number of methods to generate oriented matroids have been proposed (for instance in [4,8-10]) as these methods can be used as a building block for the algorithmic treatment of some hard problems: Algorithms to generate oriented matroids have for instance been used to decide whether certain 4-polytopes exist [6,10,14]. For these questions it is important to have effective algorithms for the generation of oriented matroids. We propose to use satisfiability solvers to generate oriented matroids. We have adapted this approach to generate oriented matroids that satisfy certain geometric constraints. Even though one can use the generated oriented matroids as a first step to find realizations (see for instance [2,6]), we will only focus on non-realizability results.},
address = {Berlin, Heidelberg},
author = {Schewe, Lars},
booktitle = {Mathematical Software - ICMS 2006},
doi = {10.1007/11832225_19},
editor = {Andrés Iglesias, Nobuki Takayama},
faupublication = {no},
isbn = {9783540380849},
pages = {216-218},
peerreviewed = {unknown},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{Generation} of oriented matroids using satisfiability solvers},
volume = {4151},
year = {2006}
}
@incollection{faucris.115449664,
abstract = {This paper discusses issues related to the progress in computational integer programming. The first part deals with the question to what extent computational experiments can be reproduced at all. Afterward the performance measurement of solvers and their comparison are investigated. Then academic progress in solving mixed-integer programming at the examples of the solver SIP and its successor SCIP is demonstrated. All arguments are supported by computational results. Finally, we discuss the pros and cons of developing academic software for solving mixed-integer programs.},
author = {Koch, Thorsten and Martin, Alexander and Pfetsch, Marc E.},
booktitle = {Facets of Combinatorial Optimization},
doi = {10.1007/978-3-642-38189-8_19},
editor = {Michael Jünger and Gerhard Reinelt},
faupublication = {yes},
isbn = {9783642381881},
pages = {483-506},
peerreviewed = {unknown},
publisher = {Springer-Verlag Berlin Heidelberg},
title = {{Progress} in {Academic} {Computational} {Integer} {Programming}},
year = {2013}
}
@article{faucris.109534304,
abstract = {We propose an equilibrium model that allows to analyze the long-run impact of the regulatory environment on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission operator and private firms in expectation of an energy-only market and cost-based redispatch. In different specifications we consider the cases of one vs. multiple price zones (market splitting) and analyze different approaches to recover network cost - in particular lump sum, generation capacity based, and energy based fees. In order to compare the outcomes of our multistage market model with a first-best benchmark, we also solve the corresponding integrated planner problem. Using two test networks we illustrate that energy-only markets can lead to suboptimal locational decisions for generation capacity and thus imply excessive network expansion. Market splitting heals these problems only partially. These results are valid for all considered types of network tariffs, although investment slightly differs across those regime},
author = {Grimm, Veronika and Martin, Alexander and Schmidt, Martin and Weibelzahl, Martin and Zöttl, Gregor},
doi = {10.1016/j.ejor.2016.03.044},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {Equilibrium Models, Mixed-Integer Nonlinear Optimization, Multilevel Programming, Electricity Markets, Network Expansion, Transmission Management},
pages = {493-509},
peerreviewed = {Yes},
title = {{Transmission} and generation investment in electricity markets: {The} effect of market splitting and network fee regimes},
url = {http://www.optimization-online.org/DB_HTML/2015/03/4803.html},
volume = {254},
year = {2016}
}
@article{faucris.115644584,
abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.},
author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert},
faupublication = {no},
journal = {Computers & Mathematics With Applications},
pages = {23 - 35},
peerreviewed = {Yes},
title = {{Optimum} path packing on wheels: {The} consecutive case},
volume = {31},
year = {1996}
}
@incollection{faucris.120542664,
author = {Günther, Ute and Martin, Alexander},
booktitle = {Tagungsband 1. Zwischenkolloqium SFB 666},
editor = {P. Groche},
faupublication = {no},
pages = {47 -- 53},
peerreviewed = {No},
publisher = {Meisenbach Verlag, Bamberg},
title = {{Modellierung} von {Fertigungsrestriktionen} bei der {Herstellung} von verzweigten {Blechbauteilen}},
year = {2007}
}
@article{faucris.117697404,
abstract = {We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to difficult nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the nonlinearities and a tailored alternating direction method. Most other publications in the field of gas transport optimization only consider pressure and flow as main physical quantities. In this work, we additionally incorporate heat power supplies and demands as well as a mixing model for different gas qualities. We demonstrate the capabilities of our method on Germany's largest transport networks and hereby present numerical results on the largest instances that were ever reported in the literature for this problem class.},
author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars and Schmidt, Martin},
doi = {10.1016/j.compchemeng.2015.07.005},
faupublication = {yes},
journal = {Computers & Chemical Engineering},
keywords = {Nonconvex mixed-integer nonlinear optimization; Alternating direction methods; Piecewise linear relaxations; Gas transport networks; Heat power supply and demand},
pages = {303-317},
peerreviewed = {Yes},
title = {{Solving} power-constrained gas transportation problems using an {MIP}-based alternating direction method},
volume = {82},
year = {2015}
}
@article{faucris.119135324,
abstract = {We show that the edge graph of a 6-dimensional polytope with 12 facets has diameter at most 6, thus verifying the d-step conjecture of Klee and Walkup in the case d = 6. This implies that for all pairs (d, n) with n - d ≤ 6, the diameter of the edge graph of a d-polytope with n facets is bounded by 6, which proves the Hirsch conjecture for all n - d ≤ 6. We prove this result by establishing this bound for a more general structure, so-called matroid polytopes, by reduction to a small number of satisfiability problems. © Taylor & Francis Group, LLC.},
author = {Bremner, David and Schewe, Lars},
doi = {10.1080/10586458.2011.564965},
faupublication = {yes},
journal = {Experimental Mathematics},
keywords = {Diameter; Hirsh conjecture; Oriented matroids; Polytopes; Satisfiability},
pages = {229-237},
peerreviewed = {Yes},
title = {{Edge}-graph diameter bounds for convex polytopes with few facets},
volume = {20},
year = {2011}
}
@incollection{faucris.120025004,
abstract = {This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvátal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported.},
author = {Martin, Alexander and Weismantel, Robert},
booktitle = {Integer Programming and Combinatorial Optimization},
editor = {R.E. Bixby, E.A. Boyd, R.Z. Ríos-Mercado},
faupublication = {no},
pages = {243 - 256},
peerreviewed = {Yes},
series = {Proceedings of the 6th IPCO Conference},
title = {{The} {Intersection} of {Knapsack} {Polyhedra} and {Extensions}},
year = {1998}
}
@incollection{faucris.115646564,
author = {Martin, Alexander},
booktitle = {Encyclopedia of Life Support Systems (EOLSS)},
faupublication = {no},
pages = {411 -- 428},
peerreviewed = {No},
publisher = {UNESCO},
title = {{Large} {Scale} {Optimization}},
year = {2002}
}
@article{faucris.120013784,
abstract = {We study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations on a graph. We propose an instantaneous control approach in which suitable Euler discretizations yield systems of ordinary differential equations on a graph. This networked system of ordinary differential equations is shown to be well-posed and affine-linear solutions of these systems are derived analytically. As a consequence, finite-dimensional mixed-integer linear optimization problems are obtained for every time step that can be solved to global optimality using general-purpose solvers. We illustrate our approach in practice by presenting numerical results on a realistic gas transport network.},
author = {Gugat, Martin and Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias and Wintergerst, David},
doi = {10.1007/s10589-017-9970-1},
faupublication = {yes},
journal = {Computational Optimization and Applications},
keywords = {Mixed-integer optimal control, Instantaneous control, Partial differential equations on graphs, Gas networks, Mixed-integer linear optimization.},
pages = {267-294},
peerreviewed = {Yes},
title = {{MIP}-based instantaneous control of mixed-integer {PDE}-constrained gas transport problems},
volume = {70},
year = {2018}
}
@article{faucris.115708824,
abstract = {While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semi- definite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semi- definite approaches for large sparse instances, we set up a common branch and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound prof- its much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch- and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.},
author = {Armbruster, Michael and Fügenschuh, Marzena and Helmberg, Christoph and Martin, Alexander},
faupublication = {yes},
journal = {Mathematical Programming Computation},
keywords = {Branch and cut algorithms; Cutting plane algorithms; Polyhedral combinatorics; Semidefinite programs; Graph bisection},
pages = {275 -- 306},
peerreviewed = {Yes},
title = {{LP} and {SDP} {Branch}-and-{Cut} {Algorithms} for the {Minimum} {Graph} {Bisection} {Problem}: {A} {Computational} {Comparison}},
volume = {4},
year = {2012}
}
@incollection{faucris.115662844,
abstract = {This paper presents cutting planes which are useful or potentially useful for solving mixed integer programs that arise in the optimisation of gas networks. We consider polyhedra that are defining essential parts of the model and give a polynomial algorithm for the calculation of the set of vertices of such polyhedra implying a polynomial separation algorithm for the convex hull of the polyhedra can be developed.},
author = {Martin, Alexander and Möller, Markus},
booktitle = {Modeling, Simulation and Optimization of Complex Processes},
editor = {H.G. Bock, E. Kostina, H.X. Phu, R. Rannacher},
faupublication = {no},
keywords = {Mixed Integer Programming; Cutting Planes; Gas Optimisation; Piecewise Linear Functions},
pages = {307 - 330},
peerreviewed = {unknown},
publisher = {Springer, Heidelberg},
title = {{Cutting} {Planes} for the {Optimisation} of {Gas} {Networks}},
year = {2005}
}
@article{faucris.115710364,
abstract = {Die Anwendung von Optimierungsmethoden ist in den letzten Jahren zu einem zentralen Bestandteil eines effizienten Energiemanagements geworden. Kraftwerke müssen beispielsweise optimal gesteuert werden und die Energieproduktion auf variierende Lastprofile angepasst werden. Die Optimierung gewinnt daher in Ergänzung zur Simulation immer mehr an Bedeutung, gerade in Zusammenhang mit ingenieurwissenschaftlichen und energiewirtschaftlichen Fragestellungen. Die wichtigsten Optimierungsmethoden werden aus mathematischer Sicht vorgestellt. An zwei ausgewählten Beispielen wird der Mehrwert moderner mathematischer Verfahren zur Bestimmung von nachweislich guten bzw. global optimalen Lösungen gezeigt.

procedure yields a mixed-integer nonlinear problem (MINLP) that can be solved to global optimality.

For the numerical solution of the MINLP, we consider a relaxation approach allowing to solve the problem globally by a sequence of mixed-integer problems (MIPs) with any required accuracy. The relaxation is based on piecewise linearization of the nonlinear constraints modeling the gas dynamics on the pipelines. Due to the particular discretization of the state equations, only univariate nonlinearities have to be approximated. This substantially facilitates the numerical treatment of the nonlinear constraints. To illustrate the efficiency of the proposed approach, we present numerical tests for typical benchmark problems.}, author = {Burlacu, Robert and Egger, Herbert and Gross, Martin and Martin, Alexander and Pfetsch, Marc E. and Schewe, Lars and Sirvent, Mathias and Skutella, Martin}, faupublication = {yes}, keywords = {Discretization; Instationary Gas Transport Optimization; Mixed-Integer Nonlinear Programming}, peerreviewed = {automatic}, title = {{A} {Global} {Optimization} {Approach} for {Instationary} {Gas} {Transport} in {Pipeline} {Networks}}, url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/221}, year = {2017} } @article{faucris.120380524, abstract = {A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach.}, author = {Martin, Alexander and Möller, Markus and Moritz, Susanne}, doi = {10.1007/s10107-005-0665-5}, faupublication = {no}, journal = {Mathematical Programming}, keywords = {Branch-and-Bound; Cutting planes; Gas optimization; Mixed integer programming; Piece-wise linear functions; SOS constraints}, pages = {563 - 582}, peerreviewed = {Yes}, title = {{Mixed} {Integer} {Models} for the {Stationary} {Case} of {Gas} {Network} {Optimization}}, volume = {105}, year = {2006} } @article{faucris.120164704, abstract = {In this paper we consider the multiple knapsack problem, which is defined as follows: given a set* N* of items with weights $f_i ,i \in N$, a set *M* of knapsacks with capacities $F_k ,k \in M$, and a profit function $c_{ik} ,i \in N,k \in M$, find an assignment of a subset of the set of items to the set of knapsacks that yields minimum cost. We consider the multiple knapsack problem from a polyhedral point of view. The inequalities that we describe here serve as the theoretical basis for a cutting plane algorithm. We present some of the implementation details of this algorithm, including a discussion and evaluation of different separation and primal heuristics. Our algorithm is applied to practical problem instances arising in the design of main frame computers, in the layout of electronic circuits, and in sugar cane alcohol production.

},
author = {Liers, Frauke and Merkert, Maximilian},
doi = {10.1137/15M1006751},
faupublication = {yes},
journal = {SIAM Journal on Optimization},
keywords = {combinatorial optimization, complete description, network flow problems, piecewise linear functions},
pages = {2863-2886},
peerreviewed = {Yes},
title = {{Structural} {Investigation} of {Piecewise} {Linearized} {Network} {Flow} {Problems}},
volume = {26},
year = {2016}
}
@article{faucris.115672964,
abstract = {For a long time product development is trying to break down the design process to single steps that allow for an uninterrupted computer-aided and algorithm-based design process. One goal of the Collaborative Research Centre 666 is the "automated" design of integral, bifurcated sheet metal parts. The final 3D CAD-model is generated based on a mathematically optimized geometry which in turn defined by product-specific individual customer requirements.},
author = {Anderl, Reiner and Kormann, Marco and Rollmann, Thomas and Wu, Zhenyu and Martin, Alexander and Ulbrich, Stefan and Günther, Ute},
faupublication = {no},
journal = {Konstruktion},
pages = {79 -- 82},
peerreviewed = {Yes},
title = {{An} {Approach} to {Algorithm}-{Based} {Design} in {Product} {Development}},
volume = {5},
year = {2007}
}
@misc{faucris.118869344,
abstract = {We consider nonlinear and nonsmooth mixing aspects in gas transport
optimization problems. As mixed-integer reformulations of pooling-type
mixing models already render small-size instances computationally
intractable, we investigate the applicability of smooth nonlinear
programming techniques for equivalent complementarity-based
reformulations. Based on recent results for remodeling piecewise affine
constraints using an inverse parametric quadratic programming approach,
we show that classical stationarity concepts are meaningful for the
resulting complementarity-based reformulation of the mixing equations.
Further, we investigate in a numerical study the performance of this
reformulation compared to a more compact complementarity-based one that
does not feature such beneficial regularity properties. All computations
are performed on publicly available data of real-world size problem
instances from steady-state gas transport.},
author = {Hante, Falk and Schmidt, Martin},
faupublication = {yes},
keywords = {Gas transport networks, Mixing, Inverse parametric quadratic programming, Complementarity constraints, MPCC},
peerreviewed = {automatic},
title = {{Complementarity}-{Based} {Nonlinear} {Programming} {Techniques} for {Optimal} {Mixing} in {Gas} {Networks}},
url = {http://www.optimization-online.org/DB_HTML/2017/09/6198.html},
year = {2017}
}
@article{faucris.217787197,
abstract = {In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP , we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems. Finally, we present two case studies that illustrate the applicability of our approach.},
author = {Burlacu, Robert and Egger, Herbert and Gross, Martin and Martin, Alexander and Pfetsch, Marc E. and Schewe, Lars and Sirvent, Mathias and Skutella, Martin},
doi = {10.1007/s11081-018-9414-5},
faupublication = {yes},
journal = {Optimization and Engineering},
keywords = {First-discretize-then-optimize; Mixed-integer nonlinear programming; Power-to-gas; Storage capacity maximization; Transient gas transport optimization},
note = {CRIS-Team Scopus Importer:2019-05-17},
pages = {543-573},
peerreviewed = {Yes},
title = {{Maximizing} the storage capacity of gas networks: a global {MINLP} approach},
volume = {20},
year = {2019}
}
@misc{faucris.213202067,
abstract = {We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, we derive sufficient conditions that ensure uniqueness of generation and demand. We also prove uniqueness of the market equilibrium for the special case of a single storage operator. Nevertheless, in case of multiple storage operators, uniqueness fails to hold in general, which we show by illustrative examples. We conclude the theoretical discussion with a general ex-post condition for proving the uniqueness of a given solution. In contrast to classical settings without storages, the computation of market equilibria is much more challenging since storage operations couple all trading events over time. For this reason, we propose a tailored parallel and distributed alternating direction method of multipliers (ADMM) for efficiently computing spot-market equilibria over long time horizons. We first analyze the parallel performance of the method itself. Finally, we show that the parallel ADMM clearly outperforms solving the respective problems directly and that it is capable of solving instances with more than 42 million variables in less than 13 minute},
author = {Grübel, Julia and Kleinert, Thomas and Krebs, Vanessa and Orlinskaya, Galina and Schewe, Lars and Schmidt, Martin and Thürauf, Johannes},
faupublication = {yes},
keywords = {Electricity markets; Storage; Market equilibria; Uniqueness; ADMM; Parallel computing; Large-scale optimization},
peerreviewed = {automatic},
title = {{On} {Electricity} {Market} {Equilibria} with {Storages}: {Modeling}, {Uniqueness}, and a {Distributed} {ADMM}},
url = {http://www.optimization-online.org/DB_HTML/2019/03/7118.html},
year = {2019}
}
@incollection{faucris.120543104,
author = {Leugering, Günter and Martin, Alexander and Stingl, Michael},
booktitle = {Produktionsfaktor Mathematik},
editor = {M. Grötschel, K. Lucas, V. Mehrmann},
faupublication = {yes},
pages = {323 -- 340},
peerreviewed = {Yes},
series = {acatech diskutiert},
title = {{Topologie} und dynamische {Netzwerke}: {Anwendungen} der {Zukunft}},
year = {2008}
}
@article{faucris.115677804,
abstract = {We introduce a continuous optimal control problem governed by ordinary and partial differential equations for supply chains on networks. We derive a mixed-integer model by discretization of the dynamics of the partial differential equations and by approximations to the cost functional. Finally, we investigate numerically properties of the derived mixed-integer model and present numerical results for a real-world example.},
author = {Fuegenschuh, A. and Goettlich, S. and Herty, Michael and Klar, Axel and Martin, Alexander},
doi = {10.1137/060663799},
faupublication = {no},
journal = {SIAM Journal on Scientific Computing},
keywords = {Supply chains; Conservation laws; Networks; Optimization},
pages = {1490 -- 1507},
peerreviewed = {Yes},
title = {{A} {Discrete} {Optimization} {Approach} to {Large} {Scale} {Supply} {Networks} {Based} on {Partial} {Differential} {Equations}},
volume = {30},
year = {2008}
}
Read More: http://epubs.siam.org/doi/abs/10.1137/110853248

In this work, we study the runway scheduling problem with aircraft precedences and safety distance constraints. We consider two extreme scenarios. In the best-case scenario, the two planners cooperate completely in order to determine optimized schedules. In the worst-case scenario, however, the planning tools compete and act as adversaries. Using techniques from mathematical optimization, we model these two scenarios. We experimentally evaluate the approaches on randomly generated instances with respect to running times for solving the problems to global optimality and with respect to the computed throughput. On small examples, we show that indeed there can be large differences in the runway utilization in the two scenarios. It would be interesting to investigate whether today’s real schedules are closer to the best-case or closer to the worst-case scenario in order to understand whether the development, implementation and maintenance of an integrated tool could pay off.},
author = {Liers, Frauke and Martin, Alexander and Peter, Andrea},
faupublication = {yes},
peerreviewed = {automatic},
title = {{Mathematical} {Analysis} of {Runway} {Scheduling} with {Aircraft} {Precedences}},
year = {2017}
}
@article{faucris.108900484,
abstract = {We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.},
author = {E. Ferreira, Carlos and Martin, Alexander and de Souza, Cid C. and Weismantel, Robert and Wolsey, Laurence},
faupublication = {no},
journal = {Mathematical Programming},
keywords = {Clustering; Ear decomposition; Equipartition; Graph partitioning; Integer programming; Knapsack},
pages = {247 - 266},
peerreviewed = {Yes},
title = {{Formulations} and valid inequalities for the node capacitated graph partitioning problem},
volume = {74},
year = {1996}
}
@incollection{faucris.108905104,
abstract = {We develop a primal heuristic based on a genetic algorithm for the minimum graph bisection problem and incorporate it in a branch-and-cut framework. The problem concerns partitioning the nodes of a weighted graph into two subsets such that the total weight of each set is within some lower and upper bounds. The objective is to minimize the total cost of the edges between both subsets of the partition. We formulate the problem as an integer program. In the genetic algorithm the LP-relaxation of the IP-formulation is exploited. We present several ways of using LP information and demonstrate the computational success.},
author = {Armbruster, Michael and Fügenschuh, Marzena and Helmberg, Christoph and Jetchev, Nikolay and Martin, Alexander},
booktitle = {Proceedings of 6th European Conference, EvoCOP 2006, Budapest, Hungary, April 10-12, 2006},
doi = {10.1007/11730095_1},
faupublication = {no},
pages = {1-12},
peerreviewed = {unknown},
publisher = {Springer, Berlin},
series = {Lecture Notes in Computer Science},
title = {{Hybrid} {Genetic} {Algorithm} {Within} {Branch}-and-{Cut} for the {Minimum} {Graph} {Bisection} {Problem}},
volume = {3906},
year = {2006}
}
@article{faucris.120855504,
abstract = {In this paper we continue the investigations in [3] for the Steiner tree packing polyhedron. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-definining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic curcuits.},
author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert},
faupublication = {no},
journal = {European Journal of Combinatorics},
pages = {39 - 52},
peerreviewed = {Yes},
title = {{Packing} {Steiner} trees: {Further} facets},
volume = {17},
year = {1996}
}
@article{faucris.106480484,
abstract = {This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a first best benchmark. We provide conditions under which the solution of the simultaneous game is also the solution of the corresponding MNCP. However, equilibria cannot be determined by the MNCP as the transmission system operator's (TSO’s) first-order conditions are insufficient, which goes back to nonconvexities of the gas flow model. This also implies that the welfare maximization problem may have multiple solutions that sometimes do not even coincide with any of the market equilibria. Our analysis shows that, even in the absence of strategic firms, market interaction fails to implement desirable outcomes from a welfare perspective due to the TSO’s incentive structure. We conclude that the technical environment calls for a market design that commits the TSO to a welfare objective through regulation and propose a design where the market solution corresponds to a welfare maximum and vice vers},
author = {Grimm, Veronika and Grübel, Julia and Schewe, Lars and Schmidt, Martin and Zöttl, Gregor},
doi = {10.1016/j.ejor.2018.09.016},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {Fundamental Welfare Theorems; Multiplicity; Natural Gas Markets; Nonconvex Equilibrium Models; Uniqueness},
peerreviewed = {Yes},
title = {{Nonconvex} {Equilibrium} {Models} for {Gas} {Market} {Analysis}: {Failure} of {Standard} {Techniques} and {Alternative} {Modeling} {Approaches}},
url = {https://www.sciencedirect.com/science/article/abs/pii/S0377221718307768},
year = {2018}
}
@phdthesis{faucris.106579264,
author = {Schmidt, Martin},
faupublication = {no},
peerreviewed = {automatic},
school = {Friedrich-Alexander-Universität Erlangen-Nürnberg},
title = {{A} {Generic} {Interior}-{Point} {Framework} for {Nonsmooth} and {Complementarity} {Constrained} {Nonlinear} {Optimization}},
year = {2013}
}
@incollection{faucris.108915664,
author = {Mahlke, Debora and Martin, Alexander and Zelmer, Andrea},
booktitle = {thema forschung},
faupublication = {yes},
pages = {66 -- 69},
peerreviewed = {No},
publisher = {TU Darmstadt},
title = {{Reliable} {Systems} - {Supply} and {Demand} from a {Comprehensive} {Perspective}},
volume = {1},
year = {2010}
}
@article{faucris.120889164,
abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.},
author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert},
faupublication = {no},
journal = {SIAM Journal on Discrete Mathematics},
keywords = {Dual graph; Dynamic programming; Multicuts; Separation; Shortest path; Steiner tree},
pages = {233 - 257},
peerreviewed = {Yes},
title = {{Packing} {Steiner} trees: {Separation} algorithms},
volume = {9},
year = {1996}
}
@article{faucris.115672084,
abstract = {In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.},
author = {Mahlke, Debora and Martin, Alexander and Moritz, Susanne},
faupublication = {no},
journal = {Mathematical Methods of Operations Research},
keywords = {Heuristics; Mixed integer nonlinear programming; Relaxation; Simulated annealing; Transient gas optimization},
pages = {99 -- 116},
peerreviewed = {Yes},
title = {{A} simulated annealing algorithm for transient optimization in gas networks},
volume = {66},
year = {2007}
}
@article{faucris.122777864,
abstract = {Due to strict regulatory rules in combination with complex nonlinear physics, major gas network operators in Germany and Europe face hard planning problems that call for optimization. In part 1 of this paper we have developed a suitable model hierarchy for that purpose. Here we consider the more practical aspects of modeling. We validate individual model components against a trusted simulation tool, give a structural overview of the model hierarchy, and use its large variety of approximations to devise robust and efficient solution techniques. An extensive computational study demonstrates the suitability of our models and techniques for previously unsolvable problems in gas network planning.},
author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.},
doi = {10.1007/s11081-015-9300-3},
faupublication = {yes},
journal = {Optimization and Engineering},
keywords = {Gas networks; Stationary flow; High-detail modeling; Nonsmooth nonlinear discrete-continuous optimization; Smoothing techniques; 90B10; 90C06; 90C30; 90C90},
pages = {437-472},
peerreviewed = {Yes},
title = {{High} detail stationary optimization models for gas networks: validation and results},
url = {http://www.optimization-online.org/DB_HTML/2014/10/4602.html},
volume = {17},
year = {2016}
}
@book{faucris.122447864,
abstract = {Sanitizable signature schemes, as defined by Ateniese et al. (ESORICS 2005), allow a signer to partly delegate signing rights to another party, called the sanitizer. That is, the sanitizer is able to modify a predetermined part of the original message such that the integrity and authenticity of the unchanged part is still verifiable. Ateniese et al. identify five security requirements for such schemes (unforgeability, immutability, privacy, transparency and accountability) but do not provide formal specifications for these properties. They also present a scheme that is supposed to satisfy these requirements. Here we revisit the security requirements for sanitizable signatures and, for the first time, present a comprehensive formal treatment. Besides a full characterization of the requirements we also investigate the relationship of the properties, showing for example that unforgeability follows from accountability. We then provide a full security proof for a modification of the original scheme according to our model. © International Association for Cryptologic Research 2009.},
author = {Brzuska, Chris and Fischlin, Marc and Freudenreich, Tobias and Lehmann, Anja and Page, Marcus and Schelbert, Jakob and Schröder, Dominique and Volk, Florian},
doi = {10.1007/978-3-642-00468-1_18},
faupublication = {no},
pages = {317-336},
peerreviewed = {Yes},
series = {Public Key Cryptography - PKC 2009},
title = {{Security} of sanitizable signatures revisited},
volume = {5443},
year = {2009}
}
@article{faucris.118421644,
abstract = {In this paper, we study the problem of technical transient gas network optimization, which can be considered a minimum cost flow problem with a nonlinear objective function and additional nonlinear constraints on the network arcs. Applying an implicit box scheme to the isothermal Euler equation, we derive a mixed-integer nonlinear program. This is solved by means of a combination of (i) a novel mixed-integer linear programming approach based on piecewise linearization and (ii) a classical sequential quadratic program applied for given combinatorial constraints. Numerical experiments show that better approximations to the optimal control problem can be obtained by using solutions of the sequential quadratic programming algorithm to improve the mixed-integer linear program. Moreover, iteratively applying these two techniques improves the results even further.},
author = {Domschke, Pia and Geißler, Björn and Kolb, Oliver and Lang, Jens and Martin, Alexander and Morsi, Antonio},
doi = {10.1287/ijoc.1100.0429},
faupublication = {yes},
journal = {Informs Journal on Computing},
keywords = {gas networks; optimal control; mixed-integer programming; nonlinear programming; sequential quadratic programming},
pages = {605-617},
peerreviewed = {Yes},
title = {{Combination} of {Nonlinear} and {Linear} {Optimization} of {Transient} {Gas} {Networks}},
volume = {23},
year = {2011}
}
@article{faucris.106309324,
abstract = {We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal design of zonal pricing electricity markets. This together with nonlinearities due to economic modeling yields extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof, whereas the second is a tailored generalized Benders decomposition. We prove for both methods that they yield global optimal solutions. Finally, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformatio},
author = {Kleinert, Thomas and Schmidt, Martin},
doi = {10.1016/j.disopt.2019.02.002},
faupublication = {yes},
journal = {Discrete Optimization},
keywords = {Electricity market design; Graph partitioning; Mixed-integer optimization; Multilevel optimization; Network design},
peerreviewed = {Yes},
title = {{Global} {Optimization} of {Multilevel} {Electricity} {Market} {Models} {Including} {Network} {Design} and {Graph} {Partitioning}},
year = {2019}
}
@article{faucris.122464804,
abstract = {In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we focus on binary Steiner trees in which all node degrees are required to be at most three. It is shown that finding a binary Steiner tree is NP-complete for arbitrary graphs. We relate the problem to Steiner trees without degree constraints as well as degree-constrained spanning trees by proving approximation ratios. Further, we give integer programming formulations for this problem on undirected and directed graphs and study the associated polytopes for both cases. Some classes of facets are introduced. Based on this study a branch-&-cut approach is developed and evaluated on biological instances coming from the reconstruction of phylogenetic trees. We are able to solve nearly all instances up to 200 nodes to optimality within a limited amount of time. This shows the effectiveness of our approach.},
author = {Liers, Frauke and Martin, Alexander and Pape, Susanne},
doi = {10.1016/j.disopt.2016.05.006},
faupublication = {yes},
journal = {Discrete Optimization},
keywords = {Steiner tree; Degree constraint; Steiner ratio; Integer programming; Polytope; Branch-&-cut},
pages = {85-117},
peerreviewed = {Yes},
title = {{Binary} {Steiner} {Trees}: {Structural} {Results} and an {Exact} {Solution} {Approach}},
volume = {21},
year = {2016}
}
@article{faucris.120371504,
abstract = {Let*G*=(*V, E*) be a graph and*T*⊆*V* be a node set. We call an edge set*S* a Steiner tree for*T* if*S* connects all pairs of nodes in*T*. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph*G*=(*V, E*) with edge weights*w*_{e}, edge capacities*c*_{e},*e*∈*E*, and node set*T*_{1},…,*T*_{N}, find edge sets*S*_{1},…,*S*_{N} such that each*S*_{k} is a Steiner tree for*T*_{k}, at most*c*_{e} of these edge sets use edge*e* for each*e*∈*E*, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).},
author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert},
faupublication = {no},
journal = {Mathematical Programming},
keywords = {Cutting planes; Facets; Packing; Polyhedron; Steiner tree},
pages = {101 - 123},
peerreviewed = {Yes},
title = {{Packing} {Steiner} {Trees}: {Polyhedral} {Investigations}},
volume = {72},
year = {1996}
}
@incollection{faucris.110561704,
abstract = {

In this chapter we discuss the problem of validation of nominations as a nonsmooth and nonconvex mixed-integer nonlinear feasibility problem. For this problem we present a primal heuristic that is based on reformulation techniques that smooth the appearing nonsmooth aspects and that reformulate discrete aspects with complementarity constraints and problem specific relaxations. The resulting mathematical program with equilibrium constraints (MPEC) model can be regularized by standard techniques leading to a nonlinear program (NLP) type model. Solutions to the latter can finally be used as approximative solutions to the underlying feasibility problem.

}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch9}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {163-180}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{An} {MPEC} based heuristic}, year = {2015} } @article{faucris.119100784, author = {Armbruster, Michael and Helmberg, Christoph and Fügenschuh, Armin and Martin, Alexander}, faupublication = {no}, journal = {SIAM Journal on Discrete Mathematics}, pages = {1073 -- 1098}, peerreviewed = {Yes}, title = {{On} the {Graph} {Bisection} {Cut} {Polytope}}, volume = {22}, year = {2008} } @incollection{faucris.117699164, abstract = {Complex real-world optimization tasks often lead to mixed-integer nonlinear problems (MINLPs). However, current MINLP algorithms are not always able to solve the resulting large-scale problems. One remedy is to develop problem specific primal heuristics that quickly deliver feasible solutions. This paper presents such a primal heuristic for a certain class of MINLP models. Our approach features a clear distinction between nonsmooth but continuous and genuinely discrete aspects of the model. The former are handled by suitable smoothing techniques; for the latter we employ reformulations using complementarity constraints. The resulting mathematical programs with equilibrium constraints (MPEC) are finally regularized to obtain MINLP-feasible solutions with general purpose NLP solvers.}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Facets of Combinatorial Optimization}, doi = {10.1007/978-3-642-38189-8_13}, editor = {Jünger M, Reinelt G}, faupublication = {no}, isbn = {978-3-642-38188-1}, pages = {295-320}, peerreviewed = {Yes}, publisher = {Springer Berlin Heidelberg}, title = {{A} {Primal} {Heuristic} for {Nonsmooth} {Mixed} {Integer} {Nonlinear} {Optimization}}, year = {2013} } @incollection{faucris.119769364, abstract = {In this article, we present a new algorithm for the solution of nonconvex mixed-integer nonlinear optimization problems together with an application from gas network optimization, the gas transport energy cost minimization problem. Here, the aim is to transport gas through the network at minimum operating cost. The proposed algorithm is based on the adaptive refinement of a new class of MIP-relaxations and has been developed within an industry project on gas network optimization. Since therefore the implementation is not as general as it could be, our computational results are restricted to instances from gas network optimization at this point of time. However, as these problems are real-world applications and turn out to be rather hard to solve with the aid of state-of-the-art MINLP-solvers we believe that our computational results reveal the potential of this new approach and motivate further research on the presented techniques.}, address = {Berlin Heidelberg}, author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars}, booktitle = {Facets of Combinatorial Optimization}, doi = {10.1007/978-3-642-38189-8_14}, editor = {Jünger M, Reinelt G}, faupublication = {yes}, isbn = {9783642381881}, pages = {321-353}, peerreviewed = {unknown}, publisher = {Springer-Verlag}, title = {{A} new algorithm for {MINLP} applied to gas transport energy cost minimization}, year = {2013} } @incollection{faucris.115668124, abstract = {We investigate the minimum graph bisection problem concerning partitioning the nodes of a graph into two subsets such that the total weight of each set is within some lower and upper limits. The objective is to minimize the total cost of edges between both subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and in parallel computing. We present an integer linear programming formulation for this problem. We develop a primal heuristic based on a genetic algorithm, incorporate it in a branch-and-cut framework and present some computational results.}, author = {Armbruster, Michael and Fügenschuh, Marzena and Helmberg, Christoph and Jetchev, Nikolay and Martin, Alexander}, booktitle = {Operations Research Proceedings 2005, Bremen, September 7-9, 2005}, faupublication = {no}, pages = {315-320}, peerreviewed = {unknown}, publisher = {Springer, Berlin}, title = {{LP}-based {Genetic} {Algorithm} for the {Minimum} {Graph} {Bisection} {Problem}}, year = {2005} } @incollection{faucris.115726424, abstract = {

We describe how to tackle the problem of validating nominations using mixed-integer programming methods. To this end we first give a mixed-integer nonlinear programming formulation of NoVa, from which we derive a mixed-integer linear relaxation. Our reformulation technique allows us to prescribe an a priori bound on the error we make when relaxing the nonlinear functions.

}, author = {Geißler, Björn and Martin, Alexander and Morsi, Antonio and Schewe, Lars}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973696}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, isbn = {978-1-611973-68-6}, pages = {103-122}, peerreviewed = {unknown}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{The} {MILP}-relaxation approach}, year = {2015} } @article{faucris.120820304, author = {Bokowski, Jürgen and Schewe, Lars}, faupublication = {no}, journal = {Revue roumaine de mathématiques pures et appliquées}, pages = {483-493}, peerreviewed = {Yes}, title = {{There} are no realizable 15\4- and 16\4 -configurations}, volume = {50}, year = {2005} } @article{faucris.118144004, abstract = {In this article we consider combinatorial markets with valuations only for singletons and pairs of buy/sell-orders for swapping two items in equal quantity. We provide an algorithm that permits polynomial time market-clearing and -pricing. The results are presented in the context of our main application: the futures opening auction problem. Futures contracts are an important tool to mitigate market risk and counterparty credit risk. In futures markets these contracts can be traded with varying expiration dates and underlyings. A common hedging strategy is to roll positions forward into the next expiration date, however this strategy comes with significant operational risk. To address this risk, exchanges started to offer so-called futures contract combinations, which allow the traders for swapping two futures contracts with different expiration dates or for swapping two futures contracts with different underlyings. In theory, the price is in both cases the difference of the two involved futures contracts. However, in particular in the opening auctions price inefficiencies often occur due to suboptimal clearing, leading to potential arbitrage opportunities. We present a minimum cost flow formulation of the futures opening auction problem that guarantees consistent prices. The core ideas are to model orders as arcs in a network, to enforce the equilibrium conditions with the help of two hierarchical objectives, and to combine these objectives into a single weighted objective while preserving the price information of dual optimal solutions. The resulting optimization problem can be solved in polynomial time and computational tests establish an empirical performance suitable for production environments.}, author = {Müller, Johannes and Pokutta, Sebastian and Martin, Alexander and Pape, Susanne and Peter, Andrea and Winter, Thomas}, doi = {10.1007/s00186-016-0555-z}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, keywords = {Equilibrium problems; Hierarchical objectives; Linear programming; Network flows; Combinatorial auctions; Futures exchanges}, pages = {155-177}, peerreviewed = {Yes}, title = {{Pricing} and clearing combinatorial markets with singleton and swap orders: {Efficient} algorithms for the futures opening auction problem}, volume = {85}, year = {2017} } @article{faucris.120538924, abstract = {In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.}, author = {Grötschel, Martin and Martin, Alexander and Weismantel, Robert}, faupublication = {no}, journal = {Mathematical Programming}, keywords = {Cutting plane algorithm; Routing in VLSI design; Steiner tree packing; Switchbox routing}, pages = {265 - 281}, peerreviewed = {Yes}, title = {{The} {Steiner} {Tree} {Packing} {Problem} in {VLSI}-{Design}}, volume = {78}, year = {1997} } @article{faucris.120001684, abstract = {We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to be NP-complete even on trees. In order to obtain a tractable problem, we introduce a method for generating a finite scenario set such that optimality of a sizing for this finite set implies the sizing's optimality for the originally given infinite set of scenarios. We further prove that the size of the finite scenario set is quadratically bounded above in the number of nodes of the underlying tree and that it can be computed in polynomial time. The resulting problem can then be solved as a standard mixed-integer linear optimization problem. Finally, we show the applicability of our theoretical results by computing globally optimal arc sizes for a realistic hydrogen transport network of Eastern German}, author = {Robinius, Martin and Schewe, Lars and Schmidt, Martin and Stolten, Detlef and Thürauf, Johannes and Welder, Lara}, doi = {10.1007/s10589-019-00085-x}, faupublication = {yes}, journal = {Computational Optimization and Applications}, keywords = {Discrete arc sizing; Mixed-integer linear optimization; Potential networks; Robust optimization; Scenario generation}, peerreviewed = {Yes}, title = {{Robust} optimal discrete arc sizing for tree-shaped potential networks}, year = {2019} } @misc{faucris.113664584, author = {Hiller, Benjamin and Koch, Thorsten and Pfetsch, Marc E. and Schmidt, Martin and Geißler, Björn and Henrion, René and Joormann, Imke and Martin, Alexander and Morsi, Antonio and Römisch, Werner and Schewe, Lars and Schultz, Rüdiger and Steinbach, Marc C.}, faupublication = {yes}, peerreviewed = {automatic}, title = {{Capacity} {Evaluation} for {Large}-{Scale} {Gas} {Networks}}, url = {http://www.mso.math.fau.de/fileadmin/wima/data_members/schmidt/forne-komso.pdf}, year = {2017} } @article{faucris.108441564, abstract = {We show that topological (n) point-line configurations exist for all n ≥ 17. It has been proved earlier that they do not exist for n ≤ 16. © 2008 Elsevier Ltd.}, author = {Bokowski, Jürgen and Grünbaum, Branko and Schewe, Lars}, doi = {10.1016/j.ejc.2008.12.008}, faupublication = {no}, journal = {European Journal of Combinatorics}, pages = {1778-1785}, peerreviewed = {Yes}, title = {{Topological} configurations (n4) exist for all n ≥ 17}, volume = {30}, year = {2009} } @article{faucris.123620464, abstract = {Detailed modeling of gas transport problems leads to nonlinear and nonconvex mixed-integer optimization or feasibility models (MINLPs) because both the incorporation of discrete controls of the network as well as accurate physical and technical modeling is required in order to achieve practical solutions. Hence, ignoring certain parts of the physics model is not valid for practice. In the present contribution we extend an approach based on linear relaxations of the underlying nonlinearities by tailored model reformulation techniques yielding block-separable MINLPs. This combination of techniques allows us to apply a penalty alternating direction method and thus to solve highly detailed MINLPs for large-scale real-world instances. The practical strength of the proposed method is demonstrated by a computational study in which we apply the method to instances from steady-state gas transport including both pooling effects with respect to the mixing of gases of different composition and a highly detailed compressor station mode}, author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars and Schmidt, Martin}, doi = {10.1287/ijoc.2017.0780}, faupublication = {yes}, journal = {Informs Journal on Computing}, keywords = {Nonconvex Mixed-Integer Nonlinear Optimization; Penalty Methods; Alternating Direction Methods; Block Separability; Gas Transport}, peerreviewed = {Yes}, title = {{Solving} {Highly} {Detailed} {Gas} {Transport} {MINLPs}: {Block} {Separability} and {Penalty} {Alternating} {Direction} {Methods}}, volume = {20}, year = {2018} } @article{faucris.108438484, abstract = {We introduce the coolest path problem, which is a mixture of two well-known problems from distinct mathematical fields. One of them is the shortest path problem from combinatorial optimization. The other is the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and present numerical solution techniques. We demonstrate that the problem can be formulated as a linear mixed-integer program. Numerical solutions can thus be achieved within one hour for instances with up to 70 nodes in the graph. © American Institute of Mathematical Sciences.}, author = {Frank, Martin and Fügenschuh, Armin-René and Herty, Michael and Schewe, Lars}, doi = {10.3934/nhm.2010.5.143}, faupublication = {no}, journal = {Networks and Heterogeneous Media}, keywords = {Heat equation; Integer programming; Shortest path}, pages = {143-162}, peerreviewed = {Yes}, title = {{The} coolest path problem}, volume = {5}, year = {2010} } @article{faucris.220869013, abstract = {Predicting the temporal behavior of embedded real-time systems is a crucial but challenging task, as it is with the energetic behavior of energy-constrained systems, such as IoT devices. To carry out static analyses in order to determine the worst-case execution time or the worst-case energy consumption of tasks, cost models are inevitable. However, these models are rarely available on a fine-grained level for commercial-off-the-shelf hardware platforms. In this letter, we present NEO, an end-to-end toolchain that automatically generates cost models, which are then integrated into an existing static-analysis tool. NEO exploits automatically generated benchmark programs, which are measured on the target platform and investigated in a virtual machine. Based on the gathered data, we formulate mathematical optimization problems that eventually yield both worst-case execution-time and energy-consumption cost models. In our evaluations with an embedded hardware platform (e.g., ARM Cortex-M0+), we show that the open-source toolchain is able to precisely bound programs' resources while achieving acceptable accuracy.}, author = {Sieh, Volkmar and Burlacu, Robert and Hönig, Timo and Janker, Heiko and Raffeck, Phillip and Wägemann, Peter and Schröder-Preikschat, Wolfgang}, doi = {10.1109/LES.2018.2868823}, faupublication = {yes}, journal = {IEEE Embedded Systems Letters}, note = {CRIS-Team WoS Importer:2019-06-18}, pages = {38-41}, peerreviewed = {Yes}, title = {{Combining} {Automated} {Measurement}-{Based} {Cost} {Modeling} {With} {Static} {Worst}-{Case} {Execution}-{Time} and {Energy}-{Consumption} {Analyses}}, volume = {11}, year = {2019} } @article{faucris.119629444, abstract = {The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and isothermal gas flows. The error control is realized by switching to more detailed models or finer discretizations if necessary to guarantee that a prescribed model and discretization error tolerance is satisfied in the end. We prove convergence of the adaptively controlled optimization method and illustrate the new approach with numerical example}, author = {Mehrmann, Volker and Schmidt, Martin and Stolwijk, Jeroen}, doi = {10.1007/s10013-018-0303-1}, faupublication = {yes}, journal = {Vietnam Journal of Mathematics}, keywords = {Gas transport optimization; Isothermal stationary Euler equations; Model hierarchy; Adaptive error control; Marking strategy}, peerreviewed = {Yes}, title = {{Model} and {Discretization} {Error} {Adaptivity} within {Stationary} {Gas} {Transport} {Optimization}}, url = {http://www.optimization-online.org/DB_HTML/2017/12/6365.html}, year = {2018} } @article{faucris.204075926, author = {Grimm, Veronika and Schewe, Lars and Schmidt, Martin and Zöttl, Gregor}, doi = {10.1007/s00186-018-0647-z}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, peerreviewed = {Yes}, title = {{A} multilevel model of the {European} entry-exit gas market}, year = {2018} } @incollection{faucris.122515844, abstract = {

We introduce the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory. Although the Simultaneous Approximation Problem (SAP) is already known in cryptography, it has mainly been considered in its *homogeneous* instantiation for *attacking* schemes. We take a look at the hardness and applicability of ISAP, i.e., the *inhomogeneous* variant, for *designing* schemes.

More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. With respect to its hardness, we review existing approaches for solving related problems and give suggestions for the efficient generation of hard instances. Regarding the applicability, we describe as a proof of concept a bit commitment scheme where the hiding property is directly reducible to DISAP. An implementation confirms its usability in principle (e.g., size of one commitment is 6273 bits and execution time is in the milliseconds).

}, author = {Armknecht, Frederik and Elsner, Carsten and Schmidt, Martin}, booktitle = {Progress in Cryptology – AFRICACRYPT 2011}, doi = {10.1007/978-3-642-21969-6_15}, editor = {Nitaj A, Pointcheval D}, faupublication = {no}, isbn = {978-3-642-21968-9}, pages = {242-259}, peerreviewed = {Yes}, publisher = {Springer Berlin / Heidelberg}, series = {Lecture Notes in Computer Science}, title = {{Using} the {Inhomogeneous} {Simultaneous} {Approximation} {Problem} for {Cryptographic} {Design}}, volume = {6737}, year = {2011} } @inproceedings{faucris.120590404, abstract = {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. In the Gurobi commercial mixed-integer solver, the presolve functionality has been steadily enhanced over time, now including a number of so-called multi-row reductions. These are reductions that simultaneously consider multiple constraints to derive improvements in the model formulation. In this paper we give an overview of such multi-row techniques and present computational results to assess their impact on overall solver performance.}, author = {Achterberg, Tobias and Bixby, Robert E. and Gu, Zonghao and Rothberg, Edward and Weninger, Dieter}, booktitle = {Proceedings of the Twenty-Sixth RAMP Symposium}, date = {2014-10-16/2014-10-17}, editor = {Hosei University, Tokyo}, faupublication = {yes}, keywords = {Mixed Integer Programming, Presolving, Gurobi}, pages = {181-196}, peerreviewed = {unknown}, title = {{Multi}-{Row} {Presolve} {Reductions} in {Mixed} {Integer} {Programming}}, url = {http://www.orsj.or.jp/ramp/2014/paper/4-4.pdf}, venue = {Tokyo}, year = {2014} } @incollection{faucris.115720924, abstract = {We introduce a mixed integer linear modeling approach for the optimization of dynamic water supply networks based on the piecewise linearization of nonlinear constraints. One advantage of applying mixed integer linear techniques is that these methods are nowadays very mature, that is, they are fast, robust, and are able to solve problems with up to a huge number of variables. The other major point is that these methods have the potential of finding globally optimal solutions or at least to provide guarantees of the solution quality. We demonstrate the applicability of our approach on examples networks.}, author = {Morsi, Antonio and Geißler, Björn and Martin, Alexander}, booktitle = {Mathematical Optimization of Water Networks}, faupublication = {yes}, pages = {35 -- 54}, peerreviewed = {Yes}, publisher = {Birkhäuser}, series = {International Series of Numerical Mathematics}, title = {{Mixed} {Integer} {Optimization} of {Water} {Supply} {Networks}}, volume = {162}, year = {2012} } @inproceedings{faucris.120545084, address = {Darmstadt}, author = {Martin, Alexander}, booktitle = {Suffizienz in der Baukultur: Besser, Anders, Weniger}, editor = {U.~Kunkel}, faupublication = {yes}, pages = {18 -- 19}, peerreviewed = {No}, publisher = {Konradin Medien GmbH}, series = {db-{Kongress} 2014}, title = {{Diskrete} {Optimierung} als {Anregung} für {Suffizienz}-{Strategien}}, year = {2014} } @article{faucris.115737204, abstract = {Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the optimal linear outer-approximation approach by Ben-Tal and Nemirovski (Math Oper Res 26:193--205, 2001) from which we derive an optimal inner approximation of the second-order cone. We examine the performance of this approach on various benchmark sets including portfolio optimization instances as well as (robustified versions of) the MIPLIB and the SNDlib.}, author = {Bärmann, Andreas and Heidt, Andreas and Martin, Alexander and Pokutta, Sebastian and Thurner, Christoph}, doi = {10.1007/s10287-015-0243-0}, faupublication = {yes}, journal = {Computational Management Science}, keywords = {Robust optimization; Approximation; Extended formulations; Second-order cone optimization; Mixed-integer programming; Portfolio optimization; 90C31; 90C59; 90C20; 90C11}, pages = {151-193}, peerreviewed = {Yes}, title = {{Polyhedral} approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study}, volume = {13}, year = {2015} } @incollection{faucris.108917204, abstract = {In this chapter we compare continuous nonlinear optimization with mixed integer optimization of water supply networks by means of a meso scaled network instance. We introduce a heuristic approach, which handles discrete decisions arising in water supply network optimization through penalization using nonlinear programming. We combine the continuous nonlinear and the mixed integer approach introduced in Chap. 3 to incorporate the solution quality. Finally, we show results for a real municipal water supply network.}, author = {Kolb, Oliver and Morsi, Antonio and Lang, Jens and Martin, Alexander}, booktitle = {Mathematical Optimization of Water Networks}, editor = {A. Martin; K. Klamroth; J. Lang; G. Leugering; A. Morsi; M. Oberlack; M. Ostrowski; R. Rosen}, faupublication = {yes}, pages = {55 -- 65}, peerreviewed = {Yes}, publisher = {Birkhäuser}, series = {International Series of Numerical Mathematics}, title = {{Nonlinear} and {Mixed} {Integer} {Linear} {Programming}}, volume = {162}, year = {2012} } @incollection{faucris.123286284, abstract = {The runway system is the main element that combines airside and groundside of the ATM System. Efficient models and planning algorithms are required. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real word. This often happens because the input data of the planning algorithms is disturbed respectively it changes. For example, an estimated time of an aircraft is not stable for the next ten hours. These disturbances are not deterministic, but often their stochastic distributions with mean values and standard deviations are known. We present a robust model together with an optimization algorithm which explicitly incorporates the knowledge of uncertainty into each planning step. Our approach transforms the planning problem into an assignment problem with side constraints. We compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Experimentally, we show that running times are better than when using a different non-linear integer optimization model. Our Monte-Carlo simulation for a mixed-mode runway system shows that our approach results in fewer sequence changes and target time updates compared to the usual approach of just updating the plan if the actual plan is not feasible any more.

}, author = {Heidt, Andreas and Helmke, Hartmut and Liers, Frauke and Martin, Alexander}, booktitle = {Proceedings of the SESAR Innovation Days 2014}, editor = {D.~Schäfer}, faupublication = {yes}, isbn = {978-2-87497-077-1}, keywords = {scheduling, uncertainty, time-indexed model, MIP, mixed-integer programming, dynamic time-indexed model, mixed mode runway scheduling}, peerreviewed = {unknown}, title = {{Robust} {Runway} {Scheduling} using a time-indexed model}, year = {2014} } @misc{faucris.122817024, author = {Bokowski, Jürgen and Martin, Alexander}, faupublication = {no}, peerreviewed = {automatic}, title = {{Egoisten} schaden sich selbst}, year = {2002} } @article{faucris.106842604, abstract = {We present various methods that have reduced the finite set of missing geometric configurations (). We show that there is no geometric configuration (17), and we provide examples for the former unknown cases n=18, n=29, n=31 - there do exist geometric configurations (). To construct these we use methods from computer algebra and optimization.}, author = {Bokowski, Jürgen and Schewe, Lars}, doi = {10.1016/j.comgeo.2011.11.001}, faupublication = {yes}, journal = {Computational Geometry-Theory and Applications}, keywords = {Geometric point line configuration; Oriented matroid; Projective incidence theorem; Pseudoline; Realization space}, pages = {532-540}, peerreviewed = {Yes}, title = {{On} the finite set of missing geometric configurations (n4)}, volume = {46}, year = {2013} } @article{faucris.118445404, abstract = {Let Δ(d, n) be the maximum possible diameter of the vertex-edge graph over all d-dimensional polytopes defined by n inequalities. The Hirsch bound holds for particular n and d if Δ(d, n)≤n-d. Francisco Santos recently resolved a question open for more than five decades by showing that Δ(d, 2d)≥d+1 for d=43; the dimension was then lowered to 20 by Matschke, Santos and Weibel. This progress has stimulated interest in related questions. The existence of a polynomial upper bound for Δ(d, n) is still an open question, the best bound being the quasi-polynomial one due to Kalai and Kleitman in 1992. Another natural question is for how large n and d the Hirsch bound holds. Goodey showed in 1972 that Δ(4, 10)=5 and Δ(5, 11)=6, and more recently, Bremner and Schewe showed that Δ(4, 11)=Δ(6, 12)=6. Here, we show that Δ(4, 12)=Δ(5, 12)=7. © 2013 Copyright Taylor and Francis Group, LLC.}, author = {Bremner, David and Deza, Antoine and Hua, William and Schewe, Lars}, doi = {10.1080/10556788.2012.668906}, faupublication = {yes}, journal = {Optimization Methods & Software}, keywords = {combinatorics; convex polytopes; discrete geometry; linear optimization; pivoting methods}, pages = {442-450}, peerreviewed = {Yes}, title = {{More} bounds on the diameters of convex polytopes}, volume = {28}, year = {2013} } @incollection{faucris.123585484, author = {Handschin, Edmund and Waniek, Daniel and Martin, Alexander and Mahlke, Debora and Zelmer, Andrea}, booktitle = {Optimierung in der Energiewirtschaft, VDI-Berichte Nr. 2018}, faupublication = {no}, pages = {133 -- 146}, peerreviewed = {Yes}, title = {{Gekoppelte} optimale {Auslegung} von {Strom}-, {Gas}- und {Wärmenetzen}}, year = {2007} } @article{faucris.117696524, abstract = {When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to nonconvex mixed-integer nonlinear optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several continuous reformulations of the problem. The applicability and relevance of different model formulations, especially of those without discrete variables, is demonstrated by a computational study on both academic examples and real-world instances. In addition, we provide preliminary computational results for an entire network.}, author = {Rose, Daniel and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, doi = {10.1007/s00186-016-0533-5}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, keywords = {Discrete-continuous nonlinear optimization; Gas networks; Gas compressor stations; Mixed-integer optimization; Continuous reformulations}, pages = {409--444}, peerreviewed = {Yes}, title = {{Computational} optimization of gas compressor stations: {MINLP} models versus continuous reformulations}, url = {http://www.optimization-online.org/DB_HTML/2h015/02/4793.html}, volume = {83}, year = {2016} } @incollection{faucris.115702224, author = {Geißler, Björn and Martin, Alexander and Morsi, Antonio and Schewe, Lars}, booktitle = {Optimierung in der Energiewirtschaft}, faupublication = {yes}, pages = {127 -- 138}, peerreviewed = {Yes}, series = {VDI-Berichte 2157}, title = {{Optimale} {Schaltentscheidungen} für {Gasnetze}}, year = {2011} } @article{faucris.115645684, abstract = {We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.}, author = {Bixby, Robert E. and Martin, Alexander}, faupublication = {no}, journal = {Informs Journal on Computing}, keywords = {Dual simplex algorithm; Parallelization}, pages = {45 -- 56}, peerreviewed = {Yes}, title = {{Parallelizing} the {Dual} {Simplex} {Method}}, volume = {12}, year = {2000} } @article{faucris.119464224, abstract = {We consider optimal control problems for gas flow in pipeline networks. The equations of motion are taken to be represented by a first-order system of hyperbolic semilinear equations derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a network and introduce a tailored time discretization thereof. In order to further reduce the complexity, we consider an instantaneous control strategy. The main part of the paper is concerned with a nonoverlapping domain decomposition of the optimal control problem on the graph into local problems on smaller sub-graphs - ultimately on single edges. We prove convergence of the domain decomposition method on networks and study the wellposedness of the corresponding time-discrete optimal control problems. The point of the paper is that we establish virtual control problems on the decomposed subgraphs such that the corresponding optimality systems are in fact equal to the systems obtained via the domain decomposition of the entire optimality system.}, author = {Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias}, faupublication = {yes}, journal = {Control and Cybernetics}, keywords = {Optimal control; Gas networks; Euler's equation; Semilinear PDE; Nonoverlapping domain decomposition}, pages = {191-225}, peerreviewed = {Yes}, title = {{Nonoverlapping} {Domain} {Decomposition} for {Optimal} {Control} {Problems} governed by {Semilinear} {Models} for {Gas} {Flow} in {Networks}}, volume = {46}, year = {2017} } @article{faucris.115641064, author = {Martin, Alexander}, faupublication = {no}, journal = {Mathematical Methods of Operations Research}, pages = {277 -- 284}, peerreviewed = {Yes}, title = {{A} polynomially solvable case of the separation problem for the {Steiner} partition inequalities}, volume = {62}, year = {1990} } @article{faucris.106528664, abstract = {Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems.}, author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars and Schmidt, Martin}, doi = {10.1137/16M1069687}, faupublication = {yes}, journal = {SIAM Journal on Optimization}, keywords = {Mixed-Integer Nonlinear Optimization; Mixed-Integer Linear Optimization; Feasibility Pump; Alternating Direction Methods; Penalty Methods}, pages = {1611-1636}, peerreviewed = {Yes}, title = {{Penalty} {Alternating} {Direction} {Methods} for {Mixed}-{Integer} {Optimization}: {A} {New} {View} on {Feasibility} {Pumps}}, url = {http://www.optimization-online.org/DB_HTML/2016/04/5399.html}, volume = {27}, year = {2017} } @article{faucris.106159284, abstract = {In this paper a combined optimization of a coupled electricity and gas system is presented. For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool, considering all system operational and unit technical constraints is solved. The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem. The coupling constraints between the two networks are nonlinear as well. The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique. The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels. The results indicate the efficiency of the proposed mixed-integer linear program model and the interplay between computational requirements and accuracy.}, author = {Sirvent, Mathias and Kanelakis, Nikolaos and Geißler, Björn and Biskas, Pandelis}, doi = {10.1007/s40565-017-0275-2}, faupublication = {yes}, journal = {Journal of Modern Power Systems and Clean Energy}, pages = {364 - 374}, peerreviewed = {Yes}, title = {{A} {Linearized} {Model} for the {Optimization} of the {Coupled} {Electricity} and {Natural} {Gas} {System}}, url = {https://link.springer.com/article/10.1007%2Fs40565-017-0275-2}, volume = {5}, year = {2017} } @article{faucris.108957244, abstract = {Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design yields welfare-optimal outcomes. This problem leads to a challenging multilevel model that contains a graph-partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. These methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as on realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformatio}, author = {Grimm, Veronika and Kleinert, Thomas and Liers, Frauke and Schmidt, Martin and Zöttl, Gregor}, doi = {10.1080/10556788.2017.1401069}, faupublication = {yes}, journal = {Optimization Methods & Software}, keywords = {Multilevel Optimization; Mixed-Integer Nonlinear Optimization; Graph Partitioning; Generalized Benders Decomposition; Electricity Market Design}, pages = {406-436}, peerreviewed = {Yes}, title = {{Optimal} price zones in electricity markets: a mixed-integer multilevel model and global solution approaches}, url = {http://www.optimization-online.org/DB_HTML/2017/01/5799.html}, volume = {34}, year = {2019} } @article{faucris.109857264, author = {Martin, Alexander and Müller, Johannes and Pokutta, Sebastian}, faupublication = {yes}, journal = {Optimization Methods and Software}, pages = {189 -- 221}, peerreviewed = {Yes}, title = {{Strict} {Linear} {Prices} in {Non}-{Convex} {European} {Day}-{Ahead} {Electricity} {Markets}}, volume = {29}, year = {2014} } @incollection{faucris.123293984, abstract = {Discrete, nonlinear and PDE constrained optimization are mostly considered as different fields of mathematical research. Nevertheless many real-life problems are most naturally modeled as PDE constrained mixed integer nonlinear programs. For example, nonlinear network flow problems where the flow dynamics are governed by a transport equation are of this type. We present four different applications together with the derivation of the associated transport equations and we show how to model these problems in terms of mixed integer linear constraints.}, address = {Dagstuhl, Germany}, author = {Fügenschuh, Armin-René and Geißler, Björn and Martin, Alexander and Morsi, Antonio}, booktitle = {Models and Algorithms for Optimization in Logistics}, editor = {Cynthia Barnhart; Uwe Clausen; Ulrich Lauther; Rolf H. Möhring}, faupublication = {no}, keywords = {Transport Equation; Partial Differential Equation; Mixed-Integer Linear Programming; Modeling; Nonlinear Constraints}, peerreviewed = {No}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, series = {Dagstuhl Seminar Proceedings}, title = {{The} {Transport} {PDE} and {Mixed}-{Integer} {Linear} {Programming}}, url = {http://drops.dagstuhl.de/opus/volltexte/2009/2167}, volume = {09261}, year = {2009} } @article{faucris.111112144, abstract = {Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s.}, author = {Schewe, Lars and Schmidt, Martin}, doi = {10.1007/s12532-018-0141-x}, faupublication = {yes}, journal = {Mathematical Programming Computation}, keywords = {Mixed-Integer Nonlinear Optimization, MINLP, MPEC, Complementarity Constraints, Primal Heuristic.}, peerreviewed = {unknown}, title = {{Computing} {Feasible} {Points} for {Binary} {MINLPs} with {MPECs}}, url = {http://www.optimization-online.org/DB_HTML/2016/12/5778.html}, year = {2018} } @book{faucris.115716084, abstract = {Water supply- and drainage systems and mixed water channel systems are networks whose high dynamic is determined and/or affected by consumer habits on drinking water on the one hand and by climate conditions, in particular rainfall, on the other hand. According to their size, water networks consist of hundreds or thousands of system elements. Moreover, different types of decisions (continuous and discrete) have to be taken in the water management. The networks have to be optimized in terms of topology and operation by targeting a variety of criteria. Criteria may for example be economic, social or ecological ones and may compete with each other. The development of complex model systems and their use for deriving optimal decisions in water management is taking place at a rapid pace. Simulation and optimization methods originating in Operations Research have been used for several decades; usually with very limited direct cooperation with applied mathematics. The research presented here aims at bridging this gap, thereby opening up space for synergies and innovation. It is directly applicable for relevant practical problems and has been carried out in cooperation with utility and dumping companies, infrastructure providers and planning offices. A close and direct connection to the practice of water management has been established by involving application-oriented know-how from the field of civil engineering. On the mathematical side all necessary disciplines were involved, including mixed-integer optimization, multi-objective and facility location optimization, numerics for cross-linked dynamic transportation systems and optimization as well as control of hybrid systems. Most of the presented research has been supported by the joint project "Discret continuous optimization of dynamic water systems" of the federal ministry of education and research (BMBF).}, author = {Martin, Alexander and Klamroth, Kathrin and Lang, Jens and Leugering, Günter and Morsi, Antonio and Oberlack, Martin and Ostrowski, Manfred and Rosen, Roland}, faupublication = {yes}, peerreviewed = {Yes}, publisher = {Birkhäuser}, series = {International Series of Numerical Mathematics}, title = {{Mathematical} {Optimization} of {Water} {Networks}}, volume = {162}, year = {2012} } @inproceedings{faucris.119872104, address = {Düsseldorf}, author = {Steber, David and Seifert, Gaby and Thurner, Christoph and Pruckner, Marco and Luther, Matthias and Martin, Alexander and German, Reinhard}, booktitle = {VDI-Berichte 2303}, date = {2017-11-08/2017-11-09}, editor = {VDI Wissensforum GmbH}, faupublication = {yes}, isbn = {978-3-18-092303-1}, pages = {3-16}, peerreviewed = {No}, publisher = {VDI Verlag GmbH}, title = {{KOSiNeK} - {Kombinierte} {Optimierung}, {Simulation} und {Netzanalyse} des elektrischen {Energiesystems} {Deutschlands} im europäischen {Kontext} - {Projektvorstellung} und erste {Ergebnisse}}, venue = {Würzburg}, year = {2017} } @incollection{faucris.123593624, abstract = {Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert.}, address = {Düsseldorf}, author = {Martin, Alexander and Geißler, Björn and Hayn, Christine and Morsi, Antonio and Schewe, Lars and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Schwarz, Robert and Schweiger, Jonas and Pfetsch, Marc E. and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M. and Schultz, Rüdiger}, booktitle = {Optimierung in der Energiewirtschaft}, faupublication = {yes}, pages = {105-114}, peerreviewed = {Yes}, publisher = {VDI-Verlag}, series = {VDI-Berichte 2157}, title = {{Optimierung} {Technischer} {Kapazitäten} in {Gasnetzen}}, year = {2011} } @incollection{faucris.108907964, author = {Fügenschuh, Armin-René and Hess, Wolfgang and Martin, Alexander and Ulbrich, Stefan}, booktitle = {Tagungsband 1. Zwischenkolloqium SFB 666}, editor = {P. Groche}, faupublication = {no}, pages = {37 -- 47}, peerreviewed = {unknown}, publisher = {Meisenbach Verlag, Bamberg}, title = {{Diskrete} und kontinuierliche {Modelle} zur {Topologie}- und {Geometrie}-{Optimierung} von {Blechprofilen}}, year = {2007} } @incollection{faucris.122514964, abstract = {In this chapter we describe a highly detailed nonlinear program (NLP) of gas networks for the case of fixed discrete decisions. By including nonlinear physics and a detailed description of the technical network devices, a level of accuracy is reached that is comparable to current commercial simulation software. Our NLP model is used to validate the solutions of the previously described models. A successful validation provides a solution of the underlying mixed-integer nonlinear program (MINLP).}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch10}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {181-210}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{The} precise {NLP} model}, year = {2015} } @inproceedings{faucris.120402084, author = {Martin, Alexander and Müller, Johannes and Pokutta, Sebastian}, booktitle = {23rd Australasian Finance and Banking Conference 2010}, faupublication = {yes}, peerreviewed = {Yes}, title = {{On} {Clearing} {Coupled} {Day}-{Ahead} {Electricity} {Markets}}, url = {http://ssrn.com/abstract=1660528}, year = {2010} } @misc{faucris.216343173, abstract = {One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem is as hard as solving the original bilevel problem.G = (

}, author = {Krebs, Vanessa and Schmidt, Martin}, doi = {10.1016/j.orp.2018.05.002}, faupublication = {yes}, journal = {Operations Research Perspectives}, keywords = {Market Equilibria; Networks; Transport Costs; Uniqueness; Perfect Competition}, pages = {169-173}, peerreviewed = {Yes}, title = {{Uniqueness} of {Market} {Equilibria} on {Networks} with {Transport} {Costs}}, url = {http://www.sciencedirect.com/science/article/pii/S2214716018300319}, volume = {5}, year = {2018} } @article{faucris.108899824, author = {Martin, Alexander and et al.}, author_hint = {A.~Martin, R.~Weismantel}, faupublication = {no}, pages = {185 -- 204}, peerreviewed = {Yes}, support_note = {Author relations incomplete. You may find additional data in field 'author_hint'}, title = {{Packing} {Paths} and {Steiner} {Trees}: {Routing} of {Electronic} {Circuits}}, volume = {6}, year = {1993} } @misc{faucris.217929705, abstract = {For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. To the best of our knowledge, the approaches for the RRF presented in the literature are restricted to continuous optimization problems. In this work, we first analyze relations between the RRF of a MIP and its continuous linear programming relaxation. In particular, we derive conditions under which a MIP and its continuous relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied and computed for a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the concept of the RRF to MIPs including “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In this extended setting, we again analyze relations between the RRF for a MIP and its continuous relaxation. Afterward, we present methods for computing the RRF for continuous linear as well as mixed-integer problems with safe constraints and variables. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 library for the calculation of the RR}, author = {Liers, Frauke and Schewe, Lars and Thürauf, Johannes}, faupublication = {yes}, keywords = {Robust Optimization; Mixed-integer programming; Uncertainty sets; Robust feasibility}, peerreviewed = {automatic}, title = {{Radius} of {Robust} {Feasibility} for {Mixed}-{Integer} {Problems}}, url = {http://www.optimization-online.org/DB_HTML/2019/05/7219.html}, year = {2019} } @incollection{faucris.122314984, abstract = {

The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.

}, author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch12}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {233-270}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{Computational} results for validation of nominations}, year = {2015} } @article{faucris.118074924, author = {Grimm, Veronika and Martin, Alexander and Weibelzahl, Martin and Zöttl, Gregor}, doi = {10.1016/j.enpol.2015.11.010}, faupublication = {yes}, journal = {Energy Policy}, pages = {453-467}, peerreviewed = {No}, title = {{On} the long run effects of market splitting: {Why} more price zones might decrease welfare}, volume = {94}, year = {2016} } @incollection{faucris.115669224, author = {Günther, Ute and Martin, Alexander and Ritter, Klaus and Wagner, Tim}, booktitle = {PAMM, Proceedings of Applied Mathematics and Mechanics}, faupublication = {no}, pages = {667 - 668}, peerreviewed = {unknown}, title = {{Cash} {Recycling} {Systems}: {Prediction} and {Optimization}}, volume = {6}, year = {2006} } @article{faucris.118445624, abstract = {In this article, we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult non-convex mixed-integer nonlinear feasibility problem. The first phase consists of four distinct algorithms applying mixed-integer linear, mixed-integer nonlinear, nonlinear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high-quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.}, author = {Pfetsch, Marc E. and Fügenschuh, Armin and Geißler, Björn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and Rövekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, Rüdiger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc C. and Vigerske, Stefan and Willert, Bernhard M.}, doi = {10.1080/10556788.2014.888426}, faupublication = {yes}, journal = {Optimization Methods and Software}, keywords = {gas network optimization; gas transport optimization; mixed-integer nonlinear programming; nomination}, pages = {15-53}, peerreviewed = {Yes}, title = {{Validation} of nominations in gas network optimization: {Models}, methods, and solutions}, volume = {30}, year = {2015} } @incollection{faucris.123275504, address = {Berlin Heidelberg}, author = {Leugering, Günter and Martin, Alexander and Stingl, Michael}, booktitle = {Produktionsfaktor Mathematik - Wie Mathematik Technik und Wirtschaft Bewegt}, doi = {10.1007/978-3-540-89435-3_14}, editor = {Martin Grötschel, Klaus Lucas, Volker Mehrmann}, faupublication = {yes}, pages = {323-338}, peerreviewed = {unknown}, publisher = {Springer}, title = {{Topologie} und {Dynamische} {Netzwerke}: {Anwendungen} {Der} {Optimierung} {MIT} {Zukunft}}, year = {2009} } @article{faucris.115667024, abstract = {This paper reports on the fourth version of the Mixed Integer Programming Library. Since MIPLIB is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.}, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, doi = {10.1016/j.orl.2005.07.009}, faupublication = {no}, journal = {Operations Research Letters}, keywords = {IP; MIP; MIPLIB; Mixed Integer Programming; Problem instances}, pages = {1--12}, peerreviewed = {Yes}, title = {{MIPLIB} 2003}, volume = {34}, year = {2006} } @incollection{faucris.115696504, author = {Göllner, Thea and Günther, Ute and Hess, Wolfgang and Martin, Alexander and Ulbrich, Stefan}, booktitle = {Tagungsband 3. Zwischenkolloqium SFB 666}, editor = {P. Groche}, faupublication = {yes}, pages = {25 -- 32}, peerreviewed = {No}, publisher = {Meisenbach Verlag, Bamberg}, title = {{Form}- und {Topologieoptimierung} verzweigter {Blechbauteile}}, year = {2010} } @incollection{faucris.111139424, abstract = {We consider optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St. Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique.}, address = {Singapore}, author = {Hante, Falk and Leugering, Günter and Martin, Alexander and Schewe, Lars and Schmidt, Martin}, booktitle = {Industrial Mathematics and Complex Systems: Emerging Mathematical Models, Methods and Algorithms}, doi = {10.1007/978-981-10-3758-0_5}, editor = {Manchanda, Pammy; Lozi, René; Siddiqi, Abul Hasan}, faupublication = {yes}, isbn = {978-981-10-3758-0}, keywords = {Networks, pipes, canals, Euler and St. Venant equations, hierarchy of models, domain decomposition, controllability, optimal control.}, pages = {77-122}, peerreviewed = {unknown}, publisher = {Springer Singapore}, series = {Industrial and Applied Mathematics}, title = {{Challenges} in {Optimal} {Control} {Problems} for {Gas} and {Fluid} {Flow} in {Networks} of {Pipes} and {Canals}: {From} {Modeling} to {Industrial} {Applications}}, url = {https://opus4.kobv.de/opus4-trr154/files/121/isiam-paper.pdf}, year = {2017} } @article{faucris.111112364, abstract = {We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with "black-box" nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinearity. We prove that our algorithm finitely terminates with an approximate feasible global optimal solution of the mixed-integer nonlinear problem. Additionally, we show the applicability of our approach by three case studies from mixed-integer optimal control, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter we also present promising numerical results of our method applied to real-world instance}, author = {Gugat, Martin and Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias and Wintergerst, David}, doi = {10.1002/net.21812}, faupublication = {yes}, journal = {Networks}, keywords = {Mixed-Integer Optimization, Simulation Based Optimization, Optimization with Differential Equations, Decomposition Method, Gas Transport Networks.}, pages = {60-83}, peerreviewed = {Yes}, title = {{Towards} {Simulation} {Based} {Mixed}-{Integer} {Optimization} with {Differential} {Equations}}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21812}, volume = {72}, year = {2018} } @inproceedings{faucris.203351645, abstract = {This article summarizes the findings of my Ph.D. thesis finished in 2015, whose topic are algorithmic approaches for the solution of network design problems. I focus on the results of a joint project with Deutsche Bahn AG on developing an optimal expansion strategy for the German railway network until 2030 to meet future demands. I have modelled this task as a multi-period network design problem and have derived an efficient decomposition approach to solve it. In a case study on real-world data on the German railway network, I demonstrate both the efficiency of by method as well as the high quality of the solutions it computes.}, address = {Cham}, author = {Bärmann, Andreas}, booktitle = {Operations Research Proceedings 2016}, editor = {Fink A, Fügenschuh A, Geiger MJ}, faupublication = {yes}, isbn = {978-3-319-55702-1}, pages = {3--8}, peerreviewed = {unknown}, publisher = {Springer International Publishing}, title = {{An} {Optimal} {Expansion} {Strategy} for the {German} {Railway} {Network} {Until} 2030}, year = {2018} } @incollection{faucris.120543324, abstract = {This paper presents an approach to designing multi-chambered profile structures made by a new manufacturing process called linear flow splitting using an algorithm based approach. The basis for this procedure is a systematic view of product properties and the separation of its internal and external properties. The link between product properties must be derived by design knowledge such as physical models or guidelines. This specific knowledge enables one to decide which internal properties, as optimization parameters, need to be adjusted in order to meet desired external properties. This procedure leads to mathematical problems that are difficult to solve, presenting a challenge for research. This approach is demonstrated with an example of a development assignment seeking a topology of a profile structure consisting of several chambers.}, author = {Wäldele, Martin and Birkhofer, Herbert and Fuegenschuh, Armin and Martin, Alexander}, booktitle = {Research into Design: Supporting Multiple Facets of Product Development}, editor = {A. Chakrabarti}, faupublication = {no}, keywords = {Algorithm-based design; Product properties; Optimization; Sheet metal}, pages = {287 -- 294}, peerreviewed = {Yes}, publisher = {Research Publishing}, title = {{Modeling} {Properties} for the {Design} of {Branched} {Sheet} {Metal} {Products}}, year = {2009} } @phdthesis{faucris.106528884, author = {Schewe, Lars}, faupublication = {no}, peerreviewed = {automatic}, school = {Friedrich-Alexander-Universität Erlangen-Nürnberg}, title = {{Satisfiability} {Problems} in {Discrete} {Geometry} ({Berichte} aus der {Mathematik})}, year = {2007} } @incollection{faucris.122210264, abstract = {

The main goal of our efforts described in this book consists of solving the problem of validation of nominations in gas networks, i.e., deciding whether a feasible solution exists for a given set of boundary conditions represented by a nomination. However, it turns out that the meaning of “feasible” is not self-evident. This is due to a multitude of reasons, ranging from the accuracy of problem data over subtle differences between our models to tractability of optimization problems. In the current chapter we elaborate on these points and try to clarify precisely in what sense and how well the mathematical methodology presented can distinguish feasible from infeasible solutions.

}, author = {Joormann, Imke and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch11}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {211-232}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{What} does “feasible” mean?}, year = {2015} } @article{faucris.117698284, abstract = {Many real-world optimization models comprise nonconvex and nonsmooth functions leading to very hard classes of optimization models. In this article, a new interior-point method for the special, but practically relevant class of optimization problems with locatable and separable nonsmooth aspects is presented. After motivating and formalizing the problems under consideration, modifications and extensions to a standard interior-point method for nonlinear programming are investigated to solve the introduced problem class. First theoretical results are given and a numerical study is presented that shows the applicability of the new method for real-world instances from gas network optimization.}, author = {Schmidt, Martin}, doi = {10.1007/s13675-015-0039-6}, faupublication = {yes}, journal = {EURO Journal on Computational Optimization}, keywords = {Interior-point methods; Barrier methods; Line-search methods; Nonlinear and nonsmooth optimization; Classification of optimization models; Gas network optimization; 90C30; 90C51; 90C90; 90C35; 90C56; 90B10}, pages = {309-348}, peerreviewed = {No}, title = {{An} interior-point method for nonlinear optimization problems with locatable and separable nonsmoothness}, volume = {3}, year = {2015} } @article{faucris.118144224, abstract = {In this work, we report about the results of a joint research project between Friedrich–Alexander–Universität Erlangen–Nürnberg and Deutsche Bahn AG on the optimal expansion of the German railway network until 2030. The need to increase the throughput of the network is given by company-internal demand forecasts that indicate an increase in rail freight traffic of about 50% over the next two decades. Our focus is to compute an optimal investment strategy into line capacities given an available annual budget, i.e., we are to choose the most profitable lines to upgrade with respect to the demand scenario under consideration and to provide a schedule according to which the chosen measures are implemented. This leads to a multiperiod network design problem—a class of problems that has received increasing interest over the past decade. We develop a mixed-integer programming formulation to model the situation and solve it via a novel decomposition approach that we call multiple-knapsack decomposition. The method can both be used as a quick heuristic and allows for the extension to an exact algorithm for the problem. We demonstrate its potential by solving a real-world problem instance provided by Deutsche Bahn AG and use the results as the basis for a broad case study for the expansion of the German railway network until 2030.}, author = {Bärmann, Andreas and Martin, Alexander and Schuelldorf, Hanno}, doi = {10.1287/trsc.2017.0747}, faupublication = {yes}, journal = {Transportation Science}, keywords = {railway transport; multiperiod network design; decomposition; infrastructure planning; mixed-integer programming}, peerreviewed = {Yes}, title = {{A} {Decomposition} {Method} for {Multiperiod} {Railway} {Network} {Expansion} - {With} a {Case} {Study} for {Germany}}, year = {2017} } @article{faucris.117575744, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called bordered block diagonal form. More precisely, given some matrix A, we try to assign as many rows as possible to some number β of blocks of size script K such that no two rows as signed to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the linear programming and mixed integer programming libraries Netlib and Miplib can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.}, author = {Borndörfer, Ralf and E. Ferreira, Carlos and Martin, Alexander}, faupublication = {no}, journal = {SIAM Journal on Optimization}, keywords = {Block structure of a sparse matrix; Cutting planes; Integer programming; Matrix decomposition; Polyhedral combinatorics}, pages = {236 -- 269}, peerreviewed = {Yes}, title = {{Decomposing} {Matrices} into {Blocks}}, volume = {9}, year = {1998} } @incollection{faucris.119107824, abstract = {Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.}, author = {Borndörfer, Ralf and Hoang, Nam Dung and Karbstein, Marika and Koch, Thorsten and Martin, Alexander}, booktitle = {Facets of Combinatorial Optimization}, editor = {Michael JÜnger and Gerhard Reinelt}, faupublication = {yes}, pages = {215--244}, peerreviewed = {Yes}, publisher = {Springer}, title = {{How} {Many} {Steiner} {Terminals} {Can} {You} {Connect} in 20 {Years}?}, year = {2013} } @misc{faucris.121873444, author = {Martin, Alexander}, faupublication = {no}, peerreviewed = {automatic}, title = {{Integer} programs with block structure}, year = {1999} } @inproceedings{faucris.119104304, abstract = {Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. The integer variant (QIP) is PSPACE-complete, and the problem is similar to games like chess, where an existential and a universal player have to play a two-person-zero sum game. At the same time, a QLP with n variables is a variant of a linear program living in , and it has strong similarities with multi-stage stochastic linear programs with variable right-hand side. Our interest in QLPs stems from the fact that they are LP-relaxations of QIPs, which themselves are mighty modeling tools. In order to solve QLPs, we apply a nested decomposition algorithm. In a detailed computational study, we examine, how different structural properties like the number of universal variables, the number of universal variable blocks as well as their positions in the QLP influence the solution process.}, author = {Ederer, Thorsten and Lorenz, Ulf and Martin, Alexander and Wolf, Jan}, booktitle = {Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings}, doi = {10.1007/978-3-642-23719-5}, editor = {C. Demetrescu, M. Halldórsson}, faupublication = {yes}, isbn = {978-3-642-23718-8}, pages = {203 -- 214}, peerreviewed = {Yes}, series = {Lecture Notes in Computer Science}, title = {{Quantified} {Linear} {Programs}: {A} {Computational} {Study}}, volume = {6942}, year = {2011} } @incollection{faucris.123294864, abstract = {In many rural areas, the public bus service is demand-oriented: By far the biggest group of customers are pupils who are transported to their schools within certain strict time limits. Usually, all schools start around the same time, which causes a morning peak in the number of deployed buses. However, schools are allowed to change their starting times within some interval. The question is, how to simultanenously rectify the starting times for all schools and bus trips in a certain county so that the number of scheduled buses is minimal. This problem can be formulated as a vehicle routing problem with coupled time windows (VRP-CTW), which is an extension of the vehicle routing problem with time windows (VRP-TW), where additional coupling constraints on the time windows are introduced. We give a mixed-integer programming formulation for VRP-CTW, and present solutions and lower bounds for randomly generated and real-world instances.}, author = {Fügenschuh, Armin-René and Martin, Alexander and et al.}, author_hint = {A.~Fügenschuh, A.~Martin, P.~Stöveken}, booktitle = {Operations Research Proceedings 2004}, editor = {H. Fleuren; D. den Hertog; P. Kort}, faupublication = {no}, pages = {150 -- 157}, peerreviewed = {unknown}, publisher = {Springer, Berlin}, support_note = {Author relations incomplete. You may find additional data in field 'author_hint'}, title = {{Integrated} {Optimization} of {School} {Starting} {Times} and {Public} {Bus} {Services}}, year = {2005} } @article{faucris.110059444, abstract = {In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-call

This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.

}, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, doi = {10.1016/j.ejor.2018.02.035}, faupublication = {yes}, journal = {European Journal of Operational Research}, keywords = {OR in energy; Natural gas network optimization; Entry-exit model; Transport network capacity; Large-scale mixed-integer nonlinear programming}, pages = {797-808}, peerreviewed = {Yes}, title = {{A} {System} to {Evaluate} {Gas} {Network} {Capacities}: {Concepts} and {Implementation}}, volume = {270}, year = {2018} } @article{faucris.204162733, abstract = {In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is use}, author = {Schewe, Lars and Schmidt, Martin and Thürauf, Johannes}, doi = {10.1007/s10288-019-00411-3}, faupublication = {yes}, journal = {4OR-A Quarterly Journal of Operations Research}, keywords = {Gas networks; Booking; Entry-exit system; Convexity; Flow models}, peerreviewed = {Yes}, title = {{Structural} {Properties} of {Feasible} {Bookings} in the {European} {Entry}-{Exit} {Gas} {Market} {System}}, url = {http://www.optimization-online.org/DB_HTML/2018/09/6831.html}, year = {2019} } @article{faucris.123414324, author = {Gottschalk, Corinna and Koster, Arie and Liers, Frauke and Peis, Britta and Schmand, Daniel and Wierz, Andreas}, doi = {10.1007/s10107-017-1170-3}, faupublication = {yes}, journal = {Mathematical Programming}, keywords = {05C21 Flows in graphs, 90C05 Linear programming, 90C59 Approximation methods and heuristics, 90C46 Optimality conditions, duality}, peerreviewed = {Yes}, title = {{Robust} flows over time: models and complexity results}, year = {2017} } @incollection{faucris.115682204, abstract = {Semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection. Using the spectral bundle method it is possible to exploit structural properties of the underlying problem and to apply, even to sparse large scale instances, cutting plane methods, probably the most successful technique in linear programming. We set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities presented in the recent study [2] of the facial structure of the associated polytope. Extensive numerical experiments show that the semidefinite branch-and-cut approach outperforms the classical simplex approach on a clear majority of the sparse large scale test instances. On instances from compiler design the simplex approach is faster.}, author = {Armbruster, Michael and Helmberg, Christoph and Fügenschuh, Marzena and Martin, Alexander}, booktitle = {Integer Programming and Combinatorial Optimization}, editor = {A. Lodi, A. Panconesi, G. Renaldi}, faupublication = {no}, keywords = {Branch and cut algorithms; Cutting plane algorithms; Polyhedral combinatorics; Semidefinite programs}, pages = {112 -- 124}, peerreviewed = {Yes}, series = {Proceedings of the IPCO 2008 Conference, LNCS 5035}, title = {{A} {Comparative} {Study} of {Linear} and {Semidefinite} {Branch}-and-{Cut} {Methods} for {Solving} the {Minimum} {Graph} {Bisection} {Problem}}, year = {2008} } @book{faucris.122269004, address = {Philadelphia}, editor = {Koch, Thorsten and Hiller, Benjamin and Pfetsch, Marc E. and Schewe, Lars}, faupublication = {yes}, isbn = {978-1-611973-68-6}, peerreviewed = {automatic}, publisher = {SIAM}, series = {SIAM-MOS Series on Optimization}, title = {{Evaluating} {Gas} {Network} {Capacities}}, year = {2015} } @incollection{faucris.123596704, abstract = {In order to optimize branched sheet metal profiles consisting of several chambers, decisions concerning topology and geometry have to be made. This leads to a problem entailing discrete and nonlinear features. We describe an integrated approach combining both aspects. The underlying idea is to use a branch-and-bound algorithm. In each node of the branch-and-bound tree, a nonlinear optimization problem has to be solved. We describe how the branch-and-bound tree is constructed, i.e., how the topology decision can be classified in a meaningful way. Moreover, we explain how to approach the nonlinear optimization problem arising in the nodes of the tree. We conclude by presenting a numerical example.}, author = {Göllner, Thea and Günther, Ute and Hess, Wolfgang and Martin, Alexander and Ulbrich, Stefan}, booktitle = {PAMM, Proceedings of Applied Mathematics and Mechanics}, faupublication = {yes}, pages = {713 -- 714}, peerreviewed = {No}, title = {{Topology} and {Geometry} {Optimization} of {Branched} {Sheet} {Metal} {Products}}, volume = {11}, year = {2011} } @article{faucris.124196424, abstract = {We introduce a mixed integer linear modeling approach for the optimization of dynamic transport networks based on the piecewise linearization of nonlinear constraints and we show how to apply this method by two examples, transient gas and water supply network optimization. We state the mixed integer linear programs for both cases and provide numerical evidence for their suitability.}, author = {Geißler, Björn and Kolb, Oliver and Lang, Jens and Leugering, Günter and Martin, Alexander and Morsi, Antonio}, doi = {10.1007/s00186-011-0354-5}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, keywords = {Mixed integer linear programming;Piecewise linear approximation;Gas network optimization;Water network optimization}, pages = {339-362}, peerreviewed = {Yes}, title = {{Mixed} integer linear models for the optimization of dynamical transport networks}, volume = {73}, year = {2011} } @masterthesis{faucris.123956624, author = {Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, school = {Friedrich-Alexander-Universität Erlangen-Nürnberg}, title = {{Über} {Aspekte} des {Designs} symmetrischer {Verschlüsselungsverfahren} mit einer {Anwendung} auf ein neues {Kryptosystem}}, year = {2008} } @incollection{faucris.108434084, abstract = {Oriented matroids are a combinatorial abstraction of finite sets of points in ℝ

}, author = {Martin, Alexander and Pokutta, Sebastian and Schewe, Lars}, doi = {10.1002/cite.201100252}, faupublication = {yes}, journal = {Chemie-Ingenieur-Technik}, keywords = {Energiebilanz; Energiedissipation; Energieeinsparung; Energiespeicherung}, pages = {832 -- 839}, peerreviewed = {Yes}, title = {{Optimierung} in der {Energiewirtschaft}: lokale vs. globale {Optimallösungen}}, volume = {84}, year = {2012} } @misc{faucris.202208666, abstract = {We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved}, author = {Hojny, Christopher and Joormann, Imke and Lüthen, Hendrik and Schmidt, Martin}, faupublication = {yes}, keywords = {Max-cut; Connectivity; Branch-and-cut; Mixed-integer programming}, peerreviewed = {automatic}, title = {{Mixed}-{Integer} {Programming} {Techniques} for the {Connected} {Max}-k-{Cut} {Problem}}, url = {http://www.optimization-online.org/DB_HTML/2018/07/6738.html}, year = {2018} } @article{faucris.108901584, 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.}, author = {Martin, Alexander and et al.}, author_hint = {H.~Marchand, A.~Martin, R.~Weismantel, L.A.~Wolsey}, doi = {10.1016/S0166-218X(01)00348-1}, faupublication = {no}, journal = {Discrete Applied Mathematics}, keywords = {Cutting planes; Mixed integer programming}, pages = {391 -- 440}, peerreviewed = {Yes}, support_note = {Author relations incomplete. You may find additional data in field 'author_hint'}, title = {{Cutting} {Planes} in {Integer} and {Mixed} {Integer} {Programming}}, volume = {123/124}, year = {2002} } @incollection{faucris.108909064, author = {Fügenschuh, Armin-René and Martin, Alexander}, booktitle = {PAMM, Proceedings of Applied Mathematics and Mechanics}, faupublication = {no}, pages = {2060049-2060050}, peerreviewed = {No}, title = {{Mixed}-{Integer} {Models} for {Topology} {Optimization} in {Sheet} {Metal} {Design}}, volume = {7}, year = {2007} } @article{faucris.117696964, author = {Domschke, Pia and Groß, Martin and Hante, Falk and Hiller, Benjamin and Schewe, Lars and Schmidt, Martin}, faupublication = {yes}, journal = {Gas und Wasserfach, Gas, Erdgas}, pages = {880-885}, peerreviewed = {No}, title = {{Mathematische} {Modellierung}, {Simulation} und {Optimierung} von {Gastransportnetzwerken}}, url = {https://www.di-verlag.de/de/Zeitschriften/gwf-Gas-Erdgas/2015/11/Mathematische-Modellierung-Simulation-und-Optimierung-von-Gastransportnetzwerken}, volume = {156}, year = {2015} } @article{faucris.108434744, abstract = {We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e. g., for face lattices of polytopes. © 2009 Springer Science+Business Media, LLC.}, author = {Schewe, Lars}, doi = {10.1007/s00454-009-9222-y}, faupublication = {no}, journal = {Discrete & Computational Geometry}, keywords = {Embeddings; Oriented matroids; Polyhedral surfaces; Satisfiability}, pages = {289-302}, peerreviewed = {Yes}, title = {{Nonrealizable} minimal vertex triangulations of surfaces: {Showing} nonrealizability using oriented matroids and satisfiability solvers}, volume = {43}, year = {2010} } @misc{faucris.115699584, author = {Geißler, Björn and Kolb, Oliver and Lang, Jens and Leugering, Günter and Martin, Alexander and Morsi, Antonio}, faupublication = {yes}, peerreviewed = {automatic}, title = {{Mixed} {Integer} {Linear} {Models} for the {Optimization} of {Dynamical} {Transport} {Networks}}, year = {2010} } @article{faucris.106529764, abstract = {The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library.}, author = {Schmidt, Martin and Aßmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc E. and Schewe, Lars and Schwarz, Robert and Sirvent, Mathias}, doi = {10.3390/data2040040}, faupublication = {yes}, journal = {Data}, keywords = {Gas Transport; Networks; Problem Instances; Mixed-Integer Nonlinear Optimization; GasLib}, peerreviewed = {Yes}, title = {{GasLib} - {A} {Library} of {Gas} {Network} {Instances}}, url = {http://www.optimization-online.org/DB_HTML/2015/11/5216.html}, volume = {2}, year = {2017} } @incollection{faucris.109835704, author = {Mahlke, Debora and Martin, Alexander and Zelmer, Andrea}, booktitle = {thema forschung}, faupublication = {no}, pages = {12 -- 17}, peerreviewed = {No}, publisher = {TU Darmstadt}, title = {{Optimale} {Auslegung} gekoppelter {Energienetze}}, volume = {3}, year = {2007} } @incollection{faucris.115682424, author = {Fügenschuh, Armin-René and Hess, Wolfgang and Schewe, Lars and Martin, Alexander and Ulbrich, Stefan}, booktitle = {Tagungsband 2. Zwischenkolloqium SFB 666}, editor = {P. Groche}, faupublication = {no}, pages = {17 -- 28}, peerreviewed = {No}, publisher = {Meisenbach Verlag, Bamberg}, title = {{Verfeinerte} {Modelle} zur {Topologie}- und {Geometrie}-{Optimierung} von {Blechprofilen} mit {Kammern}}, year = {2008} } @incollection{faucris.203352087, abstract = {Rail freight traffic in Germany has experienced significant growth rates over the last decade, and recent forecasts expect this tendency to continue over the next 20 years due to the increases in national and international trade. Internal predictions of Deutsche Bahn AG, the most important German railway enterprise, assume a mean increase of 2{%} per year for rail freight traffic until 2030. At this pace, the German railway network in its current state would reach its capacity limit way before this date. As investments into the network infrastructure bear a very high price tag, it is crucial to use the available budget in the most efficient manner. Furthermore, the large size of the networks under consideration warrants the development of efficient algorithms to handle the complex network design problems arising for real-world data. This led us to the development of network aggregation procedures which allow for much shorter solution times by compressing the network information. More exactly, our framework works by clustering the nodes of the underlying graph to components and solving the network design problem over this aggregated graph. This kind of aggregation may either be used as a quick heuristic, or it can be extended to an exact method, e.g. by iterative refinement of the clustering, The latter results in a cutting plane algorithm, which also introduces new variables with each refinement. This idea developed in Bärmann et al. (Math Program Comput 7(2):189--217, 2015) is extended in this chapter such that it is able to incorporate the costs for routing flow through the network via lifted Benders optimality cuts. Altogether, our algorithm can be seen as a novel kind of Benders decomposition which allows to shift variables from the subproblem to the master problem in the process. Computations on several benchmark sets demonstrate the effectiveness of the approach.}, address = {Cham}, author = {Bärmann, Andreas and Liers, Frauke}, booktitle = {Handbook of Optimization in the Railway Industry}, doi = {10.1007/978-3-319-72153-8_3}, editor = {Borndörfer R, Klug T, Lamorgese L, Mannino C, Reuther M, Schlechte T}, faupublication = {yes}, isbn = {978-3-319-72153-8}, pages = {47--72}, peerreviewed = {Yes}, publisher = {Springer International Publishing}, title = {{Aggregation} {Methods} for {Railway} {Network} {Design} {Based} on {Lifted} {Benders} {Cuts}}, year = {2018} } @incollection{faucris.124206104, abstract = {

This chapter describes the fundamentals of gas transport. This includes an introduction to the basic terminology and basic physical laws with respect to natural gas. Then the basic elements needed to represent gas networks are discussed: pipes, resistors, valves, control valves, and compressor machines and drives. These elements can be grouped into larger entities like compressor groups and subnetwork operation modes.

}, author = {Fügenschuh, Armin and Geißler, Björn and Gollmer, Ralf and Morsi, Antonio and Pfetsch, Marc E. and Rövekamp, Jessica and Schmidt, Martin and Spreckelsen, Klaus and Steinbach, Marc C.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch2}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {17-44}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{Physical} and technical fundamentals of gas networks}, year = {2015} } @article{faucris.120540244, abstract = {In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nearly all problem instances discussed in the literature to optimality, including one problem that - to our knowledge - has not yet been solved. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called SteinLib that is accessible via the World Wide Web.}, author = {Koch, Thorsten and Martin, Alexander}, faupublication = {no}, journal = {Networks}, keywords = {Branch-and-cut; Cutting planes; Reduction methods; Steiner tree; Steiner tree library}, pages = {207 -- 232}, peerreviewed = {Yes}, title = {{Solving} {Steiner} {Tree} {Problems} in {Graphs} to {Optimality}}, volume = {32}, year = {1998} } @incollection{faucris.115675384, address = {Dresden}, author = {Wäldele, Martin and Fügenschuh, Armin-René and Birkhofer, Herbert and Martin, Alexander}, booktitle = {5. Gemeinsames Kolloquium Konstruktionstechnik 2007}, faupublication = {no}, pages = {73 - 82}, peerreviewed = {unknown}, title = {{Algorithmenbasierte} {Produktentwicklung} für integrale {Blechbauweisen} höherer {Verzweigungsordnung}}, year = {2007} } @article{faucris.123844644, author = {Hübner, Jens and Steinbach, Marc C. and Schmidt, Martin}, doi = {10.1287/ijoc.2017.0748}, faupublication = {yes}, journal = {Informs Journal on Computing}, pages = {612-630}, peerreviewed = {Yes}, title = {{A} {Distributed} {Interior}-{Point} {KKT}-{Solver} for {Multistage} {Stochastic} {Problems}}, url = {http://www.optimization-online.org/DB_HTML/2016/02/5318.html}, volume = {29}, year = {2017} } @article{faucris.122769284, abstract = {Economic reasons and the regulation of gas markets create a growing need for mathematical optimization of natural gas networks. Real life planning tasks often lead to highly complex and extremely challenging optimization problems whose numerical treatment requires a breakdown into several simplified problems to be solved by carefully chosen hierarchies of models and algorithms. This paper presents stationary NLP type models of gas networks that are primarily designed to include detailed nonlinear physics in the final optimization steps for mid term planning problems after fixing discrete decisions with coarsely approximated physics.}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, doi = {10.1007/s11081-014-9246-x}, faupublication = {yes}, journal = {Optimization and Engineering}, keywords = {Gas networks; Stationary flow; High-detail modeling; Nonsmooth nonlinear discrete-continuous optimization; Smoothing techniques}, pages = {131-164}, peerreviewed = {Yes}, title = {{High} detail stationary optimization models for gas networks}, volume = {16}, year = {2015} } @article{faucris.119101664, abstract = {A gas network consists of pipes to transport the gas from the suppliers to the consumers. Due to friction with the pipe walls, gas pressure gets lost. Compressors compensate this pressure loss at the cost of consuming fuel gas. The aim of gas network optimization is to minimize the fuel gas consumption of the compressors in such a way that the contracts with consumers and suppliers are fulfilled. This problem leads to a very complex mixed integer nonlinear optimization problem. We present a linear approach which concentrates on time-dependent and discrete aspects. The nonlinearities are approximated by piece-wise linear functions using the concept of SOS constraints. We develop a branch-and-cut algorithm which has the potential to guarantee global optimality of the linearized problem where the nonlinearities are approximated within a given accuracy. We include an adequate handling of the SOS conditions and a separation algorithm for switching processes of compressors. A simulated annealing algorithm is included yielding feasible solutions. Our computational results show the success of our approach in this challenging field of gas network optimization.}, author = {Mahlke, D. and Martin, Alexander and Moritz, S.}, doi = {10.1080/10556780903270886}, faupublication = {no}, journal = {Optimization Methods and Software}, keywords = {mixed integer programming; transient gas optimization; piece-wise linear approximation; SOS condition; branch-and-cut}, pages = {625 -- 644}, peerreviewed = {Yes}, title = {{A} {Mixed} {Integer} {Approach} for {Time}-{Dependent} {Gas} {Network} {Optimization}}, volume = {25}, year = {2010} } @article{faucris.122465684, abstract = {

The runway is the main element that combines airside and groundside of the ATM System. Thus, it is crucial to develop efficient models and planning algorithms for its effective usage. The best planning algorithm, however, is useless if the resulting plans cannot be implemented in the real world. This often happens because the input data of the planning algorithms face disturbances or changes over time, respectively. For example, an estimated time of arrival/departure of an aircraft may be changed. It is usually not certain for the next ten hours.

In this work, we study the runway scheduling problem under uncertain conditions. First, we present mathematical optimization models that ignore uncertainties. In the most effective approach, we compute for every discretized point in time whether an aircraft is scheduled and if so, which one is. Then, in each planning step we take uncertainties into account. We then apply different robust optimization methods in order to devise solution approaches that lead to stable plans. These optimization approaches are integrated into a simulation tool and evaluated in different traffic scenarios.

The Monte-Carlo simulations for a mixed-mode runway system show that our robust approaches result in fewer sequence changes and target time updates, when compared to the usual approach in which the plan is simply updated in case of infeasibility. Thus, we show that protection against uncertainties by using robust optimization indeed leads to considerably more stable plans.

}, author = {Heidt, Andreas and Helmke, Hartmut and Kapolke, Manu and Liers, Frauke and Martin, Alexander}, doi = {10.1016/j.jairtraman.2016.02.009}, faupublication = {yes}, journal = {Journal of Air Transport Management}, keywords = {Scheduling; Uncertainty; Time-indexed model; MIP; Mixed-integer programming; Dynamic time-indexed model; Strict robustness; Light robustness}, pages = {28-37}, peerreviewed = {Yes}, title = {{Robust} runway scheduling under uncertain conditions}, volume = {56}, year = {2016} } @incollection{faucris.115686384, author = {Epe, Alexa and Mahlke, Debora and Martin, Alexander and Wagner, Herman-Josef and Weber, Christoph and Woll, Oliver and Zelmer, Andrea}, booktitle = {Innovative Modellierung und Optimierung von Energiesystemen}, editor = {R. Schultz, H.-J. Wagner}, faupublication = {no}, pages = {153 --178}, peerreviewed = {unknown}, publisher = {LIT Verlag}, title = {{Betriebsoptimierung} zur ökonomischen {Bewertung} von {Speichern}}, year = {2009} } @incollection{faucris.121811184, abstract = {In this paper we survey the basic features of state-of-the-art branch-and-cut algorithms for the solution of general mixed integer programming problems. In particular we focus on preprocessing techniques, branch-and-bound issues and cutting plane generation.}, author = {Martin, Alexander}, booktitle = {Computational Combinatorial Optimization}, editor = {D. Naddef, M. Jünger}, faupublication = {no}, peerreviewed = {unknown}, publisher = {Springer, Berlin}, title = {{General} {Mixed} {Integer} {Programming}: {Computational} {Issues} for {Branch}-and-{Cut} {Algorithms}}, year = {2001} } @misc{faucris.122404304, abstract = {In this paper we show how to use an old mathematical concept of diophantine analysis, the approximation theorem of Kronecker, in symmetric cryptography. As a rst practical application we propose and analyze the new symmetric 128-bit block cipher KronCrypt. The cipher is a 4-round Feistel network with a non-bijective round function f made up of a variable number of large key-dependent S-boxes, XORs and modular additions. Its key length is variable but not less than 128 bit. The main innovation of KronCrypt in the area of symmetric cryptography is the fact that the key-dependent S-boxes are based upon a constructive proof of the approximation theorem of Kronecker used as a boolean function. We prove the correctness of our concept in general and show how we designe the new cipher KronCrypt. Furthermore, results concerning statistical behaviour, i.e. confusion, diusion and completeness, and dierential cryptanalysis are presented.}, author = {Elsner, Carsten and Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, title = {{KronCrypt} - {A} {New} {Symmetric} {Cryptosystem} {Based} on {Kronecker}'s {Approximation} {Theorem}}, url = {http://eprint.iacr.org/}, year = {2009} } @article{faucris.115723344, abstract = {In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.}, author = {Bärmann, Andreas and Liers, Frauke and Martin, Alexander and Merkert, Maximilian and Thurner, Christoph and Weninger, Dieter}, doi = {10.1007/s12532-015-0079-1}, faupublication = {yes}, journal = {Mathematical Programming Computation}, pages = {189-217}, peerreviewed = {unknown}, title = {{Solving} {Network} {Design} {Problems} via {Iterative} {Aggregation}}, volume = {7}, year = {2015} } @inproceedings{faucris.121872124, abstract = {We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in R3. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. We construct a new infinite family of non-realizable triangula tions of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e.g. for face lattices of polytopes.}, author = {Schewe, Lars}, booktitle = {Discrete Differential Geometry: Abstracts from the workshop}, date = {2006-03-05/2006-03-11}, faupublication = {no}, pages = {707-708}, peerreviewed = {unknown}, series = {Oberwolfach Reports}, title = {{Nonrealizable} minimal triangulations of surfaces}, volume = {3}, year = {2006} } @article{faucris.115665924, abstract = {A hierachy of simplified models for traffic flow on networks is derived from continuous traffic flow models based on partial differential equations. The hierachy contains nonlinear and linear combinatorial models with and without dynamics. Optimization problems are treated for all models and numerical results and algorithms are compared.}, author = {Fügenschuh, Armin-René and Herty, Michael and Klar, Axel and Martin, Alexander}, faupublication = {no}, journal = {SIAM Journal on Optimization}, keywords = {Combinatorial methods; Partial differential equations; Traffic networks}, pages = {1155 -- 1176}, peerreviewed = {Yes}, title = {{Combinatorial} and {Continuous} {Models} for the {Optimization} of {Traffic} {Flows} on {Networks}}, volume = {16}, year = {2006} } @incollection{faucris.115669664, abstract = {A new technique for forming sheet metal makes it possible to construct branched sheet metal products out of one piece of sheet metal. Since the number of potential ways to produce one and the same component increases exponentially with every additional branch, appropriate tools for handling the large number of possibilities are necessary. In this paper we give a Mixed Integer Program that models the different ways of producing branched profiles and show how to incorporate manufacturing constraints into the model.}, author = {Günther, Ute and Martin, Alexander}, booktitle = {PAMM, Proceedings of Applied Mathematics and Mechanics}, faupublication = {no}, pages = {697 -- 698}, peerreviewed = {unknown}, title = {{Mixed} {Integer} {Models} for {Branched} {Sheet} {Metal} {Products}}, volume = {6}, year = {2006} } @inproceedings{faucris.203351150, abstract = {In this paper, we demonstrate how to learn the objective function of a decision maker while only observing the problem input data and the decision maker’s corresponding decisions over multiple rounds. Our approach is based on online learning techniques and works for linear objectives over arbitrary sets for which we have a linear optimization oracle and as such generalizes previous work based on KKT-system decomposition and dualization approaches. The applicability of our framework for learning linear constraints is also discussed briefly. Our algorithm converges at a rate of O(1/sqrt(T)), and we demonstrate its effectiveness and applications in preliminary computational results.}, address = {International Convention Centre, Sydney, Australia}, author = {Bärmann, Andreas and Pokutta, Sebastian and Schneider, Oskar}, booktitle = {Proceedings of the 34th International Conference on Machine Learning (ICML)}, editor = {Precup D, Teh YW}, faupublication = {yes}, pages = {400--410}, peerreviewed = {Yes}, publisher = {PMLR}, series = {Proceedings of Machine Learning Research}, title = {{Emulating} the {Expert}: {Inverse} {Optimization} through {Online} {Learning}}, url = {http://proceedings.mlr.press/v70/barmann17a.html}, volume = {70}, year = {2017} } @misc{faucris.119599304, abstract = {We consider the optimization of a gas network that is described by a coupled system of parabolic partial differential equations. Energy and mass balance at network junctions and active elements, like compressors or valves, are modeled as additional algebraic equations. The resulting optimal control problem is discretized in space and time by a particular finite volume method, which can be shown to be well-posed under rather general assumptions. This discretize-first-then-optimize

procedure yields a mixed-integer nonlinear problem (MINLP) that can be solved to global optimality.

For the numerical solution of the MINLP, we consider a relaxation approach allowing to solve the problem globally by a sequence of mixed-integer problems (MIPs) with any required accuracy. The relaxation is based on piecewise linearization of the nonlinear constraints modeling the gas dynamics on the pipelines. Due to the particular discretization of the state equations, only univariate nonlinearities have to be approximated. This substantially facilitates the numerical treatment of the nonlinear constraints. To illustrate the efficiency of the proposed approach, we present numerical tests for typical benchmark problems.}, author = {Burlacu, Robert and Egger, Herbert and Gross, Martin and Martin, Alexander and Pfetsch, Marc E. and Schewe, Lars and Sirvent, Mathias and Skutella, Martin}, faupublication = {yes}, keywords = {Discretization; Instationary Gas Transport Optimization; Mixed-Integer Nonlinear Programming}, peerreviewed = {automatic}, title = {{A} {Global} {Optimization} {Approach} for {Instationary} {Gas} {Transport} in {Pipeline} {Networks}}, url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/221}, year = {2017} } @article{faucris.120380524, abstract = {A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach.}, author = {Martin, Alexander and Möller, Markus and Moritz, Susanne}, doi = {10.1007/s10107-005-0665-5}, faupublication = {no}, journal = {Mathematical Programming}, keywords = {Branch-and-Bound; Cutting planes; Gas optimization; Mixed integer programming; Piece-wise linear functions; SOS constraints}, pages = {563 - 582}, peerreviewed = {Yes}, title = {{Mixed} {Integer} {Models} for the {Stationary} {Case} of {Gas} {Network} {Optimization}}, volume = {105}, year = {2006} } @article{faucris.120164704, abstract = {In this paper we consider the multiple knapsack problem, which is defined as follows: given a set

Read More: http://epubs.siam.org/doi/abs/10.1137/S1052623493254455},
author = {E. Ferreira, Carlos and Martin, Alexander and Weismantel, Robert},
faupublication = {no},
journal = {SIAM Journal on Optimization},
keywords = {Branch and cut; Cutting planes; Multiple knapsack problem; Separation},
pages = {858 - 877},
peerreviewed = {Yes},
title = {{Solving} {Multiple} {Knapsack} {Problems} by {Cutting} {Planes}},
volume = {6},
year = {1996}
}
@article{faucris.203351402,
abstract = {We introduce the *Clique Problem with Multiple-Choice constraints (CPMC)* and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This special case, which we name *staircase compatibility*, generalizes common properties in several applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world problem settings. The first one is a problem in railway timetabling, where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear network flow problems, illustrated at the example of gas networks. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the proble},
author = {Bärmann, Andreas and Gellermann, Thorsten and Merkert, Maximilian and Schneider, Oskar},
doi = {10.1016/j.disopt.2018.04.001},
faupublication = {yes},
journal = {Discrete Optimization},
keywords = {Clique problem with multiple-choice constraints; Staircase compatibility; Total unimodularity; Scheduling; Piecewise linearization},
pages = {111-132},
peerreviewed = {Yes},
title = {{Staircase} {Compatibility} and its {Applications} in {Scheduling} and {Piecewise} {Linearization}},
url = {http://www.sciencedirect.com/science/article/pii/S1572528618300306},
volume = {29},
year = {2018}
}
@article{faucris.123587684,
abstract = {We consider a flow network where the flow of parts can be controlled at the vertices of the network. Based on a modified coarse grid discretization presented in Fügenschuh et al. (SIAM J Scientific Comput 30(3):1490-1507, 2008) we derive a mixed-integer program (MIP). Under suitable assumptions on the cost functional we prove that there exists an equivalent linear program (LP). We present numerical results concerning validity of our result and show the improvement of the computing times using the equivalent LP over the MIP.},
author = {Fügenschuh, Armin-René and Goettlich, S. and Herty, Michael and Kirchner, C. and Martin, Alexander},
doi = {10.1007/s00607-009-0038-7},
faupublication = {no},
journal = {Computing},
keywords = {Adjoint calculus; Conservation laws; Flow networks; Networks},
pages = {245 -- 265},
peerreviewed = {Yes},
title = {{Efficient} {Reformulation} and {Solution} of a {Nonlinear} {PDE}-{Controlled} {Flow} {Network} {Model}},
volume = {85},
year = {2009}
}
@incollection{faucris.110458964,
abstract = {Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). In a previous paper, we developed a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Further, we investigated the impact of disturbances on our solutions, since in reality uncertainty and inaccuracy almost always lead to deviations from actual plans. In this paper, we now present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. We describe a simulation environment and test our new solution methods against standard algorithms (e.g., First-Come-First-Serve). The encouraging results show that our approaches significantly reduce the number of necessary replan nings.},
author = {Fürstenau, Norbert and Heidt, Andreas and Kapolke, Manu and Liers, Frauke and Mittendorf, Monika and Weiß, Christian},
booktitle = {Proceedings of the SESAR Innovations Days 2015},
editor = {Dirk Schäfer},
faupublication = {yes},
keywords = {runway utilization; planning,pre-tactical; optimization; uncertainties; stochastic; robust; algorithms; models; validation; Monte Carlo simulation},
peerreviewed = {unknown},
publisher = {Eurocontrol},
title = {{Pre}-{Tactical} {Planning} of {Runway} {Utilization} {Under} {Uncertainty}: {Optimization} and {Validation}},
year = {2015}
}
@inproceedings{faucris.106847664,
abstract = {Let Δ(d, n) be the maximum possible diameter of the vertex-edge graph over all d-dimensional polytopes de- fined by n inequalities. The Hirsch bound holds for particular n and d if Δ (d, n) ≤ n - d. Francisco Santos recently resolved a question open for more than five decades by showing that Δ (d, 2d) = d + 1 for d = 43, the dimension was then lowered to 20 by Matchske, Santos and Weibel. This progress has stimulated interest in related questions. The existence of a polynomial upper bound for Δ (d, n) is still an open question, the best bound being the quasi-polynomial one due to Kalai and Kleitman in 1992. Another natural question is for how large n and d the Hirsch bound holds. Goodey showed in 1972 that Δ (4, 10) = 5 and Δ (5, 11) = 6, and more recently, Bremner and Schewe showed Δ (4, 11) = Δ 6, 12) = 6. Here we show that (4, 12) = Δ (5, 12) = 7 and present strong evidence that Δ (6, 13) = 7.},
author = {Bremner, David and Deza, Antoine and Hua, William and Schewe, Lars},
booktitle = {Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011},
date = {2011-08-10/2011-08-12},
faupublication = {yes},
pages = {193-198},
title = {{Pushing} the boundaries of polytopal realizability},
url = {https://www.scopus.com/record/display.uri?eid=2-s2.0-84882934180&origin=inward},
venue = {Toronto, ON},
year = {2011}
}
@inproceedings{faucris.119108924,
address = {Bamberg},
author = {Pruckner, Marco and Thurner, Christoph and Martin, Alexander and German, Reinhard},
booktitle = {MMB & DFT 2014, Proceedings of the International Workshop SOCNET 2014 and FGENET 2014},
editor = {K.~Fischbach, M.~Großmann, U.~Krieger, T.~Staake},
faupublication = {yes},
pages = {97 -- 104},
peerreviewed = {Yes},
title = {{A} {Coupled} {Optimization} and {Simulation} {Model} for the {Energy} {Transition}},
volume = {16},
year = {2014}
}
@inproceedings{faucris.123452164,
author = {Lorenz, Ulf and Martin, Alexander and Wolf, Jan},
booktitle = {Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings},
doi = {10.1007/978-3-642-15775-2_44},
editor = {M. de Berg, U. Meyer},
faupublication = {yes},
isbn = {978-3-642-15774-5},
pages = {512-523},
peerreviewed = {Yes},
series = {Lecture Notes in Computer Science},
title = {{Polyhedral} and {Algorithmic} {Properties} of {Quantified} {Linear} {Programs}},
volume = {6346},
year = {2010}
}
@article{faucris.108911264,
abstract = {We present a new model for a strategic locomotive scheduling problem arising at the Deutsche Bahn AG. The model is based on a multicommodity minimum cost flow formulation that is also used for public bus scheduling problems. However, several new aspects have to be additionally taken into account such as cyclic departures of the trains, time windows on starting and arrival times, network load-dependent travel times, and a transfer of cars between trains. The model is formulated as an integer linear programming problem (ILP). The formulation is improved by preprocessing and additional cutting planes. Solutions are obtained using a randomized greedy heuristic in combination with commercial ILP solvers. Computational results are presented for several real-world test instances.},
author = {Fügenschuh, Armin and Homfeld, Henning and Huck, Andreas and Martin, Alexander and Yuan, Zhi},
doi = {10.1287/trsc.1080.0248},
faupublication = {no},
journal = {Transportation Science},
keywords = {Cutting planes; Cyclic vehicle scheduling; Heuristics; Integer linear programming; Railroad freight transport; Time windows},
pages = {478 -- 491},
peerreviewed = {Yes},
title = {{Scheduling} {Locomotives} and {Car} {Transfers} in {Freight} {Transport}},
volume = {42},
year = {2008}
}
@misc{faucris.201727031,
abstract = {This paper mainly studies two topics: linear complementarity problems
(LCPs) for modeling electricity market equilibria and optimization under
uncertainty. While there have been quite some attempts to deal with uncertain LCPs in a stochastic - i.e., distributional - sense, robust
LCPs have only gained attention very recently. In this paper, we
consider both perfectly competitive and Nash-Cournot models of
electricity markets and study their robustifications using strict
robustness and the Γ-approach. For three out of the four combinations of
economic competition and robustification we derive algorithmically
tractable convex optimization counterparts that have a clear-cut
economic interpretation. In the case of perfect competition this
particularly means that the two classical welfare theorems also hold in
both considered robust cases. Using the mentioned counterparts, we can
also prove the existence and, in some cases, uniqueness of robust
equilibria. Surprisingly, it turns out that there is no such economic
sensible counterpart for the case of Γ-robustifications of Nash-Cournot
models. Thus, an analogue of the welfare theorems does not hold in this case. Finally, we provide a computational case study that illustrates
the different effects of the combination of economic competition and
uncertainty modeling.},
author = {Kramer, Anja and Krebs, Vanessa and Schmidt, Martin},
faupublication = {yes},
keywords = {Robust optimization; Linear complementarity problems; Electricity market equilibrium models; Perfect competition; Nash-Cournot competition},
peerreviewed = {automatic},
title = {{Strictly} and {Γ}-{Robust} {Counterparts} of {Electricity} {Market} {Models}: {Perfect} {Competition} and {Nash}--{Cournot} {Equilibria}},
url = {http://www.optimization-online.org/DB_HTML/2018/07/6709.html},
year = {2018}
}
@misc{faucris.120075604,
abstract = {Robust model predictive control approaches and other applications lead to nonlinear optimization problems defined on (scenario) trees. We present structure-preserving Quasi-Newton update formulas as well as structured inertia correction techniques that allow to solve these problems by interior-point methods with specialized KKT solvers for tree-structured optimization problems. The same type of KKT solvers could be used in active-set based SQP methods. The viability of our approach is demonstrated by two robust control problems.},
author = {Hübner, Jens and Schmidt, Martin and Steinbach, Marc C.},
faupublication = {yes},
keywords = {Nonlinear stochastic optimization, Interior-point methods, Structured Quasi-Newton updates, Structured inertia correction, Robust model predictive control.},
peerreviewed = {automatic},
title = {{Optimization} {Techniques} for {Tree}-{Structured} {Nonlinear} {Problems}},
url = {http://www.optimization-online.org/DB_HTML/2017/02/5845.html},
year = {2017}
}
@inproceedings{faucris.203404200,
author = {Steber, David and Pruckner, Marco and Thurner, Christoph and Burlacu, Robert and Graber, Thomas and Deß, Tobias and Luther, Matthias and Martin, Alexander and German, Reinhard},
booktitle = {Integration of Sustainable Energy Conference (ISEneC) 2018},
faupublication = {yes},
peerreviewed = {unknown},
title = {{Combined} {Optimization}, {Simulation} and {Grid} {Analysis} of the {German} {Electrical} {Power} {System} in an {European} {Context} ({KOSiNeK}) - {Presentation} of the research project and first results},
venue = {Nürnberg},
year = {2018}
}
@misc{faucris.111120284,
abstract = {Pricing of access to energy networks is an important issue in
liberalized energy sectors because of the natural monopoly character of
the underlying transport infrastructures. We introduce a general pricing
framework for potential based energy flows in arbitrarily structured
transport networks. In different specifications of our general pricing
model we discuss first- and second-best pricing results and compare
different pricing outcomes of potential-free and potential based energy
flow models. Our results show that considering nonlinear laws of physics
leads to significantly different pricing results on networks and that
these differences can only be seen in sufficiently complex, e.g.,
cyclic, networks as they can be found in real-world situations.},
author = {Schewe, Lars and Schmidt, Martin},
doi = {10.2139/ssrn.2628611},
faupublication = {yes},
keywords = {Energy Networks, Pricing, Gas Networks, Electricity Networks.},
peerreviewed = {automatic},
title = {{The} {Impact} of {Potential}-{Based} {Physics} {Models} on {Pricing} in {Energy} {Networks}},
url = {http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2628611},
year = {2018}
}
@article{faucris.117660444,
abstract = {Efficient planning of runway utilization is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. In this paper, we develop a specific optimization approach for the pre-tactical planning phase that reduces complexity by omitting unnecessary information. Instead of determining arrival/departure times to the minute in this phase yet, we assign *several* aircraft to the same time window of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, we solve a generalized assignment problem on a bipartite graph. To know how many aircraft can be assigned to one time window, we consider separation requirements for consecutive aircraft types. In reality, however, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. Thus, we present approaches to incorporate uncertainty directly in our model in order to achieve a stabilization with respect to changes in the data. Namely, we use techniques from robust optimization and stochastic optimization. Further, we analyze real-world data from a large German airport to obtain realistic delay distributions, which turn out to be two-parametric Γ-distributions. Finally, we describe a simulation environment to test our new solution methods.},
author = {Kapolke, Manu and Fürstenau, Norbert and Heidt, Andreas and Liers, Frauke and Mittendorf, Monika and Weiß, Christian},
doi = {10.1016/j.jairtraman.2016.02.004},
faupublication = {yes},
journal = {Journal of Air Transport Management},
keywords = {Pre-tactical planning; Runway; Optimization; Uncertainty; Robustness; Data analysis},
peerreviewed = {Yes},
title = {{Pre}-tactical optimization of runway utilization under uncertainty},
year = {2016}
}
@incollection{faucris.117399964,
abstract = {Efficient planning of runway utilisation is one of the main challenges in Air Traffic Management (ATM). It is important because runway is the combining element between airside and groundside. Furthermore, it is a bottleneck in many cases. However, uncertainty and inaccuracy almost always lead to deviations from the actual plan or schedule. In this paper, we develop an optimization approach for the pre-tactical planning phase that provides some flexibility in the face of small disturbances in the input data, so that we need to change our plans less frequently. Instead of determining arrival/departure times to the minute in this phase yet, we assign several aircraft to the same time slot of a given size. The exact orders within those time windows can be decided later in tactical planning. Mathematically, this leads to a generalised assignment problem on a bipartite graph. We develop an integer program (IP), which can be solved very fast but may provide unnecessary large time buffers, and extend it to a mixed integer program (MIP) that solves the problem to global optimality. We present computational results concerning the abovementioned optimization approach and investigate the impact of disturbances on our deterministic solutions. As a next step, we will incorporate uncertainties directly in our model. Therefore, we analyse real-world data from a large German airport in order to obtain realistic delay distributions and describe a simulation environment to test current and future solution methods.},
author = {Heidt, Andreas and Kapolke, Manu and Liers, Frauke and Fürstenau, Norbert and Helmke, Hartmut},
booktitle = {Proceedings of the SESAR Innovation Days 2014},
editor = {Dirk Schaefer, Javier Saez},
faupublication = {yes},
isbn = {978-2-87497-077-1},
keywords = {arrival / departure scheduling; stochastic optimization; robustness; delay statistics; modeling},
peerreviewed = {unknown},
title = {{Pre}-tactical {Time} {Window} assignment: {Runway} {Utilization} and the {Impact} of {Uncertainties}},
url = {http://www.sesarinnovationdays.eu},
year = {2014}
}
@misc{faucris.200121582,
abstract = {It is folklore knowledge that nonconvex mixed-integer nonlinear
optimization problems can be notoriously hard to solve in practice. In
this paper we go one step further and drop analytical properties that
are usually taken for granted in mixed-integer nonlinear optimization.
First, we only assume Lipschitz continuity of the nonlinear functions
and additionally consider multivariate implicit constraint functions
that cannot be solved for any parameter analytically. For this class of
mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear
function - in contrast to an approximation of the graph of the function
considered in prior work. This method is shown to compute global optimal
solutions in finite time and we also provide a worst-case iteration
bound. However, first numerical experiences reveal that a lot of work is
still to be done for this highly challenging class of problems and we
thus finally propose some possible directions of future researc},
author = {Schmidt, Martin and Sirvent, Mathias and Wollner, Winnifried},
faupublication = {yes},
keywords = {Mixed-Integer Nonlinear Optimization; Global Optimization; Lipschitz Optimization; Gas Networks},
peerreviewed = {automatic},
title = {{The} {Cost} of {Not} {Knowing} {Enough}: {Mixed}-{Integer} {Optimization} with {Implicit} {Lipschitz} {Nonlinearities}},
url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/235},
year = {2018}
}
@misc{faucris.222280969,
abstract = {An approach is presented for the optimal design of batch and steady-state recycling (SSR) chromatography. The optimization problem is decomposed into two stages. At the first stage, an efficient formulation as mixed-integer problem (MIP) is applied to obtain optimal fractionation times for chromatograms simulated by the equilibrium model. At the second stage, the optima are evaluated against a parametrized objective function. The chosen combination of model and optimization method provides a computationally very efficient tool. A comprehensive example study demonstrates that batch chromatography achieves the highest productivities at the cost of limited yields, which is optimal only for negligible feed costs. In other instances, the more flexible SSR concept provides larger profits. The results reveal also new optimal operating policies for SSR processes with segmented product fractions and waste streams.

a new generalization called reliability branching of today's state-of-the-art strong branching and pseudocost branching strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed new strategy.},
author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander},
faupublication = {no},
journal = {Operations Research Letters},
keywords = {Branch-and-bound; Mixed-integer-programming; Pseudocost-branching; Reliability-branching; Strong-branching; Variable selection},
pages = {42 -- 54},
peerreviewed = {Yes},
title = {{Branching} {Rules} {Revisited}},
volume = {33},
year = {2005}
}
@misc{faucris.124206984,
author = {Schmidt, Martin},
faupublication = {no},
peerreviewed = {No},
title = {{Über} {Aspekte} des {Designs} symmetrischer {Verschlüsselungsverfahren} mit einer {Anwendung} auf ein neues {Kryptosystem}},
year = {2008}
}
@inproceedings{faucris.116208664,
abstract = {In Germany, and in particular in Bavaria, the energy transition towards a more sustainable energy system is an important issue. The nuclear phase-out until 2023 is enacted and the extension of renewable energy sources takes place faster than expected. Optimization models can help to find the optimal extension path for renewable and conventional energy sources from an investment cost perspective. In addition, simulation models can be used to analyze how the electricity demand could be covered by different energy sources in a higher time resolution. In this paper we describe our optimization and simulation framework for the energy transition in Bavaria to perform an energy system analysis. Additionally, we present a coupled approach to analyze the annual energy balances for an optimal extension path.

},
address = {Bamberg},
author = {Pruckner, Marco and Thurner, Christoph and Martin, Alexander and German, Reinhard},
booktitle = {Proceedings of the International Workshop on Demand Modeling and Quantitative Analysis of Future Generation Energy Networks and Energy Efficient Systems},
date = {2014-03-17/2014-03-19},
faupublication = {yes},
isbn = {978-3-86309-208-5},
keywords = {Electricity transition, Energy System Analysis, Hybrid Simulation,
Energy optimization, Unit commitment problem},
note = {UnivIS-Import:2015-04-16:Pub.2014.tech.IMMD.IMMD7.acoupl},
pages = {97-104},
publisher = {University of Bamberg Press},
title = {{A} {Coupled} {Optimization} and {Simulation} {Model} for the {Energy} {Transition} in {Bavaria}},
venue = {Bamberg, Germany},
year = {2014}
}
@incollection{faucris.108916544,
abstract = {In this chapter we want to demonstrate that in certain cases general mixed integer nonlinear programs (MINLPs) can be solved by just applying purely techniques from the mixed integer linear world. The way to achieve this is to approximate the nonlinearities by piecewise linear functions. The advantage of applying mixed integer lin- ear techniques are that these methods are nowadays very mature, that is, they are fast, robust, and are able to solve problems with up to millions of variables. In addition, these methods have the potential of finding globally optimal solutions or at least to provide solution guarantees. On the other hand, one tends to say at this point “If you have a hammer, everything is a nail.”[15], because one tries to reformulate or to approximate an ac- tual nonlinear problem until one obtains a model that is tractable by the methods one is common with. Besides the fact that this is a very typical approach in mathematics the question stays whether this is a reasonable approach for the solution of MINLPs or whether the nature of the nonlin- earities inherent to the problem gets lost and the solutions obtained from the mixed integer linear problem have no meaning for the MINLP. The purpose of this chapter is to discuss this question. We will see that the truth lies somewhere in between and that there are problems where this is indeed a reasonable way to go and others where it is not.},
author = {Geißler, Björn and Martin, Alexander and Morsi, Antonio and Schewe, Lars},
booktitle = {Mixed Integer Nonlinear Programming},
doi = {10.1007/978-1-4614-1927-3},
editor = {Lee J, Leyffer S},
faupublication = {yes},
isbn = {978-1-4614-1926-6},
pages = {287-314},
peerreviewed = {unknown},
publisher = {Springer Science+Business Media, New York},
series = {The IMA Volumes in Mathematics and its Applications},
title = {{Using} {Piecewise} {Linear} {Functions} for {Solving} {MINLPs}},
volume = {154},
year = {2012}
}
@inproceedings{faucris.115685504,
author = {Waniek, Daniel and Rehtanz, Christian and Handschin, Edmund and Martin, Alexander and Mahlke, Debora and Zelmer, Andrea},
booktitle = {Innovative Modellierung und Optimierung von Energiesystemen},
editor = {R.~Schultz, H.-J-~Wagner},
faupublication = {no},
pages = {9 -- 38},
peerreviewed = {Yes},
publisher = {LIT Verlag},
title = {{Kostenoptimierte} {Planung} gekoppelter {Strom}-, {Gas}- und {Wärmenetze}},
year = {2009}
}
@inproceedings{faucris.108914344,
author = {Martin, Alexander and et al.},
author_hint = {U.~Günther, A.~Martin, T.~Shang},
booktitle = {Tagungsband 2. Zwischenkolloqium {SFB} 666},
editor = {P.~Groche},
faupublication = {no},
pages = {29 -- 34},
peerreviewed = {No},
publisher = {Meisenbach Verlag, Bamberg},
support_note = {Author relations incomplete. You may find additional data in field 'author_hint'},
title = {{Integration} von {Fertigungsrestriktionen} - {Ein} {Ansatz} aus der {Graphentheorie}},
year = {2008}
}
@article{faucris.119145664,
abstract = {In this paper we establish conditions under which uniqueness of market equilibrium is obtained in a setup where prior to trading of electricity, transmission capacities between different market regions are fixed. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested capacities, taking into account that market prices (partially) reflect scarce transmission capacities between the different market zones. For this type of peak-load pricing model on a network we state general conditions for existence and uniqueness of the market equilibrium and provide a characterization of equilibrium investment and production. The presented analysis covers the cases of perfect competition and monopoly - the case of strategic firms is approximated by a conjectural variations approach. Our result is a prerequisite for analyzing regulatory policy options with computational multilevel equilibrium models, since uniqueness of the equilibrium at lower levels is of key importance when solving these models. Thus, our paper contributes to an evolving strand of literature that analyzes regulatory policy based on computational multilevel equilibrium models and aims at taking into account individual objectives of various agents, among them not only generators and customers but also, e.g., the regulator deciding on network expansio},
author = {Grimm, Veronika and Schewe, Lars and Schmidt, Martin and Zöttl, Gregor},
doi = {10.1016/j.ejor.2017.03.036},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {Pricing; Peak-Load Pricing; Networks; Uniqueness},
pages = {971 - 983},
peerreviewed = {Yes},
title = {{Uniqueness} of market equilibrium on a network: {A} peak-load pricing approach},
url = {http://www.optimization-online.org/DB_HTML/2015/08/5072.html},
volume = {261},
year = {2017}
}
@misc{faucris.119276344,
abstract = {In this paper we present a four-level market model that accounts for airport capacity extension, fleet investment, aircraft scheduling, and ticket trade. In particular, budget-constrained airports decide on the first level on their optimal runway capacity extension and on a corresponding airport charge. Airports anticipate optimal long-term fleet investment of airlines on the second level, optimal medium-term aircraft scheduling on the third level, and short-term outcomes of a competitive ticket market on the fourth level. We compare this market model with an integrated single-level benchmark model that simultaneousely accounts for all investment, scheduling, and market clearing constraints. As we show, our four-level market model may result in inefficient long-run investments in both runway capacity and new aircraft. In addition, we identify policy regulations that may have the potential to reduce inefficiencies of the market model relative to the integrated benchmark model.},
author = {Sirvent, Mathias and Weibelzahl, Martin},
faupublication = {yes},
peerreviewed = {automatic},
title = {{Airport} {Capacity} {Extension}, {Fleet} {Investment}, and {Optimal} {Aircraft} {Scheduling} in a {Four}-{Level} {Market} {Model}: {On} the {Effects} of {Market} {Regulations}},
url = {http://www.optimization-online.org/DB_HTML/2017/05/5989.html},
year = {2017}
}
@article{faucris.112089384,
abstract = {We investigate the problem of designing energy-efficient timetables for railway traffic. More precisely, we slightly adapt a given timetable draft before it is published by moderately shifting the departure times of the trains at the stations. To this end, we propose a mixed-integer programming model for feasible adaptations of the timetable draft and investigate its behaviour under different objective functions which fall into two classes: reducing the energy cost and increasing the stability of the power supply system. These tests are performed on real-world problem instances from our industry partner Deutsche Bahn AG. They show a significant potential for improvements in the existing railway timetables.},
author = {Bärmann, Andreas and Martin, Alexander and Schneider, Oskar},
doi = {10.1007/s12469-017-0160-4},
faupublication = {yes},
journal = {Public Transport},
keywords = {Railway timetabling; Power peak reduction; Mixed-integer programming},
pages = {95-113},
peerreviewed = {unknown},
title = {{A} comparison of performance metrics for balancing the power consumption of trains in a railway network by slight timetable adaptation},
volume = {9},
year = {2017}
}
@inproceedings{faucris.108694564,
author = {Sieh, Volkmar and Burlacu, Robert and Hönig, Timo and Janker, Heiko and Raffeck, Phillip and Wägemann, Peter and Schröder-Preikschat, Wolfgang},
booktitle = {Proceedings of the 20th International Symposium on Real-Time Distributed Computing (ISORC 2017)},
date = {2017-05-16/2017-05-18},
doi = {10.1109/ISORC.2017.10},
faupublication = {yes},
isbn = {9781538615744},
keywords = {energy-model generation; static analysis; timing-model generation; WCEC; WCET},
note = {UnivIS-Import:2017-12-18:Pub.2017.tech.IMMD.IMMD4.anendt},
pages = {158--167},
peerreviewed = {Yes},
publisher = {Institute of Electrical and Electronics Engineers Inc.},
title = {{An} {End}-{To}-{End} {Toolchain}: {From} {Automated} {Cost} {Modeling} to {Static} {WCET} and {WCEC} {Analysis}},
url = {https://www4.cs.fau.de/Publications/2017/sieh_17_isorc.pdf},
venue = {Toronto, Canada},
year = {2017}
}
@article{faucris.118158084,
abstract = {We consider uniqueness and multiplicity of market equilibria in a short-run setup where traded quantities of electricity are transported through a capacitated network in which power flows have to satisfy the classical lossless DC approximation. The firms face fluctuating demand and decide on their production, which is constrained by given capacities. Today, uniqueness of such market outcomes are especially important in more complicated multilevel models for measuring market (in)efficiency. Thus, our findings are important prerequisites for such studies. We show that market equilibria are unique on tree networks under mild assumptions and we also present a priori conditions under which equilibria are unique on cycle networks. On general networks, uniqueness fails to hold and we present simple examples for which multiple equilibria exist. However, we prove a posteriori criteria for the uniqueness of a given solution and characterize situations in which multiple solutions exis},
author = {Krebs, Vanessa and Schewe, Lars and Schmidt, Martin},
doi = {10.1016/j.ejor.2018.05.016},
faupublication = {yes},
journal = {European Journal of Operational Research},
keywords = {Market Equilibria; Uniqueness; Multiplicity; Networks; DC Power Flow; Perfect Competition},
pages = {165-178},
peerreviewed = {Yes},
title = {{Uniqueness} and {Multiplicity} of {Market} {Equilibria} on {DC} {Power} {Flow} {Networks}},
url = {http://www.optimization-online.org/DB_HTML/2017/10/6239.html},
volume = {271},
year = {2018}
}
@incollection{faucris.117664184,
abstract = {The optimal design and control of infrastructures, e.g. in traffic control, water-supply, sewer-systems and gas-pipelines, the optimization of structures, form and formation of materials, e.g. in lightweight structures, play a predominant role in modern fundamental and applied research. However, until very recently, simulation-based optimization has been employed in the sense that parameters are being adjusted in a forward simulation using either ‘trial-and-error’ or a few steps of a rudimentary unconstrained derivative-free and mostly stochastic optimization code. It has become clear by now that instead often a model-based and more systematic constrained optimization that exploits the structure of the problem under consideration may outperform the former more naive approaches. Thus, modern mathematical optimization methods respecting constraints in state and design variables can be seen as a catalyst for recent and future technologies. More and more success stories can be detected in the literature and even in the public press which underline the role of optimization as a key future technology. In particular, optimization with partial differential equations (PDEs) as constraints, or in other words ‘PDE-constrained optimization’ has become research topic of great influence. A DFG-Priority-Program (PP) has been established by the German Science Foundation (DFG) in 2006 in which well over 25 project are funded throughout Germany. The PP focuses on the interlocking of fundamental research in optimization, modern adaptive, hierarchical and structure exploiting algorithms, as well as visualization and validation. With similar goals in mind, a European network within the European Science Foundation (ESF) ‘PDE-constrained Optimization’ has been recently established that provides a European platform for this cutting edge technology. In this report the authors dwell on exemplary areas of their expertise within applications that are already important and will increasingly dominate future developments in mechanical and civil engineering. These applications are concerned with optimal material and design in material sciences and light-weight structures as well as real-time capable optimal control of flows in transportation systems such as gas-pipeline networks. ‘Advanced Materials’, ‘Energy-Efficiency’ and ‘Transport’ are key problems for the future society which definitely deserve public funding by national and international agencies.},
address = {Berlin Heidelberg},
author = {Leugering, Günter and Martin, Alexander and Stingl, Michael},
booktitle = {Production Factor Mathematics},
doi = {10.1007/978-3-642-11248-5_14},
editor = {Martin Grötschel, Klaus Lucas, Volker Mehrmann},
faupublication = {yes},
pages = {263-276},
peerreviewed = {unknown},
publisher = {Springer},
title = {{Topology} and {Dynamic} {Networks}: {Optimization} with {Application} in {Future} {Technologies}},
year = {2010}
}
@article{faucris.121780824,
abstract = {Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy network},
author = {Groß, Martin and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Skutella, Martin},
doi = {10.1002/net.21865},
faupublication = {yes},
journal = {Networks},
keywords = {Maximum flow problem, Network reduction, Potential networks, Potential-based flows, Series-parallel graphs.},
peerreviewed = {Yes},
title = {{Algorithmic} {Results} for {Potential}-{Based} {Flows}: {Easy} and {Hard} {Cases}},
url = {http://www.optimization-online.org/DB_HTML/2017/08/6185.html},
year = {2018}
}
@misc{faucris.214630022,
abstract = {Globalized robust optimization has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection depending on the distance of the realized scenario from the predefined uncertainty set. In this work, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its usability for discrete optimization. We show that in this case, the generalized robust counterpart possesses algorithmically tractable reformulations for mixed-integer linear nominal problems. Under mild assumptions, we derive a reformulation which uses only slightly more variables and constraints than the standard robust counterpart under Gamma-uncertainty. For combinatorial problems, our globalized robust counterpart remains fixed-parameter tractable, although with a runtime exponential in Gamma. Furthermore,we showthat globalized robust optimization under scaling of the Gamma-uncertainty-sets is NP-hard already in simple cases. We support our theoretical findings by experimental results on the globalized robust versions of the minimum-spanning-tree, shortest-path and knapsack problems. It turns out that our algorithmically tractable reformulations are not more difficult to solve than the respective standard robust counterparts while globalized robustness is guaranteed. Moreover, they produce solutions which offer suitable protection against uncertainty while performing very well in the nominal objective function.

In this work we study polyhedra in the context of network flow problems, in which the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation—a common and established approach in many applications. Several methods for modeling piecewise linear functions which provide a complete description for a single network arc are known. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on—but not limited to—the connection between binary variables and flow variables that is used in the multiple choice method or the convex combination method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art mixed-integer program solver greatly benefits from using our cutting planes for random and realistic network topologies.