Primal Heuristics for Branch and Price: The Assets of Diving Methods
From MaRDI portal
Publication:5138257
DOI10.1287/ijoc.2018.0822OpenAlexW2622743854MaRDI QIDQ5138257
Eduardo Uchoa, Ruslan Sadykov, Issam Tahiri, François Vanderbeck, Artur Alves Pessoa
Publication date: 3 December 2020
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01237204v3/file/phcgWorkPap.pdf
column generationvertex coloringprimal heuristicscutting stockmatheuristicsbranch and pricegeneralized assignmentrounding heuristicsdiving heuristics
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Mathematical programming (90Cxx)
Related Items
Improving Variable Orderings of Approximate Decision Diagrams Using Reinforcement Learning ⋮ A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering ⋮ Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems ⋮ A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service ⋮ A three-phase matheuristic algorithm for the multi-day task assignment problem ⋮ Matheuristics: survey and synthesis ⋮ Bin Packing Problem with Time Lags ⋮ Integral Column Generation for Set Partitioning Problems with Side Constraints ⋮ Integer programming column generation: accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems ⋮ Improving energy aware nanosatellite task scheduling by a branch-cut-and-price algorithm ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ A generic exact solver for vehicle routing and related problems ⋮ Consensus-based Dantzig-Wolfe decomposition ⋮ A nested benders decomposition-based algorithm to solve the three-stage stochastic optimisation problem modeling population-based breast cancer screening ⋮ A rotation-based branch-and-price approach for the nurse scheduling problem ⋮ Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems ⋮ An exact column-generation approach for the lot-type design problem ⋮ A column generation-based diving heuristic to solve the multi-project personnel staffing problem with calendar constraints and resource sharing ⋮ Solving bin packing problems using VRPSolver models ⋮ Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers ⋮ Combining Dantzig-Wolfe and Benders decompositions to solve a large-scale nuclear outage planning problem ⋮ Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: a column-generation-based approach ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut ⋮ Generalized relax-and-fix heuristic
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- The discrete time window assignment vehicle routing problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Optimal interval scheduling with a resource constraint
- A set-covering based heuristic algorithm for the periodic vehicle routing problem
- Quantum annealing of the graph coloring problem
- Branching in branch-and-price: A generic scheme
- An exact method with variable fixing for solving the generalized assignment problem
- A survey of very large-scale neighborhood search techniques
- Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
- Feasibility pump 2.0
- Local branching
- Exploring relaxation induced neighborhoods to improve MIP solutions
- A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
- Solving a network design problem
- Maximum-weight stable sets and safe lower bounds for graph coloring
- The distance constrained multiple vehicle traveling purchaser problem
- Column-generation based bounds for the homogeneous areas problem
- An exact algorithm for parallel machine scheduling with conflicts
- A feasibility pump heuristic for general mixed-integer problems
- Improving the feasibility pump
- A generic view of Dantzig--Wolfe decomposition in mixed integer programming
- A path relinking approach with ejection chains for the generalized assignment problem
- The feasibility pump
- A branch-and-price-and-cut approach for sustainable crop rotation planning
- Column Generation based Primal Heuristics
- A Column-Generation Based Tactical Planning Method for Inventory Routing
- A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times
- Reformulation and Decomposition of Integer Programs
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- A Minimal Algorithm for the 0-1 Knapsack Problem
- A Computational Study of Search Strategies for Mixed Integer Programming
- A heuristic column generation method for the heterogeneous fleet VRP
- A Column Generation Approach for Large-Scale Aircrew Rostering Problems
- A set‐partitioning‐based exact algorithm for the vehicle routing problem
- Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
- Primal Heuristics for Branch-and-Price Algorithms
- Implementing Mixed Integer Column Generation
- Recursive Computational Procedure for Two-dimensional Stock Cutting
