EURO 2025 Leeds
Abstract Submission

1445. From Infeasibility to Feasibility - Improvement Heuristics to Find First Feasibles for MIPs

Invited abstract in session WD-43: Algorithms and Applications, stream Software for Optimization.

Wednesday, 14:30-16:00
Room: Newlyn GR.07

Authors (first author is the speaker)

1. Tobias Achterberg
Gurobi

Abstract

Relaxation Induced Neighborhood Search (RINS) and other large neighborhood search (LNS) improvement heuristics for mixed integer programs (MIPs) explore some neighborhood around a given feasible solution to find other solutions with better objective value. This often leads to a chain of improving solutions with a high quality solution at its end, even if the starting solution is rather poor.

RINS and its variants are the most important heuristic ingredients in Gurobi to find good solutions quickly. But they have one issue: they can only be employed after an initial feasible solution has been found.

This initial feasible solution is usually found by other heuristics, so-called "start heuristics", like rounding of LP solutions, fix-and-dive, or the Feasibility Pump.

In this talk, we discuss a different approach, which works surprisingly well: similar in spirit to the Feasibility Pump, consider infeasible integral vectors as input to the improvement heuristics and search in the neighborhood for vectors with small violation to act as new starting point for the next LNS improvement heuristic invocation.

Keywords

Status: accepted

Back to the list of papers