90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (175)
- Master's Thesis (17)
- Bachelor's Thesis (9)
- Doctoral Thesis (6)
- Article (2)
- In Proceedings (1)
Keywords
- Mixed-Integer Programming (9)
- Periodic Timetabling (9)
- Mixed Integer Programming (8)
- Periodic Event Scheduling Problem (8)
- mixed-integer programming (8)
- Mixed-Integer Nonlinear Programming (6)
- mixed integer programming (6)
- MINLP (5)
- branch-and-bound (5)
- Network Design (4)
- Markov State Models (3)
- NESS (3)
- Non-reversible Markov Processes (3)
- Online Optimization (3)
- Optimal Experimental Design (3)
- Periodic timetabling (3)
- Railway Timetabling (3)
- SDP (3)
- branch-and-price (3)
- column generation (3)
- constraint integer programming (3)
- integer programming (3)
- linear programming (3)
- mixed-integer linear programming (3)
- mixed-integer nonlinear programming (3)
- parallelization (3)
- Cutting Planes (2)
- Graph Partitioning (2)
- Heuristic (2)
- Linear Programming (2)
- MIP (2)
- Machine Learning (2)
- Nonlinear Programming (2)
- Optimization (2)
- Predictive Maintenance (2)
- Public Transport (2)
- Railway Track Allocation (2)
- Relaxations (2)
- Rolling Stock Rotation Planning (2)
- Routing (2)
- SCIP (2)
- SOCP (2)
- Steiner tree optimization (2)
- System Dynamics (2)
- System Dynamics; Mixed-Integer Nonlinear Optimization (2)
- Telecommunications (2)
- Timetabling (2)
- acyclic orientations (2)
- bipolar orientations (2)
- bound tightening (2)
- branch and bound (2)
- branch-and-cut (2)
- column generation framework (2)
- cut selection (2)
- cutting plane selection (2)
- domain propagation (2)
- extremal combinatorics (2)
- gas networks (2)
- global optimization (2)
- large-scale integer programming (2)
- maximum-weight connected subgraph (2)
- mixed-integer semidefinite programming (2)
- network aggregation (2)
- optimal control (2)
- optimization solver (2)
- potential-driven network flows (2)
- primal heuristics (2)
- propagation (2)
- rapid branching (2)
- ASTS orientations (1)
- Airline Applications (1)
- Algorithm Analysis (1)
- Artificial Intelligence (1)
- Balanced Cuts (1)
- Balanced Hypergraphs (1)
- Benchmark Solutions (1)
- Benders Decomposition (1)
- Biobjective Optimization (1)
- Bipartite matching (1)
- Boolean Satisfiability Problem (1)
- Bounds Strengthening (1)
- Branch and Bound (1)
- Branch-and-Bound, Mixed-Integer Programming (1)
- Branchwidth (1)
- Buchungsvalidierung (1)
- Bundesliga (1)
- C-stationarity (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)
- Congestion Game (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)
- Convex envelopes (1)
- Crew Planning (1)
- Cumulative Scheduling (1)
- Cut Selection (1)
- Cutting planes (1)
- Cycle Bases (1)
- Cycle inequality (1)
- Data Uncertainty (1)
- Depot Planning (1)
- Duality (1)
- Dynamic Traffic (1)
- Elimination number (1)
- Expansion Planning (1)
- Expansion planning of energy networks (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)
- Gas network optimization (1)
- Gasnetzplanung (1)
- Global Optimal Control (1)
- Graph Algorithms (1)
- Graph Covering (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 Linear Programming (1)
- Integer linear program (1)
- Integer programming (1)
- Integrated Passenger Routing (1)
- Interval Data (1)
- Kiefer's p-criterion (1)
- Kombinatorische Optimierung (1)
- Large Neighborhood Search (1)
- Line Planning (1)
- Linienplanung (1)
- Logistics (1)
- Low-rank solutions (1)
- Lower Bound (1)
- MINLP model (1)
- MINLPs (1)
- MIPLIB (1)
- MIQCP (1)
- Management Science and Operations Research (1)
- Master Surgery Scheduling (1)
- Matchings (1)
- Mathematical Programming (1)
- Maximum Coverage (1)
- Mengerian Hypergraphs (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness (1)
- Mixed-Integer Linear Programming (1)
- Mixed-Integer Nonlinear Optimization (1)
- Mixed-Integer Programming solvers (1)
- Modeling and Simulation (1)
- Moving Block (1)
- Multiband Robustness (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- Multiresponse experiments (1)
- Nash Equilibrium (1)
- Nash equilibria (1)
- Network Design, Demand Uncertainty, Robust Optimization, Telecommunications (1)
- Network Flows (1)
- Network aggregation (1)
- Network expansion (1)
- Network measurements (1)
- Newton's method (1)
- Node merging (1)
- Nominierungsvalidierung (1)
- Nonlinear Network Design Applications (1)
- Nonlinear Network Flow (1)
- Nonlinear Optimization (1)
- Normal Hypergraphs (1)
- OBBT (1)
- OR in energy (1)
- Optical access networks (1)
- Optimal Control (1)
- Optimierung (1)
- Optische Zugangsnetze (1)
- PESPlib (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- 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)
- Pipe merging (1)
- Polymatrix game (1)
- Polynomial Time Approximability (1)
- Praxisstudie (1)
- Predictive maintenance (1)
- Preprocessing Shortest Path Problems (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)
- QAP (1)
- Quadratic Optimization (1)
- Racing ParaSCIP (1)
- Railway Optimization (1)
- Railway Scheduling (1)
- Railway Track Assignment (1)
- Rescheduling (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)
- Rolling stock rotation planning (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)
- Split Closure (1)
- Sport (1)
- Sports league (1)
- Stackelberg Equilibrium (1)
- Stackelberg game (1)
- State-expanded graph model (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)
- Test Library (1)
- Tiebreaking criteria (1)
- Tight Cuts (1)
- Topologieplanung (1)
- Topology Optimization (1)
- Track Allocation (1)
- Train Routing (1)
- Train Timetabling (1)
- Transient gas flow transport (1)
- Transportation (1)
- Transportation Network (1)
- Treewidth (1)
- Ubiquity Generator Framework (1)
- Variable-Depth Neighborhood Search (1)
- Variational inequalities (1)
- Vehicle scheduling (1)
- adaptive search behavior (1)
- affine covariant (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)
- composite step methods (1)
- compressor station (1)
- configuration models (1)
- control constraints (1)
- convex hull reformulation (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- cubic regularization (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 networks (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)
- exact rational mixed integer programming (1)
- facets (1)
- flight planning (1)
- flow orientations (1)
- flow patterns (1)
- forecasting (1)
- free flight (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)
- 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 optimization (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)
- multiperiod optimal power flow, distribution network planning, battery storage (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)
- nonlinear time series (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 with PDEs (1)
- optimization-based bound tightening (1)
- parallel (1)
- path-following (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)
- reinforcement learning (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)
- shortest path (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)
- variable selection (1)
- visualization (1)
- ÖPNV (1)
Institute
- Mathematical Optimization (156)
- Mathematical Optimization Methods (34)
- Network Optimization (29)
- Applied Algorithmic Intelligence Methods (14)
- AI in Society, Science, and Technology (9)
- Mathematics of Telecommunication (7)
- Mathematics of Transportation and Logistics (6)
- Mathematical Algorithmic Intelligence (4)
- Numerical Mathematics (4)
- ZIB Allgemein (4)
Periodic timetabling is a challenging planning task in public transport.
As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turnarounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.
Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions.
Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67% of affected MIPLIB 2017 instances by 4%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97% of affected MIPLIB 2017 instances by 5%.
We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles
and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse-
quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.
A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult.
The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.
We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.
Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly.
This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress.
We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite.
Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP.
Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method.
Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework.
All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub.
Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance
(2023)
We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.