consortiums

PROJECT 5

DISTRIBUTION AND ASSIGNMENT

Fred Glover, Gary Kochenberger,
Bahram Alidaee, CesarRego
School of Business Administration
University of Mississippi

Proposed Grant $161,226

Abstract:
Many difficult combinatorial optimization problems cannot be solved quickly. Increasing our success with these problems can spell the difference between success and failure in a business venture or a military campaign. This is especially relevant for Navy personnel problems such as manpower planning. As noted in Sailor 21

“Before the distribution and assignment methodologies can become a part of the Navy manpower and personnel organization, a variety of issues must be addressed and resolved. One set of hurdles lies in the capacity and performance of mathematical programming algorithms and computers.” And in explanation of these hurdles: “The Navy assigns at least 11000 people per month. [Although] the current optimization models can handle separate communities and ratings and other large groupings, none of the models can handle a problem that considers assignments more than 1500 people and 2500 jobs in a single run.”

This critical limitation in models and solution capabilities is also relevant to Navy applications that depend on handling vast amounts of data and knowledge, such as the critical decision support applications for the distribution arena. As also noted in Sailor 21 “Computing, sorting, organizing, validation and cleaning the data for the various models and systems will be a challenge. Making the data available in real time, at the appropriate level of aggregation and ensuring the consistency across models is a fundamental requirement.”
x
A very recent innovation in meta-heuristics is the emergence of the Ghost Image Processing (GIP) approach (Glover, 1994; Woodruff, 1995, 1999). The GIP framework provides a way to restructure processes related to self-organizing neural networks (Kohonen, 1988), and has applications to strategies of state space smoothing (Coy, Golden, and Wasil, 1998). Significantly, GIP is inherently very much different from Scatter Search, whose successful applications have previously been noted, yet incorporates principles that are building blocks of SS. As a result GIP and SS have powerful complementarities and yet are highly compatible, allowing them to be joined to exploit different aspects of hard optimization problems. A key feature contributed by GIP is the demonstration by Woodruff (1995) that GIP is particularly well suited as a strategy for tackling very-large-scale problems.

Our objective in this research is therefore to integrate Scatter Search and Ghost Image Processing to capitalize on their complementary strengths, and their independent success records. Members of the research team have recently combined Scatter Search with Tabu Search strategies that are shared with GIP to dramatically increase the size and difficulty of problems that can be handled from the domain known as Binary Quadratic Programming (Glover, Amini, Kochenberger and Alidaee, 2000), which has many practical applications in combinatorial optimization, particularly in classification and data mining (Kochenberger, Alidaee and Amini, 1998). The adaptability of the GIP framework, its relevance for large-scale optimization, and its ability to be integrated with SS, therefore commends it as a foundation for a new class of methods for solving whose size and complexity have made them inaccessible to practical solution by methods currently available.