A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP

  • Suresh Bolusani
  • Gioni Mexi
  • Mathieu Besançon
  • Mark Turner
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , , Short URL: https://optimization-online.org/?p=27237

    This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and evaluation of MRENS in a full-fledged MILP solver, specifically coupled with the recently-introduced Lagromory separator for generating multiple reference solutions. Computational experiments on the MIPLIB 2017 benchmark set show that MRENS, with multiple reference solutions, improves the solver's ability to find higher-quality feasible solutions compared to single-reference approaches. This study highlights the potential of multi-reference heuristics in enhancing primal heuristics in MILP solvers.

    Article

    Download

    View A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP