Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints

DOI10.1016/j.ejor.2016.09.051zbMath1394.90477OpenAlexW2531214128MaRDI QIDQ1751662

Rita Macedo, François Clautiaux, Marie-Émilie Voge, Cláudio Alves, Saïd Hanafi

Publication date: 25 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01410170/file/two_ida.pdf

zbMATH Keywords

integer programmingcombinatorial optimizationaggregation of integer modelsarc-flow integer models

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (17)

Layered graph approaches for combinatorial optimization problems ⋮ An introduction to stochastic bin packing-based server consolidation with conflicts ⋮ New partial aggregations for multicommodity network flow problems: an application to the fixed-charge network design problem ⋮ Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery ⋮ An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem ⋮ A generic exact solver for vehicle routing and related problems ⋮ Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events ⋮ Mathematical models and decomposition methods for the multiple knapsack problem ⋮ Perspectives on integer programming for time-dependent models ⋮ On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems ⋮ New exact techniques applied to a class of network flow formulations ⋮ Optimization for L₁-Norm Error Fitting via Data Aggregation ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ Branch-and-refine for solving time-expanded MILP formulations

Cites Work

• Bin packing and cutting stock problems: mathematical models and exact algorithms
• 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
• An exact algorithm for a single-vehicle routing problem with time windows and multiple routes
• Multi-phase dynamic constraint aggregation for set partitioning type problems
• LP models for bin packing and cutting stock problems
• Friendly bin packing instances without integer round-up property
• Solving network design problems via iterative aggregation
• Arc-flow model for the two-dimensional guillotine cutting stock problem
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Theoretical Investigation of Aggregation in Pseudo-polynomial Network-Flow Models
• Aggregation and Disaggregation Techniques and Methodology in Optimization
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• State-space relaxation procedures for the computation of bounds to routing problems
• `` Strong NP-Completeness Results
• Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
• Surrogate Constraints

This page was built for publication: Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints