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)
08-48
Given a combinatorial optimization problem and a subset $N$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of $N$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Grötschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.
08-46
Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.
08-43
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.
08-39
It is well known that competitive analysis yields too pessimistic results when applied to the paging problem and it also cannot make a distinction between many paging strategies. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the good performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We show that when sequences are drawn from distributions modelling locality of reference, LRU is stochastically better than any other online paging algorithm.
08-35
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
08-34
We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
08-33
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known.
08-32
Testing is the process of stimulating a system with inputs in order to reveal hidden parts of the system state. In the case of non-deterministic systems, the difficulty arises that an input pattern can generate several possible outcomes. Some of these outcomes allow to distinguish between different hypotheses about the system state, while others do~not. In this paper, we present a novel approach to find, for non-deterministic systems modeled as constraints over variables, tests that allow to distinguish among the hypotheses as good as possible. The idea is to assess the quality of a test by determining the ratio of distinguishing (good) and not distinguishing (bad) outcomes. This measure refines previous notions proposed in the literature on model-based testing and can be computed using model counting techniques. We propose and analyze a greedy-type algorithm to solve this test optimization problem, using existing model counters as a building block. We give preliminary experimental results of our method, and discuss possible improvements.
08-31
This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.
08-30
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.
08-29
Starting with the description of the Traveling Salesmen Problem formulation as given by van Vyve and Wolsey in the article Approximate extended formulations'', we investigate the effects of small variations onto the performance of contemporary mixed integer programming solvers. We will show that even minor changes in the formulation of the model can result in performance difference of more than a factor of 1000. As the results show it is not obvious which changes will result in performance improvements and which not.
08-28
This paper describes several experiments to explore the options for solving a class of mixed integer nonlinear programming problems that stem from a real-world mine production planning project. The only type of nonlinear constraints in these problems are bilinear equalities involving continuous variables, which enforce the ratios between elements in mixed material streams. A branch-and-bound algorithm to handle the integer variables has been tried in another project. However, this branch-and-bound algorithm is not effective for handling the nonlinear constraints. Therefore state-of-the-art nonlinear solvers are utilized to solve the resulting nonlinear subproblems in this work. The experiments were carried out using the NEOS server for optimization. After finding that current nonlinear programming solvers seem to lack suitable preprocessing capabilities, we preprocess the instances beforehand and use an heuristic approach to solve the nonlinear subproblems. In the appendix, we explain how to add a polynomial constraint handler that uses IPOPT as embedded nonlinear programming solver for the constraint programming framework SCIP. This is one of the crucial steps for implementing our algorithm in SCIP. We briefly described our approach and give an idea of the work involved.
08-26
Den kürzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. Über einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Borndörfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung beschäftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Zählen von Lösungen, das, wie wir sehen werden, eng mit dem Zählen von Wegen zusammenhängt. Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche Lösungsmethoden untersuchen. Wie bestimmt man den kürzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle möglichen Wege? Nach einer Einführung in die Graphentheorie und einer Konkretisierung der Probleme wird zunächst für beide eine Lösung mit auf Graphen basierenden Algorithmen vorgestellt. Während der Algorithmus von Dijkstra sehr bekannt ist, habe ich für das Zählen von Wegen einen eigenen Algorithmus auf der Basis der Tiefensuche entwickelt. Im zweiten Teil der Arbeit wird das Konzept der ganzzahligen Programmierung vorgestellt und die Lösungsmöglichkeiten für Wegeprobleme, die sich darüber ergeben. Schließlich wurden die vorgestellten Algorithmen am Beispiel des S- und U-Bahnnetzes von Berlin implementiert und mit Programmen, die die gleichen Fragen über ganzzahlige Programmierung lösen, verglichen.
08-23
Dieser kurze Aufsatz zur Algorithmengeschichte ist Eberhard Knobloch, meinem Lieblings-Mathematikhistoriker, zum 65. Geburtstag gewidmet. Eberhard Knobloch hat immer, wenn ich ihm eine historische Frage zur Mathematik stellte, eine Antwort gewusst – fast immer auch sofort. Erst als ich mich selbst ein wenig und dazu amateurhaft mit Mathematikgeschichte beschäftigte, wurde mir bewusst, wie schwierig dieses „Geschäft“ ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in früheren Zeiten kennen. Man muss zusätzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen“ war, insbesondere, was seinerzeit gültige Beweisideen und -schritte waren, und daher damals keiner präzisen Definition oder Einführung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies möchte ich in diesem Artikel kurz darlegen in der Hoffnung, dass sich Wissenschaftshistoriker dieses Themas noch intensiver annehmen, als sie das bisher tun. Der Grund ist, dass heute Algorithmen viele Bereiche unserer Alltagswelt steuern und unser tägliches Leben oft von funktionierenden Algorithmen abhängt. Daher wäre eine bessere Kenntnis der Algorithmengeschichte von großem Interesse.
08-22
Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.
08-21
Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. könnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale Bürger"' weiss davon nichts, der Schulunterricht könnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zugänglich. Solche Anwendungen, die zusätzlich noch der Lebensumwelt der Schüler zugehören, können dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die Lösung praktischer Fragen, anschaulich zu erläutern. Gerade in der diskreten Mathematik können hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenständiges Entdecken der Schüler entwickelt werden. Wir beginnen mit einigen Beispielen.
08-20
Millionen von Menschen werden allein in Deutschland täglich von Bussen, Bahnen und Flugzeugen transportiert. Der öffentliche Personenverkehr (ÖV) ist von großer Bedeutung für die Lebensqualität einzelner aber auch für die Leistungsfähigkeit ganzer Regionen. Qualität und Effizienz von ÖV-Systemen hängen ab von politischen Rahmenbedingungen (staatlich geplant, wettbewerblich organisiert) und der Eignung der Infrastruktur (Schienensysteme, Flughafenstandorte), vom vorhandenen Verkehrsangebot (Fahr- und Flugplan), von der Verwendung angemessener Technologien (Informations-, Kontroll- und Buchungssysteme) und dem bestmöglichen Einsatz der Betriebsmittel (Energie, Fahrzeuge und Personal). Die hierbei auftretenden Entscheidungs-, Planungs- und Optimierungsprobleme sind z.T. gigantisch und "schreien" aufgrund ihrer hohen Komplexität nach Unterstützung durch Mathematik. Dieser Artikel skizziert den Stand und die Bedeutung des Einsatzes von Mathematik bei der Planung und Durchführung von öffentlichem Personenverkehr, beschreibt die bestehenden Herausforderungen und regt zukunftsweisende Maßnahmen an.
08-19
We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis.
08-18
This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.
08-16
The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany.
08-15
The purpose of this paper is twofold. An immediate practical use of the presented algorithm is its applicability to the parametric solution of underdetermined linear ordinary differential equations (ODEs) with coefficients that are arbitrary analytic functions in the independent variable. A second conceptual aim is to present an algorithm that is in some sense dual to the fundamental Euclids algorithm, and thus an alternative to the special case of a Gr\"{o}bner basis algorithm as it is used for solving linear ODE-systems. In the paper Euclids algorithm and the new dual version' are compared and their complementary strengths are analysed on the task of solving underdetermined ODEs. An implementation of the described algorithm is interactively accessible at http://lie.math.brocku.ca/crack/uode.
08-13
We classify all integrable 3-dimensional scalar discrete affine linear equations $Q_3=0$ on an elementary cubic cell of the lattice ${\mathbb Z}^3$. An equation $Q_3=0$ %of such form is called integrable if it may be consistently imposed on all $3$-dimensional elementary faces of the lattice ${\mathbb Z}^4$. Under the natural requirement of invariance of the equation under the action of the complete group of symmetries of the cube we prove that the only ontrivial(non-linearizable) integrable equation from this class is the well-known dBKP-system.
08-12
Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.
08-11
An algorithmic method using conservation law multipliers is introduced that yields necessary and sufficient conditions to find invertible mappings of a given nonlinear PDE to some linear PDE and to construct such a mapping when it exists. Previous methods yielded such conditions from admitted point or contact symmetries of the nonlinear PDE. Through examples, these two linearization approaches are contrasted.
08-10
The paper describes a method for solution of very large overdetermined algebraic polynomial systems on an example that appears from a classification of all integrable 3-dimensional scalar discrete quasilinear equations $Q_3=0$ on an elementary cubic cell of the lattice ${\mathbb Z}^3$. The overdetermined polynomial algebraic system that has to be solved is far too large to be formulated. A probing' technique which replaces independent variables by random integers or zero allows to formulate subsets of this system. An automatic alteration of equation formulating steps and equation solving steps leads to an iteration process that solves the computational problem.
08-09
In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.
08-08
Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Grötschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.
08-04
Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.
08-01
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.
07-39
07-37
We address the property checking problem for SoC design verification at the register transfer level (RTL) by integrating techniques from integer programming, constraint programming, and SAT solving. Specialized domain propagation and preprocessing algorithms for individual RTL operations extend a general constraint integer programming framework. Conflict clauses are learned by analyzing infeasible LPs and deductions, and by employing reverse propagation. Experimental results show that our approach outperforms SAT techniques for proving the validity of properties on circuits containing arithmetics.
07-36
In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.
07-33
This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years.
07-30
In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP. We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.
07-29
The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.
07-28
In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published. Up to our knowledge, all of them are improvement heuristics. We present a new start heuristic for general MIPs working in the spirit of large neighborhood search. It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP. Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding. Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.
07-26
Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.
07-25
We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.
07-22
We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq$^2$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of Seq and Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of $(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq$^2$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by $O{1.77^d\,d^{d+1}}$. We present lower bounds of $(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the $\ell_p$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are $p$ and $O{p}$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines.
07-21
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps.
07-20
The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
07-15
We provide information on the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design that can be accessed at http://sndlib.zib.de. In version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network planning problem instances. In this paper, we provide a mathematical model for each planning problem considered in the library and describe the data concepts of the SNDlib. Furthermore, we provide statistical information and details about the origin of the data sets.
07-02
This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.
05-45
We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.
05-35
The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.
05-20
In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.
03-39
Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.
03-03
02-25
Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called $c$-competitive if on every input the solution it produces has cost'' at most $c$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.
00-34
This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.