Branch-and-Price: Column Generation for Solving Huge Integer Programs
From MaRDI portal
Publication:2770133
DOI10.1287/OPRE.46.3.316zbMath0979.90092OpenAlexW2167580124WikidataQ56814662 ScholiaQ56814662MaRDI QIDQ2770133
Nemhauser, George I., Savelsbergh, Martin W. P., Pamela H. Vance, Cynthia Barnhart, Ellis L. Johnson
Publication date: 7 February 2002
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/764cbb2d06d95a2f983b3683a0b9103aaeae7968
column generationinteger programsbranch-and-bound algorithmsLagrangian dualityLP relaxationbranch-and-bound treespecial branching rules
Integer programming (90C10) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)
Related Items (only showing first 100 items - show all)
Stabilizing branch‐and‐price for constrained tree problems ⋮ Matheuristics: survey and synthesis ⋮ Column elimination for capacitated vehicle routing problems ⋮ The rendezvous vehicle routing problem ⋮ “Make no little plans”: Impactful research to solve the next generation of transportation problems ⋮ A column generation approach for the team formation problem ⋮ Branch‐and‐price for energy optimization in multi‐hop wireless sensor networks ⋮ Application of decomposition techniques in a wildfire suppression optimization model ⋮ Single machine parallel-batch scheduling under time-of-use electricity prices: new formulations and optimisation approaches ⋮ Columnwise neighborhood search: A novel set partitioning matheuristic and its application to the <scp>VeRoLog</scp> Solver Challenge 2019 ⋮ A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ 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 ⋮ Efficient learning of large sets of locally optimal classification rules ⋮ A Maritime Pulp Distribution Problem ⋮ Solving large-scale dynamic vehicle routing problems with stochastic requests ⋮ Improving energy aware nanosatellite task scheduling by a branch-cut-and-price algorithm ⋮ Stochastic inventory routing with time-based shipment consolidation ⋮ Branch-and-price algorithms for large-scale mission-oriented maintenance planning problems ⋮ 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 ⋮ Adaptive solution prediction for combinatorial optimization ⋮ Day-ahead aircraft routing with data-driven primary delay predictions ⋮ A branch‐and‐price algorithm for identical parallel machine scheduling with multiple milestones ⋮ A Column Generation Model for Truck Routing in the Chilean Forest Industry ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ Assigning Team Tasks and Multiple Activities to Fixed Work Shifts ⋮ Electric aircraft charging network design for regional routes: a novel mathematical formulation and kernel search heuristic ⋮ Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ Learning to repeatedly solve routing problems ⋮ Combining metaheuristics with mathematical programming, constraint programming and machine learning ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Optimization in liner shipping ⋮ Exact Approaches for Network Design Problems with Relays ⋮ A Joint Vehicle Routing and Speed Optimization Problem ⋮ From High-Level Model to Branch-and-Price Solution in G12 ⋮ A column generation approach for the split delivery vehicle routing problem ⋮ A Complementary Column Generation Approach for the Graph Equipartition Problem ⋮ Optimization in liner shipping ⋮ Combining metaheuristics with mathematical programming, constraint programming and machine learning ⋮ Constraint programming-based column generation ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Searching for optimal integer solutions to set partitioning problems using column generation ⋮ Lower bounds and algorithms for the 2-dimensional vector packing problem ⋮ Constraint programming-based column generation ⋮ A branch-and-price algorithm for the Steiner tree packing problem. ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Exact algorithms for integrated facility location and production planning problems ⋮ Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation ⋮ \textsc{Laps}\ \textsc{Care} -- an operational system for staff planning of home care ⋮ A new novel local search integer-programming-based heuristic for PCB assembly on collect-and-place machines ⋮ Solving the minimum convex partition of point sets with integer programming ⋮ A discrete meta-control procedure for approximating solutions to binary programs ⋮ An exact algorithm for an integrated project staffing problem with a homogeneous workforce ⋮ A mixed integer programming approach to multi-skilled workforce scheduling ⋮ Workforce scheduling and routing problems: literature survey and computational study ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Globally optimal clusterwise regression by column generation enhanced with heuristics, sequencing and ending subset optimization ⋮ BoxStep methods for crew pairing problems ⋮ A comparison of five heuristics for the multiple depot vehicle scheduling problem ⋮ Branch-and-price and constraint programming for solving a real-life technician dispatching problem ⋮ All-integer column generation for set partitioning: basic principles and extensions ⋮ Branch-and-price algorithm for the resilient multi-level hop-constrained network design ⋮ An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems ⋮ The timetable constrained distance minimization problem ⋮ Combining column generation and constraint programming to solve the tail assignment problem ⋮ A two-level approach to large mixed-integer programs with application to cogeneration in energy-efficient buildings ⋮ Alternative approaches to the crude oil tanker routing and scheduling problem with split pickup and split delivery ⋮ An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration ⋮ 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 ⋮ Scheduling pumpoff operations in onshore oilfields under electric-power constraints ⋮ The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach ⋮ Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows ⋮ A branch-and-price algorithm for stable workforce assignments with hierarchical skills ⋮ Decomposition approaches for recoverable robust optimization problems ⋮ Increasing the revenue of self-storage warehouses by optimizing order scheduling ⋮ Optimal allocation of emergency medical resources in a mass casualty incident: patient prioritization by column generation ⋮ A column generation approach for solving the examination-timetabling problem ⋮ Scheduling cranes at an indented berth ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ Maximizing expected number of transplants in kidney exchange programs ⋮ A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times ⋮ Computing minimal forecast horizons: an integer programming approach ⋮ A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites ⋮ Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation ⋮ Hybrid column generation for large-size covering integer programs: application to transportation planning ⋮ A multilevel integrative approach to hospital case mix and capacity planning ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ Tactical fixed job scheduling with spread-time constraints ⋮ Optimal interval scheduling with a resource constraint ⋮ Optimal shift partitioning of pharmacies ⋮ The production routing problem: a review of formulations and solution algorithms ⋮ Mathematical models and algorithms for a high school timetabling problem ⋮ The impact of reserve duties on the robustness of a personnel shift roster: an empirical investigation ⋮ A \texttt{cost-regular} based hybrid column generation approach ⋮ A constraint programming based column generation approach to nurse rostering problems ⋮ A branch-price-and-cut method for a ship routing and scheduling problem with split loads
Uses Software
This page was built for publication: Branch-and-Price: Column Generation for Solving Huge Integer Programs
