large-neighbourhood search

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

  • Stephen J. Maher
  • Elina Rönnberg
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more

    Large neighbourhood Benders’ search

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    A general enhancement of the Benders’ decomposition algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, their use is typically limited to finding solutions to the Benders’ decomposition master problem, which may be … Read more