Refine
Year of publication
Document Type
- ZIB-Report (29)
- In Proceedings (14)
- Article (9)
- Book chapter (7)
- Master's Thesis (2)
- Book (1)
- Doctoral Thesis (1)
- Other (1)
Is part of the Bibliography
- no (64)
Keywords
- online algorithms (5)
- online optimization (4)
- Online-Optimierung (3)
- elevator control (3)
- probabilistic analysis (3)
- Aufzugssteuerung (2)
- Stochastische Dominanz (2)
- acyclic orientations (2)
- bipolar orientations (2)
- branch-and-bound (2)
- potential-driven network flows (2)
- stochastic dominance (2)
- vehicle dispatching (2)
- ADAC (1)
- ASTS orientations (1)
- Aufzugsgruppensteuerung (1)
- Buchungsvalidierung (1)
- Dial-a-Ride problem (1)
- Dial-a-Ride problem on trees (1)
- Disjunctive Programming (1)
- Dispatching von Fahrzeugen (1)
- Echzeitoptimierung (1)
- Entry-Exit Model (1)
- Exakte Reoptimierung (1)
- Gas Distribution Networks (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gasnetzplanung (1)
- IGNORE strategy (1)
- LRU (1)
- MINLP model (1)
- MINLPs (1)
- Markov chains (1)
- Markov-Ketten (1)
- Mathematical Optimization (1)
- Mixed-Integer Nonlinear Nonconvex Stochastic Optimization (1)
- Nominierungsvalidierung (1)
- Online-Algorithmen (1)
- Onlinealgorithmen (1)
- Onlineoptimierung (1)
- Paging (1)
- Probabilistische Analyse (1)
- Randomisierte Algorithmen (1)
- Technische Kapazitäten (1)
- Topologieplanung (1)
- Topology Planning (1)
- Traveling-Salesman-Problem (1)
- Union of Polytopes (1)
- Volume Algorithm (1)
- Zielrufsteuerung (1)
- Zweistufiges Problem (1)
- approximate convex decomposition (1)
- bound tightening (1)
- column generation (1)
- competitive analysis (1)
- compressor station (1)
- convex hull reformulation (1)
- destination call system (1)
- disjunctive set (1)
- elevator control, online optimization, reoptimization algorithms, column generation (1)
- elevator group control (1)
- entry-exit model (1)
- enumeration algorithm (1)
- exact reoptimation (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)
- high load (1)
- large-scale mixed-integer nonlinear programming (1)
- locality of reference (1)
- mixed-integer nonlinear programming (1)
- model reformulation (1)
- multi-way compressor station (1)
- multiple sources and sinks (1)
- nonlinear model (1)
- online (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- operations research in energy (1)
- optimality gap (1)
- paging (1)
- polyhedral model (1)
- probabilistic competitive analysis (1)
- randomized algorithm (1)
- real time optimation (1)
- real-time (1)
- reoptimization (1)
- soft time windows (1)
- survey (1)
- traveling salesman problem (1)
- two-stage problem (1)
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.
Optimization models often feature disjunctions of polytopes as
submodels. Such a disjunctive set is initially (at best) relaxed to
its convex hull, which is then refined by branching.
To measure the error of the convex relaxation, the (relative)
difference between the volume of the convex hull and the volume of the
disjunctive set may be used. This requires a method to compute the
volume of the disjunctive set. Naively, this can be done via
inclusion/exclusion and leveraging the existing code for the volume
of polytopes. However, this is often inefficient.
We propose a revised variant of an old algorithm by Bieri and Nef
(1983) for this purpose. The algorithm uses a sweep-plane to
incrementally calculate the volume of the disjunctive set as a
function of the offset parameter of the sweep-plane.
Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.