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)
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.
Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.
Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.
Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib.
This paper investigates the estimation of the size of Branch-and-Bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B&B search, such as the gap, and propose a new measure, which we call leaf frequency.
We study two simple ways to transform these progress measures into B&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model.
In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP.
The SCIP Optimization Suite provides a collection of software packages for
mathematical optimization centered around the constraint integer programming frame-
work SCIP. This paper discusses enhancements and extensions contained in version 7.0
of the SCIP Optimization Suite. The new version features the parallel presolving library
PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op-
timization problems and can be used stand-alone or integrated into SCIP via a presolver
plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im-
provements in the Benders’ decomposition solver of SCIP, user-defined decomposition
structures can be read, which are used by the automated Benders’ decomposition solver
and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation
that is used to predict the completion of the overall solving process and potentially
trigger restarts. Moreover, substantial performance improvements of the MIP core were
achieved by new developments in presolving, primal heuristics, branching rules, conflict
analysis, and symmetry handling. Last, not least, the report presents updates to other
components and extensions of the SCIP Optimization Suite, in particular, the LP solver
SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.
In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.
Maximal Quadratic-Free Sets
(2019)
The intersection cut paradigm is a powerful framework that facilitates
the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a
simplicial conic relaxation of S and an S-free set: a convex zone whose
interior does not intersect S. Ideally, such S-free set would be maximal
inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how
to construct maximal S-free sets when S is defined as a general quadratic
inequality. Our maximal S-free sets are such that efficient separation of
a vertex in LP-based approaches to quadratically constrained problems is
guaranteed. To the best of our knowledge, this work is the first to provide
maximal quadratic-free sets.
Improved optimization models for potential-driven network flow problems via ASTS orientations
(2019)
The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.
The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments.