ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (425)
- Habilitation (4)
Keywords
- mixed integer programming (25)
- integer programming (21)
- constraint integer programming (13)
- branch-and-bound (11)
- mixed-integer programming (11)
- Mixed Integer Programming (9)
- Optimierung (9)
- MINLP (8)
- combinatorial optimization (8)
- line planning (8)
- Mixed-Integer Nonlinear Programming (7)
- branch-and-cut (7)
- constraint programming (7)
- domain propagation (7)
- Ganzzahlige Programmierung (6)
- column generation (6)
- cumulative constraint (6)
- Integer Programming (5)
- Network Design (5)
- Periodic timetabling (5)
- branching rule (5)
- online optimization (5)
- primal heuristic (5)
- primal heuristics (5)
- Constraint Programming (4)
- Large Neighborhood Search (4)
- Linienplanung (4)
- MIP (4)
- Optimization (4)
- Periodic Event Scheduling Problem (4)
- Primal Heuristic (4)
- System Dynamics (4)
- computational complexity (4)
- conflict analysis (4)
- large neighborhood search (4)
- linear programming (4)
- mixed-integer nonlinear programming (4)
- nonconvex (4)
- optimization software (4)
- parallelization (4)
- presolving (4)
- state-dependent processor sharing (4)
- Column Generation (3)
- Cumulative Scheduling (3)
- Kombinatorische Optimierung (3)
- MIQCP (3)
- Mixed-Integer Programming (3)
- Nahverkehr (3)
- Online-Optimierung (3)
- Operations Research (3)
- Optimal Experimental Design (3)
- Periodic Timetabling (3)
- Pooling Problem (3)
- Pseudo-Boolean (3)
- Relaxations (3)
- SDP (3)
- branch-and-price (3)
- computer algebra (3)
- counting (3)
- duty scheduling (3)
- elevator control (3)
- global optimization (3)
- maximum-weight connected subgraph (3)
- mixed-integer semidefinite programming (3)
- network aggregation (3)
- network design (3)
- online algorithms (3)
- polyhedral combinatorics (3)
- propagation (3)
- public transport (3)
- rapid branching (3)
- robust optimization (3)
- scheduling (3)
- sojourn time (3)
- strong branching (3)
- transfers (3)
- Aufzugssteuerung (2)
- Automatic Differentiation (2)
- Branch-And-Cut (2)
- Combinatorial Optimization (2)
- Crack (2)
- Cutting Planes (2)
- Energetic Reasoning (2)
- Fahrplanung (2)
- Fallstudie (2)
- Flows in graphs (2)
- Game Theory (2)
- Gemischt-Ganzzahlige Programmierung (2)
- Hilbert's projective metric (2)
- IP (2)
- Linienplan (2)
- Lipschitz Continuity (2)
- M/GI/m-PS (2)
- MIPLIB (2)
- Mixed Integer Nonlinear Programming (2)
- Nachbarschaftssuche (2)
- Netzwerkaggregation (2)
- Nonsmooth (2)
- OBBT (2)
- Optimierungssoftware (2)
- ParaSCIP (2)
- Passenger routing (2)
- Piecewise Linearization (2)
- Preisplanung (2)
- Primalheuristik (2)
- Primalheuristiken (2)
- Public transport (2)
- REDUCE (2)
- Railway Slot Allocation (2)
- Railway Track Allocation (2)
- Relaxation (2)
- Robust Optimization (2)
- SCIP (2)
- SOCP (2)
- Scheduling (2)
- Semidefinite Programming (2)
- Stackelberg Equilibrium (2)
- Steiner tree (2)
- Steiner tree optimization (2)
- Steiner tree packing (2)
- Steiner tree problems (2)
- Stochastische Dominanz (2)
- System Dynamics; Mixed-Integer Nonlinear Optimization (2)
- Train Timetabling (2)
- Train Timetabling Problem (2)
- Trapezoidal Rule (2)
- Ubiquity Generator Framework (2)
- Vehicle Routing Problem (2)
- Zählen (2)
- abs-normal form (2)
- acyclic orientations (2)
- bipolar orientations (2)
- block structure (2)
- bound tightening (2)
- branch and bound (2)
- case study (2)
- chip verification (2)
- column generation framework (2)
- competitive analysis (2)
- cutting planes (2)
- demand function (2)
- direct connection (2)
- discrete choice model (2)
- discrete equations (2)
- dual degeneracy (2)
- duty templates (2)
- energy efficiency (2)
- energy system models (2)
- exact computation (2)
- facets (2)
- fare planning (2)
- gas networks (2)
- integrable systems (2)
- large polynomial systems (2)
- lognormal duration (2)
- maximum-weight connected subgraph problem (2)
- metric inequalities (2)
- mixed integer nonlinear programming (2)
- mixed-integer linear programming (2)
- mixed-integer quadratically constrained programming (2)
- moments (2)
- optimality-based bound tightening (2)
- optimization solver (2)
- optimization-based bound tightening (2)
- optional activities (2)
- potential-driven network flows (2)
- preprocessing (2)
- prize-collecting Steiner tree problem (2)
- probabilistic analysis (2)
- railway track allocation (2)
- resource-constrained project scheduling (2)
- routing (2)
- scip (2)
- search strategy (2)
- set partitioning (2)
- shortest path routing (2)
- stochastic dominance (2)
- telecommunications (2)
- traveling salesman problem (2)
- vehicle positioning (2)
- öffentlicher Verkehr (2)
- 0-1 Program (1)
- ADOL-C (1)
- ALOHA (1)
- ASTS orientations (1)
- Algorithm Analysis (1)
- Algorithmengeschichte (1)
- Algorithmic Differentiation (1)
- Algorithmus (1)
- Ant Colony Optimization (1)
- Approximation Algorithms (1)
- Approximation Hierarchies (1)
- Approximation hierarchies (1)
- Approximationsalgorithmen (1)
- Aufzugsgruppensteuerung (1)
- Ausubel Milgrom Proxy Auction Mechanism (1)
- Automatic differentiation (1)
- BBAW (1)
- Balanced Cuts (1)
- Bandwidth allocation (1)
- Base Station Cooperation (1)
- Benders decomposition (1)
- Benders' decomposition (1)
- Bicriteria Optimization (1)
- Biobjective Optimization (1)
- Bipartite matching (1)
- Bounds Strengthening (1)
- Branch and Bound (1)
- Branch and Cut (1)
- Branch and bound method (1)
- Branch-and-Bound, Mixed-Integer Programming (1)
- Branch-and-Cut (1)
- Branchwidth (1)
- Buchungsvalidierung (1)
- Bundesliga (1)
- Bundle Method (1)
- CPAIOR (1)
- Capacitated Network Design (1)
- Cardinality Constraints (1)
- Cardinality Forcing Inequalities (1)
- Cardinality constraints (1)
- Carvingwidth (1)
- Change-cycle inequality (1)
- Chipverifikation (1)
- Circuit Switching (1)
- Clinch number (1)
- Column generation (1)
- Combinatorial Auction Problem (1)
- Combinatorial Auctions (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Combinatorial optimization (1)
- Computational Cost (1)
- Computational graph (1)
- Connected Facility Location (1)
- Connected Facility Location, Branch-and-Cut, FTTx Deployment (1)
- Connectivity (1)
- Constraint Integer Programming (1)
- Constraintprogrammierung (1)
- Controls in transportation networks (1)
- Copositive Programming (1)
- Copositive programming (1)
- Covering (1)
- Crew Planning (1)
- Cutting plane algorithm (1)
- Cutting planes (1)
- Cycle inequality (1)
- D-optimality (1)
- DIMACS Challenge (1)
- Data Library (1)
- Data Uncertainty (1)
- Degree Property (1)
- Dense Output (1)
- Depot Planning (1)
- Design efficiency (1)
- Dimensionierung (1)
- Disjunctive Programming (1)
- Diskrete Mathematik (1)
- Diskrete Optimierung (1)
- Dispatching von Fahrzeugen (1)
- Distributed Memory (1)
- Drift Minimization (1)
- Duality (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Dynamic Programming (1)
- Dynamic Traffic (1)
- Echzeitoptimierung (1)
- Eigenschaftsprüfer (1)
- Elimination number (1)
- Energy Preservation (1)
- Energy supply systems (1)
- Entry-Exit Model (1)
- Equivalence theorem (1)
- Euclid's algorithm (1)
- Exact Designs (1)
- Exact Large Neighborhood Search (1)
- Exact linear programming (1)
- Exakte Reoptimierung (1)
- Expansion Planning (1)
- Extensible Bin Packing (1)
- Extreme Points (1)
- FORM (1)
- FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency (1)
- Factors (1)
- Fahrplan (1)
- Feasibility Pump (1)
- Flugzeugumlaufplanung (1)
- Gas Distribution Networks (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gas Network Applications (1)
- Gas Network Planning (1)
- Gasnetzplanung (1)
- Gaussian Process (1)
- Generalization (1)
- Generalized Hermite interpolation (1)
- George Dantzig (1)
- Global Optimal Control (1)
- Graph Partitioning (1)
- Graph Separators (1)
- Graphen (1)
- Graphenisomorphie (1)
- Graphs (1)
- Gurobi (1)
- Hall condition (1)
- Hall's Theorem (1)
- Harvest Scheduling (1)
- Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation (1)
- Heuristics (1)
- Hierarchical approach (1)
- Hypergraph (1)
- Hypervolume (1)
- IP-over-WDM (1)
- Implementation (1)
- Infeasibility Detection (1)
- Integer programming (1)
- Integrated Passenger Routing (1)
- Iterative algorithm (1)
- Iterative refinement (1)
- Kalman Filter (1)
- Kardinalitätsbeschränkung (1)
- Kiefer's p-criterion (1)
- Konfliktanalyse (1)
- Kostenaufteilungsprobleme (1)
- König's Theorem (1)
- Kürzeste Wege (1)
- LP solver (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- LRU (1)
- Lagrangian Relaxation (1)
- Late Breaking Abstracts (1)
- Life Cycle Sustainability Assessment (1)
- Line Planning, Extended Formulation, Public Transport (1)
- Linear Programming (1)
- Linear and Integer Programming (1)
- Linear programming (1)
- Lipschitz continuity (1)
- Low-rank solutions (1)
- M/D/2-PS (1)
- MINLP model (1)
- MINLP solver (1)
- MINLP, global optimization, operative planning, water supply networks (1)
- MINLPs (1)
- MIP solver (1)
- MIPLIB2003 (1)
- Markov State Models (1)
- Markov chains (1)
- Markov-Ketten (1)
- Matchings in hypergraphs (1)
- Mathematical Optimization (1)
- Mathematik als Entscheidungshilfe (1)
- Mathematikunterricht in Schulen (1)
- Matroid Polytope (1)
- Matroid-Polytop (1)
- Matroids (1)
- Maximum Coverage (1)
- Mehrfachausfälle (1)
- Mengenüberdeckung (1)
- Metaheuristic (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Linear Programming (1)
- Mixed-Integer Nonlinear Nonconvex Stochastic Optimization (1)
- Mixed-Integer Nonlinear Optimization (1)
- Mixed-Integer Programming solvers (1)
- Mixed-Intger Programming (1)
- Mixed-integer linear programming (1)
- Model-based optimal design (1)
- Modelling (1)
- Moore recurrences (1)
- Multi-Criteria Optimisation (1)
- Multiband Robust Optimization (1)
- Multiband Robustness (1)
- Multiobjective Shortest Path Problem (1)
- Multiperiod Design (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- Multiresponse experiments (1)
- Multistage (1)
- NESS (1)
- Nachfragefunktion (1)
- Network Design, Demand Uncertainty, Robust Optimization, Telecommunications (1)
- Network Evolution (1)
- Network Optimization (1)
- Network expansion (1)
- Network measurements (1)
- Netzplanung (1)
- Newton barrier method (1)
- Node merging (1)
- Nominierungsvalidierung (1)
- Non-Cooperative Two-Person Games; Mixed-Integer Nonlinear Optimization (1)
- Non-reversible Markov Processes (1)
- Nonconvex Optimization (1)
- Nonconvexity (1)
- Nonlinear Network Design Applications (1)
- Nonlinear Network Flow (1)
- Nonlinear Optimization (1)
- Nonlinear Programming (1)
- Nonlinear programming (1)
- Nonsmooth Taylor polynomial/series (1)
- Normal hypergraphs (1)
- OR in energy (1)
- Online Optimization (1)
- Online-Algorithmen (1)
- Onlinealgorithmen (1)
- Onlineoptimierung (1)
- Opacity (1)
- Open Access, Maßnahmen, Empfehlungen (1)
- Optical access networks (1)
- Optimal Control (1)
- Optimal Design (1)
- Optimal Design of Experiments (1)
- Optimal design (1)
- Optimal design of computer experiments (1)
- Optimal design of experiments (1)
- Optimal operation (1)
- Optische Zugangsnetze (1)
- Orbitope (1)
- Output-Sensitive Multiobjective Combinatorial Problems (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Packing (1)
- Packing problems (1)
- Paging (1)
- Parallel Computing (1)
- Parallel processing (1)
- Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack (1)
- Parameterized complexity (1)
- Partition Inequalities (1)
- Paths (1)
- Piecewise Linear Approximation (1)
- Polyhedral Combinatorics (1)
- Polymatrix game (1)
- Polynomial Time Approximability (1)
- Praxisstudie (1)
- Price of Anarchy (1)
- Primal-Dual Approximation (1)
- Probabilistische Analyse (1)
- Problem Instances (1)
- Problembibliothek (1)
- Produktionsfaktor Mathematik (1)
- Progress measures (1)
- Propagation Algorithm (1)
- Protein Folding (1)
- Proximale Bündelmethode (1)
- Public Transit (1)
- Quadratic Optimization (1)
- Quadratic Programming (1)
- Racing ParaSCIP (1)
- Railway Optimization (1)
- Railway Scheduling (1)
- Railway Track Assignment (1)
- Random Access Channel (1)
- Randomisierte Algorithmen (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (1)
- Reduce (1)
- Restart (1)
- Robust Optimization, Multiband Uncertainty, Compact Robust Counterpart, Cutting Planes, Probabilistic Bound (1)
- Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design (1)
- Robust minmax designs (1)
- Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching (1)
- Rolling Stock Rostering (1)
- Round-robin tournament (1)
- Routing (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- SCIP-Jack (1)
- SOCP Representability (1)
- Scenario Decomposition (1)
- Scenario Technique; System Dynamics (1)
- Scheduling, Extended Formulations, Network Migration, WDM Networks (1)
- Second Order Cone Programming (1)
- Security Games (1)
- Self Organizing Networks (SONs) (1)
- Self-Avoiding Path (1)
- Semidefinite Packing Problem (1)
- Semidefinite programming (1)
- Separation algorithm (1)
- Separationsalgorithmus (1)
- Shortest Path Routing (1)
- Shortest Routes in Public Transport (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Spaltenerzeugung (1)
- Spaltengenerierung (1)
- Sparse kernels (1)
- Spieltheorie (1)
- Spline Interpolation (1)
- Sport (1)
- Sports league (1)
- Stackelberg game (1)
- Standard Quadratic Programming (1)
- Steiner Connectivity Problem (1)
- Steiner Tree (1)
- Steiner Tree Generalization (1)
- Steiner Tree Problem (1)
- Steiner connectivity (1)
- Steiner tree problem (1)
- Steiner tree solver (1)
- Steiner tree variants (1)
- Steiner trees (1)
- Stochastic Programming (1)
- Stochastic Scheduling (1)
- Supercomputer (1)
- Sustainability Indicator (1)
- Sustainability Indicators (1)
- Sweep Line (1)
- Sweep Line Algorithm (1)
- Symmetrie-Brechung (1)
- Symmetrie-Erkennung (1)
- TSP (1)
- Tail Assignment (1)
- Tail assignment (1)
- Taktfahrplan (1)
- Technische Kapazitäten (1)
- Telecommunication (1)
- Telecommunications (1)
- Telota (1)
- Ticket prices (1)
- Tiebreaking criteria (1)
- Toll Enforcement (1)
- Topologieplanung (1)
- Topology Optimization (1)
- Topology Planning (1)
- Total Unimodularity (1)
- Track Allocation (1)
- Track Allocation Problem (1)
- Traffic Uncertainty (1)
- Train Dispatching (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Traveling-Salesman-Problem (1)
- Treewidth (1)
- UMTS (1)
- Umsteigen (1)
- Union of Polytopes (1)
- Valid Inequalities (1)
- Value Creation Process (1)
- Variable-Depth Neighborhood Search (1)
- Vehicle scheduling (1)
- Vickrey Auction (1)
- Vickrey Auktion (1)
- Volume Algorithm (1)
- Wahlverfahren und Mathematik (1)
- Wegeprobleme (1)
- Wireless Communications (1)
- Zielrufsteuerung (1)
- Zweistufiges Problem (1)
- abs-linear form (1)
- absolute convergence (1)
- activity network (1)
- adaptive search behavior (1)
- affine adjustable robust counterparts (1)
- affine routing (1)
- algorithm selection (1)
- algorithmic differentiation (1)
- algorithmic piecewise differentiation (AD and APD) (1)
- analytic center (1)
- anlalytic center (1)
- approximate convex decomposition (1)
- approximation algorithm (1)
- approximation algorithms (1)
- approximations (1)
- assignment (1)
- authentischer Mathematikunterricht (1)
- automated test generation (1)
- automatische Test Generierung (1)
- balanced hypergraph (1)
- benchmarking (1)
- bicriteria optimization (1)
- bilevel optimization (1)
- bilinear terms (1)
- binpacking with side constraints (1)
- bivariate functions (1)
- bounds (1)
- branch and cut (1)
- branch-cut-and-price framework (1)
- busy period (1)
- capacity optimization (1)
- chains (1)
- clique polytope (1)
- coarse-to-fine approach (1)
- combinatorial packing (1)
- compact formulation (1)
- complexity (1)
- compressed sparse row format (1)
- compressor station (1)
- computational (1)
- configuration models (1)
- conflict learning (1)
- connectivity (1)
- conservation laws (1)
- constant batch size (1)
- convex envelope (1)
- convex hull reformulation (1)
- convex relaxation (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- cost allocation game (1)
- cplex (1)
- crew rostering (1)
- cumulative constraints (1)
- cut selection (1)
- cut-based inequalities (1)
- cutset inequalities (1)
- cycle embedding problem (1)
- cycles (1)
- data library (1)
- data sets (1)
- descrete choice (1)
- destination call system (1)
- deterministic parallelism (1)
- directed hypergraphs (1)
- discrete optimization (1)
- disjunctive set (1)
- diskrete Mathematik (1)
- diskrete Optimierung (1)
- driver satisfaction (1)
- dual proof analysis (1)
- dual reductions (1)
- duty rostering (1)
- dynamic programming (1)
- elevator control, online optimization, reoptimization algorithms, column generation (1)
- elevator group control (1)
- energetic reasoning (1)
- energy optimization, non-linear optimization, smart grid (1)
- entry-exit model (1)
- enumeration algorithm (1)
- eulerian multigraphs (1)
- evaluation procedures (1)
- exact rational integer programming (1)
- exact reoptimation (1)
- extremal combinatorics (1)
- extremal combinatorics, extremal set theory, cutting plane, exact integer programming (1)
- f-factors in hypergraphs (1)
- facet (1)
- facet classification (1)
- fares (1)
- fix-and-propagate (1)
- flow orientations (1)
- flow patterns (1)
- forecasting (1)
- formal chip verification (1)
- formale Chip Verifikation (1)
- forward mode propagation (1)
- freely allocable capacity (1)
- freight train routing (1)
- ganzzahlige Programme (1)
- ganzzahlige Programmierung (1)
- gas compressor modeling (1)
- gas compressor modeling, polyhedral model, accuracy, z factor (1)
- gas network optimization (1)
- gas transport optimization (1)
- gemischt-ganzzahlige Programmierung (1)
- generalized Taylor expansion (1)
- generalized flow formula (1)
- generalized hermite interpolation (1)
- generic column generation (1)
- graph ismorphism (1)
- graph segmentation (1)
- graph transformation (1)
- grid graphs (1)
- high performance computing (1)
- high-performance computing (1)
- hop constraints (1)
- hyperassignment (1)
- hyperassignments (1)
- hypergraph (1)
- hypergraphs (1)
- ideal matrices (1)
- impatient customers (1)
- implicit generation of splines (1)
- inequality (1)
- infinite-server (1)
- integer characterizations (1)
- integrated scheduling (1)
- interior point algorithm (1)
- interior-point method (1)
- interior-point methods (1)
- kombinatorische Optimierung (1)
- kürzeste-Wege Routing (1)
- large scale optimization (1)
- large-scale integer programming (1)
- large-scale mixed-integer nonlinear programming (1)
- line planning, transfers,Steiner connectivity problem (1)
- linear ODEs (1)
- linear programming bounds (1)
- linear relaxation (1)
- linear underestimator (1)
- linearization (1)
- locality of reference (1)
- locally exponential service time (1)
- lognormal distribution (1)
- lot-sizing (1)
- machine learning (1)
- macroscopic railway modeling (1)
- makroskopische Bahnmodellierung (1)
- massive parallization (1)
- matching (1)
- mathematical programming (1)
- matrix geometric mean (1)
- max-cut (1)
- mengerian hypergraph (1)
- micro chip (1)
- mixed integer programming; primal heuristics; conflict analysis; branch-and-bound (1)
- mixed integer quadratically constrained programming (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- mixed-integer programs (1)
- mixed-integer quadratically constrained programs (1)
- mixed-integer-programming (1)
- model reformulation (1)
- modeling (1)
- multi armed bandit (1)
- multi armed bandit problem (1)
- multi-commodity flow problem (1)
- multi-commodity flows (1)
- multi-criteria optimization (1)
- multi-hour (1)
- multi-layer (1)
- multi-layer approach (1)
- multi-layer network design (1)
- multi-period (1)
- multi-way compressor station (1)
- multiobjective optimization (1)
- multiple knapsack problem with color constraints (1)
- multiple sources and sinks (1)
- multistep methods (1)
- network detection (1)
- network flow (1)
- network interdiction (1)
- no-good learning (1)
- nonconvex optimization (1)
- nonlinear model (1)
- nonlinear programming (1)
- nonsmooth integration of differential algebraic equations (DAE and ODE) (1)
- nuisance trend (1)
- online algorithm (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- operations research (1)
- operations research in energy (1)
- optimal design of experiments (1)
- optimal experimental designs (1)
- optimality prediction (1)
- optimization (1)
- optimization in public transport (1)
- optional resources (1)
- orbitopes (1)
- paging (1)
- parallel (1)
- parallel branch-and-bound (1)
- parallel computing (1)
- path (1)
- path problems (1)
- pattern detection (1)
- perfect f-matchings in hypergraphs (1)
- perfect hypergraph (1)
- perfect matchings (1)
- performance measure (1)
- periodic timetable (1)
- periodic timetabling (1)
- periodic timetabling, modulo network simplex, passenger routing (1)
- piecewise linear tangent approximation (1)
- piecewise smooth (1)
- polyhedral model (1)
- polyhedral structure (1)
- portfolio solvers (1)
- positive semidefinite matrices (1)
- power consumption (1)
- pressure drop equation (1)
- pricing (1)
- prize-collecting Steiner tree (1)
- projection (1)
- propagation algorithms (1)
- property checking (1)
- public transit (1)
- public transport optimization (1)
- python (1)
- quadrati (1)
- quadratic complexity (1)
- quadratic programming (1)
- railway capacity (1)
- railway models (1)
- railway models, railway capacity, track allocation framework (1)
- railway operations (1)
- railway planning (1)
- railway rolling stock optimization (1)
- railway timetables (1)
- railway vehicle rotation scheduling (1)
- random environment (1)
- randomized algorithm (1)
- rank 1-solution (1)
- re-optimization (1)
- real time optimation (1)
- recourse (1)
- reduction techniques (1)
- reliability branching (1)
- reoptimization (1)
- resource-constrained project Scheduling (1)
- robust network design (1)
- robust optimization, rolling stock planning (1)
- robuste Optimierung (1)
- rolling stock rotation problem (1)
- rolling-stock-planning (1)
- rostering (1)
- rounding (1)
- semidefinite Programming (1)
- semidefinite cone (1)
- semidefinite duality (1)
- semidefinite representability (1)
- separation (1)
- separation algorithm (1)
- sequential coarse-first-fine-second planning approach (1)
- set covering (1)
- set packing (1)
- shortest paths (1)
- simplex method (1)
- sojourn times (1)
- solution learning (1)
- sport ranking (1)
- steel mill slab design problem (1)
- steel mill slab problem (1)
- supercomputing (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- surrogate relaxation (1)
- survey (1)
- survivable network design (1)
- symmetries (1)
- symmetry (1)
- symmetry breaking (1)
- symmetry detection (1)
- telecommunication network (1)
- telecommunication network design (1)
- tight cuts (1)
- time transformation (1)
- timetabling (1)
- toll billing (1)
- track allocation framework (1)
- treating absolute values (abs, max and min) (1)
- tree-size estimates (1)
- trip timetable (1)
- two-stage problem (1)
- underdetermined systems (1)
- uniform hypergraphs (1)
- unimodal demand (1)
- variable locks (1)
- variable selection (1)
- vehicle dispatching (1)
- vehicle rotation planning (1)
- vehicle routing (1)
- visualization (1)
- waiting time dependent service (1)
- workload (1)
- zählen (1)
- ÖPNV (1)
- Öffentlicher Personenverkehr (1)
- Öffentlicher Verkehr (1)
Institute
- Mathematical Optimization (429) (remove)
23-15
It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.
23-06
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.
23-01
For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version~8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided.
22-28
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.
22-14
The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate the usage of multiple reference vectors in all stages of the FP algorithm. In particular, we use LP-feasible vectors obtained during the main loop to tighten the variable domains before entering the computationally expensive enumeration stage. Moreover, we consider multiple integer reference vectors to explore further optimizing directions and introduce alternative objective scaling terms to balance the contributions of the distance functions and the original MIP objective. Our computational experiments demonstrate that the new method can improve performance on general MIP test sets. In detail, our modifications provide a 29.3% solution quality improvement and 4.0% running time improvement in an embedded setting, needing 16.0% fewer iterations over a large test set of MIP instances. In addition, the method’s success rate increases considerably within the first few iterations. In a standalone setting, we also observe a moderate performance improvement, which makes our version of FP suitable for the two main use-cases of the algorithm.
22-23
Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.
20-26
We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.
20-20
Conflict Analysis for MINLP
(2020)
The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.
20-14
Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains.
20-16
Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.