Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions

Primary tabs

Given a feasible solution to a Mixed Integer Programming (MIP) model, a natural question is whether that solution can be improved using local search techniques. Local search has been applied very successfully in a variety of other combinatorial optimization domains. Unfortunately, local search relies extensively on the notion of
a solution neighborhood, and this neighborhood is almost always tailored to the structure of the particular problem being solved. A MIP model typically conveys little information about the underlying problem structure. This talk will consider two new approaches to exploring
interesting, domain-independent neighborhoods in MIP. The more
effective of the two, which we call Relaxation Induced Neighborhood Search (RINS), constructs a promising neighborhood using information
contained in the continuous relaxation of the MIP model. Neighborhood exploration is then formulated as a MIP model itself and solved recursively. The second, which we call guided dives, is a simple
modification of the MIP tree traversal order. Loosely speaking, it guides the search towards nodes that are close neighbors of the best known feasible solution. Extensive computational experiments on very
difficult MIP models show that both approaches outperform default CPLEX MIP and a previously described approach for exploring MIP neighborhoods (local branching) with respect to several different metrics. The metrics
we consider are quality of the best integer solution produced within a time limit, ability to improve a given integer solution (of both good and poor quality), and time required to diversify the search in order to find a new solution.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience

No target audience selected.