90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (134)
- Master's Thesis (9)
- Bachelor's Thesis (7)
- Doctoral Thesis (5)
- Article (1)
Keywords
- mixed integer programming (6)
- mixed-integer programming (6)
- MINLP (5)
- Mixed Integer Programming (5)
- Mixed-Integer Nonlinear Programming (5)
- branch-and-bound (5)
- Mixed-Integer Programming (4)
- Network Design (4)
- Periodic Event Scheduling Problem (4)
- Markov State Models (3)
- NESS (3)
- Non-reversible Markov Processes (3)
- Optimal Experimental Design (3)
- Periodic Timetabling (3)
- Periodic timetabling (3)
- SDP (3)
- branch-and-price (3)
- column generation (3)
- constraint integer programming (3)
- integer programming (3)
- linear programming (3)
- mixed-integer nonlinear programming (3)
- parallelization (3)
- Linear Programming (2)
- MIP (2)
- Optimization (2)
- Relaxations (2)
- SCIP (2)
- SOCP (2)
- Steiner tree optimization (2)
- System Dynamics (2)
- System Dynamics; Mixed-Integer Nonlinear Optimization (2)
- acyclic orientations (2)
- bipolar orientations (2)
- bound tightening (2)
- branch and bound (2)
- branch-and-cut (2)
- column generation framework (2)
- domain propagation (2)
- gas networks (2)
- large-scale integer programming (2)
- maximum-weight connected subgraph (2)
- mixed-integer linear programming (2)
- mixed-integer semidefinite programming (2)
- network aggregation (2)
- optimization solver (2)
- potential-driven network flows (2)
- primal heuristics (2)
- propagation (2)
- rapid branching (2)
- ASTS orientations (1)
- Algorithm Analysis (1)
- Balanced Cuts (1)
- Balanced Hypergraphs (1)
- Biobjective Optimization (1)
- Bipartite matching (1)
- Bounds Strengthening (1)
- Branch and Bound (1)
- Branch-and-Bound, Mixed-Integer Programming (1)
- Branchwidth (1)
- Buchungsvalidierung (1)
- Bundesliga (1)
- Carvingwidth (1)
- Change-cycle inequality (1)
- Clinch number (1)
- Column Generation (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Combinatorial optimization (1)
- Conic Programming (1)
- Connected Facility Location (1)
- Connected Facility Location, Branch-and-Cut, FTTx Deployment (1)
- Constraint Programming (1)
- Controls in transportation networks (1)
- Crew Planning (1)
- Cumulative Scheduling (1)
- Cutting Planes (1)
- Cutting planes (1)
- Cycle inequality (1)
- Data Uncertainty (1)
- Depot Planning (1)
- Duality (1)
- Dynamic Traffic (1)
- Elimination number (1)
- Expansion Planning (1)
- FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency (1)
- Factors (1)
- Game Theory (1)
- Gas Network Applications (1)
- Gasnetzplanung (1)
- Global Optimal Control (1)
- Graph Partitioning (1)
- Graph Separators (1)
- Harvest Scheduling (1)
- Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation (1)
- Heuristics (1)
- Hypervolume (1)
- Infeasibility Detection (1)
- Integer programming (1)
- Integrated Passenger Routing (1)
- Kiefer's p-criterion (1)
- Kombinatorische Optimierung (1)
- Large Neighborhood Search (1)
- Linienplanung (1)
- Low-rank solutions (1)
- MINLP model (1)
- MINLPs (1)
- MIPLIB (1)
- MIQCP (1)
- Master Surgery Scheduling (1)
- Matchings (1)
- Maximum Coverage (1)
- Mengerian Hypergraphs (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed-Integer Linear Programming (1)
- Mixed-Integer Nonlinear Optimization (1)
- Mixed-Integer Programming solvers (1)
- Multiband Robustness (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- Multiresponse experiments (1)
- Nash Equilibrium (1)
- Network Design, Demand Uncertainty, Robust Optimization, Telecommunications (1)
- Network Flows (1)
- Network expansion (1)
- Network measurements (1)
- Node merging (1)
- Nominierungsvalidierung (1)
- Nonlinear Network Design Applications (1)
- Nonlinear Network Flow (1)
- Nonlinear Optimization (1)
- Nonlinear Programming (1)
- Normal Hypergraphs (1)
- OBBT (1)
- OR in energy (1)
- Optical access networks (1)
- Optimal Control (1)
- Optimierung (1)
- Optische Zugangsnetze (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Parallel processing (1)
- Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack (1)
- Parameterized complexity (1)
- Piecewise Linear Approximation (1)
- Polymatrix game (1)
- Polynomial Time Approximability (1)
- Praxisstudie (1)
- Primal Heuristic (1)
- Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization (1)
- Progress measures (1)
- Propagation Algorithm (1)
- Pseudo-Boolean (1)
- Quadratic Optimization (1)
- Racing ParaSCIP (1)
- Railway Optimization (1)
- Railway Scheduling (1)
- Railway Track Assignment (1)
- Restart (1)
- Robust Optimization (1)
- Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design (1)
- Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching (1)
- Rolling Stock Rostering (1)
- Round-robin tournament (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- SCIP-Jack (1)
- Scenario Technique; System Dynamics (1)
- Scheduling (1)
- Scheduling, Extended Formulations, Network Migration, WDM Networks (1)
- Second Order Cone Programming (1)
- Security Game (1)
- Semidefinite Packing Problem (1)
- Shortest Routes in Public Transport (1)
- Spline Interpolation (1)
- Sport (1)
- Sports league (1)
- Stackelberg Equilibrium (1)
- Stackelberg game (1)
- Steiner tree (1)
- Steiner tree problem (1)
- Steiner tree problems (1)
- Steiner tree variants (1)
- Steiner trees (1)
- Technische Kapazitäten (1)
- Telecommunication (1)
- Tiebreaking criteria (1)
- Tight Cuts (1)
- Topologieplanung (1)
- Topology Optimization (1)
- Track Allocation (1)
- Train Timetabling (1)
- Transportation Network (1)
- Treewidth (1)
- Ubiquity Generator Framework (1)
- Variable-Depth Neighborhood Search (1)
- Vehicle scheduling (1)
- adaptive search behavior (1)
- algorithm selection (1)
- anlalytic center (1)
- approximate convex decomposition (1)
- benchmarking (1)
- bilevel optimization (1)
- bilinear terms (1)
- binpacking with side constraints (1)
- branching rule (1)
- capacity optimization (1)
- chains (1)
- coarse-to-fine approach (1)
- combinatorial optimization (1)
- competitive analysis (1)
- compressor station (1)
- configuration models (1)
- convex hull reformulation (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- cut selection (1)
- cycle embedding problem (1)
- data sets (1)
- deterministic parallelism (1)
- disjunctive set (1)
- dynamic programming (1)
- elevator control (1)
- elevator control, online optimization, reoptimization algorithms, column generation (1)
- energy optimization, non-linear optimization, smart grid (1)
- energy system models (1)
- entry-exit model (1)
- enumeration algorithm (1)
- exact rational integer programming (1)
- extremal combinatorics (1)
- facets (1)
- flow orientations (1)
- flow patterns (1)
- forecasting (1)
- freely allocable capacity (1)
- freight train routing (1)
- gas compressor modeling (1)
- gas compressor modeling, polyhedral model, accuracy, z factor (1)
- gas network optimization (1)
- generalized flow formula (1)
- global optimization (1)
- graph segmentation (1)
- high-performance computing (1)
- hop constraints (1)
- interior-point methods (1)
- large neighborhood search (1)
- large-scale mixed-integer nonlinear programming (1)
- line planning (1)
- machine learning (1)
- mathematical programming (1)
- matrix geometric mean (1)
- maximum-weight connected subgraph problem (1)
- mixed integer nonlinear programming (1)
- mixed-integer quadratically constrained programs (1)
- model reformulation (1)
- multi armed bandit (1)
- multi armed bandit problem (1)
- multi-commodity flows (1)
- multi-layer approach (1)
- multi-way compressor station (1)
- multiobjective optimization (1)
- multiple knapsack problem with color constraints (1)
- multiple sources and sinks (1)
- network flow (1)
- network interdiction (1)
- nonconvex (1)
- nonconvex optimization (1)
- nonlinear model (1)
- nuisance trend (1)
- online algorithms (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- operations research in energy (1)
- optimal design of experiments (1)
- optimal experimental designs (1)
- optimality prediction (1)
- optimality-based bound tightening (1)
- optimization (1)
- optimization in public transport (1)
- optimization software (1)
- optimization-based bound tightening (1)
- parallel (1)
- pattern detection (1)
- periodic timetabling (1)
- polyhedral model (1)
- portfolio solvers (1)
- pressure drop equation (1)
- prize-collecting Steiner tree (1)
- prize-collecting Steiner tree problem (1)
- probabilistic analysis (1)
- projection (1)
- python (1)
- railway capacity (1)
- railway models (1)
- railway operations (1)
- railway planning (1)
- railway timetables (1)
- railway track allocation (1)
- railway vehicle rotation scheduling (1)
- rank 1-solution (1)
- reduction techniques (1)
- reliability branching (1)
- reoptimization (1)
- robust optimization, rolling stock planning (1)
- rolling stock rotation problem (1)
- semidefinite representability (1)
- separation (1)
- sequential coarse-first-fine-second planning approach (1)
- set partitioning (1)
- simplex (1)
- sport ranking (1)
- steel mill slab design problem (1)
- strong branching (1)
- surrogate relaxation (1)
- survey (1)
- telecommunications (1)
- toll billing (1)
- track allocation framework (1)
- tree-size estimates (1)
- unimodal demand (1)
- visualization (1)
- ÖPNV (1)
Institute
- Mathematical Optimization (156) (remove)
In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll für eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zunächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fällewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur Lösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen
werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegrößen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich größeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden.
In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.
In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.
We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.
In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT.
Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs.
We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.
Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.
Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.