90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Document Type
- ZIB-Report (15)
Has Fulltext
- yes (15) (remove)
Is part of the Bibliography
- no (15)
Keywords
- acyclic orientations (2)
- bipolar orientations (2)
- branch-and-bound (2)
- potential-driven network flows (2)
- ASTS orientations (1)
- Buchungsvalidierung (1)
- Gasnetzplanung (1)
- MINLP model (1)
- MINLPs (1)
- Nominierungsvalidierung (1)
- Technische Kapazitäten (1)
- Topologieplanung (1)
- approximate convex decomposition (1)
- bound tightening (1)
- column generation (1)
- competitive analysis (1)
- compressor station (1)
- convex hull reformulation (1)
- disjunctive set (1)
- elevator control (1)
- elevator control, online optimization, reoptimization algorithms, column generation (1)
- entry-exit model (1)
- enumeration algorithm (1)
- flow orientations (1)
- flow patterns (1)
- freely allocable capacity (1)
- gas compressor modeling (1)
- gas compressor modeling, polyhedral model, accuracy, z factor (1)
- gas network optimization (1)
- large-scale mixed-integer nonlinear programming (1)
- mixed-integer nonlinear programming (1)
- model reformulation (1)
- multi-way compressor station (1)
- multiple sources and sinks (1)
- nonlinear model (1)
- online algorithms (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- operations research in energy (1)
- polyhedral model (1)
- probabilistic analysis (1)
- reoptimization (1)
- survey (1)
Institute
Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.
We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm.
We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.