Arc flow formulations based on dynamic programming: theoretical foundations and applications
From MaRDI portal
Publication:2239929
DOI10.1016/J.EJOR.2021.04.024zbMath1487.90204arXiv2010.00558OpenAlexW3091309232MaRDI QIDQ2239929
Manuel Iori, Vinícius Loti de Lima, Cláudio Alves, François Clautiaux, José M. Valério de Carvalho
Publication date: 5 November 2021
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.00558
Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Dynamic programming (90C39) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (11)
A Branch-and-Price Algorithm for the Multiple Knapsack Problem ⋮ Facility location problems on graphs with non-convex neighborhoods ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Tool switching problems in the context of overlay printing with multiple colours ⋮ Exact and heuristic methods for a workload allocation problem with chain precedence constraints ⋮ Dynamic scheduling of patients in emergency departments ⋮ Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model ⋮ Exact solution of network flow models with strong relaxations ⋮ Tool switching problems with tool order constraints ⋮ New exact techniques applied to a class of network flow formulations
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Integer linear programming models for the skiving stock problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Bin packing and related problems: general arc-flow formulation with graph compression
- An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling
- Column generation for extended formulations
- The proper relaxation and the proper gap of the skiving stock problem
- Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
- Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model
- A time-indexed LP-based approach for min-sum job-shop problems
- A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem
- An integer programming model for two- and three-stage two-dimensional cutting stock problems
- A time indexed formulation of non-preemptive single machine scheduling problems
- Exact solution of bin-packing problems using column generation and branch-and-bound
- Stabilized column generation
- Branch-and-price algorithms for the one-dimensional cutting stock problem
- An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
- Layered graph approaches for combinatorial optimization problems
- Logic based Benders' decomposition for orthogonal stock cutting problems
- Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
- Dynamic constraint and variable aggregation in column generation
- Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines
- Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints
- A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
- Mathematical models and decomposition methods for the multiple knapsack problem
- LP models for bin packing and cutting stock problems
- Nominal and robust train timetabling problems
- Perspectives on integer programming for time-dependent models
- Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks
- Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization
- On the exact solution of a large class of parallel machine scheduling problems
- A generic exact solver for Vehicle Routing and related problems
- Improved flow-based formulations for the skiving stock problem
- Friendly bin packing instances without integer round-up property
- Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
- Improved branch-cut-and-price for capacitated vehicle routing
- Novel formulations and modeling enhancements for the dynamic berth allocation problem
- Dynamic graph generation for the shortest path problem in time expanded networks
- Arc-flow model for the two-dimensional guillotine cutting stock problem
- Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time
- A Suggested Computation for Maximal Multi-Commodity Network Flows
- Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
- Using Extra Dual Cuts to Accelerate Column Generation
- Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling
- An Improved Primal Simplex Algorithm for Degenerate Linear Programs
- Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming
- An Introduction to Network Flows over Time
- Theoretical Investigation of Aggregation in Pseudo-polynomial Network-Flow Models
- A Linear Programming Approach to the Cutting-Stock Problem
- Integer Programming Formulation of Traveling Salesman Problems
- The Decomposition Algorithm for Linear Programs
- Mathematical Models and Search Algorithms for the Capacitated p-Center Problem
- Dual-Optimal Inequalities for Stabilized Column Generation
- Polyhedral Characterization of Discrete Dynamic Programming
- New dynamic programming algorithms for the resource constrained elementary shortest path problem
- Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems
- Modeling and Solving the Train Timetabling Problem
- Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
- State-space relaxation procedures for the computation of bounds to routing problems
- A New Linear Programming Approach to the Cutting Stock Problem
- A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
- A pseudopolynomial network flow formulation for exact knapsack separation
- The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
- The Continuous-Time Service Network Design Problem
- Decision Diagrams and Dynamic Programming
- Graph Coloring Lower Bounds from Decision Diagrams
- The Meet-in-the-Middle Principle for Cutting and Packing Problems
- Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
- Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
- Selected Topics in Column Generation
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- Constructing Maximal Dynamic Flows from Static Flows
- Shortest Path Problems with Resource Constraints
- Dynamic Programming Algorithms for the Integer Programming Problem—I: The Integer Programming Problem Viewed as a Knapsack Type Problem
- Vehicle routing problems with multiple trips
- Deriving compact extended formulations via LP-based separation techniques
- Extended formulations in combinatorial optimization
- An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem
This page was built for publication: Arc flow formulations based on dynamic programming: theoretical foundations and applications
