Accession Number:

ADA421653

Title:

The Neighborhood Covering Heuristic (NCH) Approach for the General Mixed Integer Programming Problem

Descriptive Note:

Final rept. 1 Jul 2003-2 Feb 2004

Corporate Author:

AKRON UNIV OH DEPT OF THEORETICAL AND APPLIED MATHEMATICS

Report Date:

2004-02-02

Pagination or Media Count:

35.0

Abstract:

We accomplished our objectives, successfully implementing the Neighborhood Covering Heuristic NCH for solving the mixed integer programming problems. NCH is a unique, proprietary approach with several ground-breaking advantages. We completed a series of comparisons between NCH and the standard Branch and Bound BAB approach. Using the tunable parameters available within NCH, we created ten variants. We randomly generated sets of MIP problems, where the numbers of integer and binary variables, and constraints were varied in a systematic way. Then we applied both BAB and our ten variants of NCH to each of the generated problems. We obtained several significant results. First, when other parameters are fixed, the number of integer and binary variables in a random MIP problem does not have an exponential impact on the time required to find a feasible solution using NCH. Second, the performance data show that NCH produces feasible solutions significantly faster than BAB. Moreover the variance in time to produce a feasible solution is smaller in NCH. This reduction in variance and the resulting greater predictability of time to first solution will be extremely attractive to logistic companies, consultants, and useful directly in the Navy COMPASS program specifically and for Navy optimization needs in general.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE