Selected Topics in Column Generation

DOI10.1287/opre.1050.0234zbMath1165.90578OpenAlexW1970355999WikidataQ115213130 ScholiaQ115213130MaRDI QIDQ5322154

Marco E. Lübbecke, Jacques Desrosiers

Publication date: 18 July 2009

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.1050.0234

Mathematics Subject Classification ID

Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Cross line and column generation for the cut covering problem in wireless networks, A column generation approach for a multi-attribute vehicle routing problem, Column generation for a UAV assignment problem with precedence constraints, Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems, Consistency Cuts for Dantzig-Wolfe Reformulations, A column-generation-based algorithm for a resource-constrained project scheduling problem with a fractional shared resource, Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem, Models and algorithms for three-stage two-dimensional bin packing, Constraint-specific recovery network for solving airline recovery problems, A new branch-and-price algorithm for the traveling tournament problem, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, Column generation algorithm for sensor coverage scheduling under bandwidth constraints, Stabilizing branch‐and‐price for constrained tree problems, Integrated job scheduling and network routing, Genetic Column Generation: Fast Computation of High-Dimensional Multimarginal Optimal Transport Problems, Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows, LP-based dual bounds for the maximum quasi-clique problem, First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem, Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time, Simultaneously exploiting two formulations: an exact Benders decomposition approach, Solution approaches for integrated vehicle and crew scheduling with electric buses, A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts, Integrated production and transportation scheduling with order-dependent inventory holding costs, Optimizing package express operations in China, Total coloring and total matching: polyhedra and facets, A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service, On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage, Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization, A column generation-based heuristic for a rehabilitation patient scheduling and routing problem, Branch‐price‐and‐cut for the truck–drone routing problem with time windows, A column generation approach for the team formation problem, Column generation for service assignment in cloud-based manufacturing, An integer programming column generation principle for heuristic search methods, A column‐generation‐based approach to fleet design problems mixing owned and hired vehicles, Branch‐and‐price for energy optimization in multi‐hop wireless sensor networks, A heuristic for the skiving and cutting stock problem in paper and plastic film industries, Estimating the marginal cost to deliver to individual customers, Routing and scheduling of network flows with deadlines and discrete capacity allocation, 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, Efficient emission reduction through dynamic supply mode selection, Improving energy aware nanosatellite task scheduling by a branch-cut-and-price algorithm, Stochastic inventory routing with time-based shipment consolidation, New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems, Adaptive solution prediction for combinatorial optimization, Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows, Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches, New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows, Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem, Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows, Assigning Team Tasks and Multiple Activities to Fixed Work Shifts, Consensus-based Dantzig-Wolfe decomposition, The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm, Exact solution of network flow models with strong relaxations, Regenerator Location Problem in Flexible Optical Networks, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines, Optimization in liner shipping, A Joint Vehicle Routing and Speed Optimization Problem, Detecting critical node structures on graphs: A mathematical programming approach, Multi-Tree Decomposition Methods for Large-Scale Mixed Integer Nonlinear Optimization, Communication-Constrained Expansion Planning for Resilient Distribution Systems, On the minimum cost multiple-source unsplittable flow problem, Optimization in liner shipping, Constraint programming-based column generation, Searching for optimal integer solutions to set partitioning problems using column generation, Constraint programming-based column generation, Joint vehicle assembly‐routing problems: An integrated modeling and optimization approach, The Two Dimensional Bin Packing Problem with Side Constraints, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, One-dimensional cutting stock with a limited number of open stacks: bounds and solutions from a new integer linear programming model, Dual Inequalities for Stabilized Column Generation Revisited, A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem, A novel modeling approach for express package carrier planning, Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation, Vector Space Decomposition for Solving Large-Scale Linear Programs, Projective Cutting-Planes, Solving capacitated part-routing problems with setup times and costs: a Dantzig-Wolfe decomposition-based solution approach, The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing, School bus routing—a column generation approach, A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times, A note on the primal-dual column generation method for combinatorial optimization, Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times, A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants, Cutting planes for branch-and-price algorithms, Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types, A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning, Large-scale optimization with the primal-dual column generation method, A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen, Task assignment with start time-dependent processing times for personnel at check-in counters, Solving the minimum convex partition of point sets with integer programming, Decomposition-based heuristic for the zoning and crop planning problem with adjacency constraints, Fast approximate \(L_\infty\) minimization: speeding up robust regression, Globally optimal clusterwise regression by column generation enhanced with heuristics, sequencing and ending subset optimization, Improving blood products supply through donation tailoring, The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation, All-integer column generation for set partitioning: basic principles and extensions, A path-based solution approach for the green vehicle routing problem, Application of optimization for solving a sawing stock problem with a cant sawing pattern, Dantzig-Wolfe decomposition approach to the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network, Combining column generation and constraint programming to solve the tail assignment problem, A generalization of column generation to accelerate convergence, Two exact algorithms for the traveling umpire problem, Decomposition based hybrid metaheuristics, A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes, A branch-cut-and-price algorithm for the piecewise linear transportation problem, A comparison of column-generation approaches to the synchronized pickup and delivery problem, A branch and price approach for routing and refueling station location model, A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times, A column generation approach for solving the examination-timetabling problem, Bin packing and cutting stock problems: mathematical models and exact algorithms, A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem, Network interdiction via a critical disruption path: branch-and-price algorithms, A hybrid column generation with GRASP and path relinking for the network load balancing problem, Liner shipping network design with deadlines, A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints, A new formulation and approach for the black and white traveling salesman problem, The production routing problem: a review of formulations and solution algorithms, Branch-and-price approaches for the network design problem with relays, The green capacitated multi-item lot sizing problem with parallel machines, Vehicle routing with probabilistic capacity constraints, Lane covering with partner bounds in collaborative truckload transportation procurement, Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows, Exact approaches for the knapsack problem with setups, Combined column-and-row-generation for the optimal communication spanning tree problem, Testing probabilistic models of choice using column generation, Large-scale pickup and delivery work area design, An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges, A branch-price-and-cut algorithm for the workover rig routing problem, A constraint programming based column generation approach to nurse rostering problems, Accelerating the branch-and-price algorithm using machine learning, A branch and price algorithm for the pharmacy duty scheduling problem, Heuristic decomposition approaches for an integrated task scheduling and personnel rostering problem, A column generation approach for the rail crew re-scheduling problem, The network design problem with relays, On the cutting stock problem under stochastic demand, Two-dimensional cutting stock problem with sequence dependent setup times, A note on branch-and-cut-and-price, An exact solution procedure for multi-item two-echelon spare parts inventory control problem with batch ordering in the central warehouse, Dynamic constraint and variable aggregation in column generation, Optimization methods for the train unit shunting problem, Iterative estimation maximization for stochastic linear programs with conditional value-at-risk constraints, A column-generation approach for joint mobilization and evacuation planning, A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts, Scheduling fighter squadron training missions using column generation, Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows, Modelling weak disposability in data envelopment analysis under relaxed convexity assumptions, A tutorial on column generation and branch-and-price for vehicle routing problems, A branch-and-price approach for harvest scheduling subject to maximum area restrictions, Divide-and-price: a decomposition algorithm for solving large railway crew scheduling problems, Analysis of programming properties and the row-column generation method for 1-norm support vector machines, Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design, A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem, Compatibility of short and long term objectives for dynamic patient admission scheduling, Using high performance computing for unrelated parallel machine scheduling with sequence-dependent setup times: development and computational evaluation of a parallel branch-and-price algorithm, A set partitioning reformulation of a school bus scheduling problem, Sustainable vegetable crop supply problem with perishable stocks, Branch-and-price approach for the multi-skill project scheduling problem, Integrated districting, fleet composition, and inventory planning for a multi-retailer distribution system, The sport teams grouping problem, A Branch and Price algorithm for the \(k\)-splittable maximum flow problem, Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies, A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks, Pruning in column generation for service vehicle dispatching, Aircraft and crew scheduling for fractional ownership programs, A new warmstarting strategy for the primal-dual column generation method, On minimum reload cost cycle cover, On dynamically generating relevant elementary flux modes in a metabolic network using optimization, Column generation in the integral simplex method, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems, Polylithic modeling and solution approaches using algebraic modeling systems, A Lagrangian heuristic for satellite range scheduling with resource constraints, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, Algorithms for the one-dimensional two-stage cutting stock problem, Stabilized branch-and-price algorithms for vector packing problems, Complementary column generation and bounding approaches for set partitioning formulations, Total flow time minimization in a flowshop sequence-dependent group scheduling problem, Speeding up column generation for robust wireless network planning, Branch-and-price-and-cut algorithms for solving the reliable \(h\)-paths problem, An inexact bundle variant suited to column generation, On minimum \(k\)-modal partitions of permutations, Chebyshev center based column generation, A shortest path-based approach to the multileaf collimator sequencing problem, The train driver recovery problem-a set partitioning based model and solution method, Robustness analysis of elementary flux modes generated by column generation, Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation, Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities, On decomposition and multiobjective-based column and disjunctive cut generation for MINLP, A branch-and-price-and-cut approach for sustainable crop rotation planning, Electric bus planning \& scheduling: a review of related problems and methodologies, A supervised learning-driven heuristic for solving the facility location and production planning problem, The vehicle allocation problem: alternative formulation and branch-and-price method, Branch-and-cut-and-price for multi-agent path finding, Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, Mathematical programming approaches for dual multicast routing problem with multilayer risk cost, A branch-and-price-and-check model for the vehicle routing problem with location congestion, Feeder routing for air-to-air refueling operations, A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering, The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming, A branch-and-price algorithm for capacitated hypergraph vertex separation, Cargo routing and scheduling problem in deep-sea transportation: case study from a fertilizer company, Real-time freight locomotive rescheduling and uncovered train detection during disruption, A prototype column generation strategy for the multiple container loading problem, Dynamic location of modular manufacturing facilities with relocation of individual modules, An integer optimality condition for column generation on zero-one linear programs, Pilotage planning in seaports, A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks, Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier, Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem, Air cargo scheduling: integrated models and solution procedures, Dantzig-Wolfe decomposition and branch-and-price solving in G12, Solving the electricity production planning problem by a column generation based heuristic, Theoretical treatment of target coverage in wireless sensor networks, Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows, A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand, An efficient approach to solve the large-scale semidefinite programming problems, Dynamic constraint aggregation for solving very large-scale airline crew pairing problems, A column generation-based heuristic for the split delivery vehicle routing problem with time windows, The dynamic-demand joint replenishment problem with approximated transportation costs, An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs, An exact column-generation approach for the lot-type design problem, Arc flow formulations based on dynamic programming: theoretical foundations and applications, A branch-and-price algorithm for the scheduling of customer visits in the context of multi-period service territory design, Dynamic job assignment: a column generation approach with an application to surgery allocation, An exact branch-and-price algorithm for scheduling rescue units during disaster response, Column generation for vehicle routing problems with multiple synchronization constraints, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Solution approaches for solving the log transportation problem, Branch-and-price-and-cut for a service network design and hub location problem, A multi-item approach to repairable stocking and expediting in a fluctuating demand environment, Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures, Lower bounds and algorithms for the minimum cardinality bin covering problem, A new cross decomposition method for stochastic mixed-integer linear programming, A column generation approach to high school timetabling modeled as a multicommodity flow problem, A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals, A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems, A specialized primal-dual interior point method for the plastic truss layout optimization, Decomposition-based inner- and outer-refinement algorithms for global optimization, The re-planning and scheduling of surgical cases in the operating room department after block release time with resource rescheduling, Stabilized dynamic constraint aggregation for solving set partitioning problems, Dynamic multi-appointment patient scheduling for radiation therapy, Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints, Using branch-and-price to determine optimal treatment plans for volumetric modulated arc therapy (VMAT), Integer programming models for the multidimensional assignment problem with star costs, Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans, An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007, Stabilized branch and price with dynamic parameter updating for discontinuous tour scheduling, On column generation approaches for approximate solutions of quadratic programs in intensity-modulated radiation therapy, A graph partitioning strategy for solving large-scale crew scheduling problems, Decomposition and dynamic cut generation in integer linear programming, Sustainable vegetable crop supply problem, A generic view of Dantzig--Wolfe decomposition in mixed integer programming, Avoiding redundant columns by adding classical Benders cuts to column generation subproblems, Exact solution of the soft-clustered vehicle-routing problem, Branch and price for the vehicle routing problem with discrete Split deliveries and time windows, The stochastic transportation problem with single sourcing, A multi-commodity two-echelon capacitated vehicle routing problem with time windows: model formulations and solution approach, Decomposition theorems for linear programs, Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization, A branch and price algorithm to solve the quickest multicommodity \(k\)-splittable flow problem, Railway crew scheduling: models, methods and applications, Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design, Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition, Improving set partitioning problem solutions by zooming around an improving direction, Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach, A resource constrained scheduling problem with multiple independent producers and a single linking constraint: a coal supply chain example, New approaches to nurse rostering benchmark instances, The time buffer approximated buffer allocation problem: a row-column generation approach, Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange, Column generation based heuristic for learning classification trees, A lexicographic pricer for the fractional bin packing problem, A branch-cut-and-price algorithm for optimal decoding in digital communication systems, Branch-and-price for a class of nonconvex mixed-integer nonlinear programs, A branch-and-price procedure for clustering data that are graph connected, New exact techniques applied to a class of network flow formulations, Fast quantum subroutines for the simplex method, Scheduling with uncertain processing times in mixed-criticality systems, Scheduling heterogeneous delivery tasks on a mixed logistics platform, A two-stage solution approach for personalized multi-department multi-day shift scheduling, A branch-and-price algorithm for the two-dimensional vector packing problem, Robust drone selective routing in humanitarian transportation network assessment, An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems, Robust vehicle routing under uncertainty via branch-price-and-cut, Row-reduced column generation for degenerate master problems