Return to search

ZI Round, a MIP Rounding Heuristic

We introduce a new pure integer rounding heuristic, ZI Round, and compare this heuristic to recent extremely fast pure integer rounding heuristic Simple Rounding. Simple Rounding was introduced in the non-commercial code SCIP. ZI Round attempts to round each fractional variable while using row slacks to maintain primal feasibility. We use the MIPLIB 2003 library for the test set. The average time in our run per instance for both Simple Rounding and ZI Round was 0.8 milliseconds, but ZI Round found more feasible solutions with a the same or better objective value. Also the average time to solve the lp relaxation per instance was 2.2 seconds, so these two rounding heuristics are several magnitudes faster than other heuristics which must use the lp solver, including diving heuristics.We also show that ZI Round performs well on a set covering class and a railway crew scheduling class.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-18196
Date01 October 2010
CreatorsWallace, Chris
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0018 seconds