Academic journal article
By Cope, Robert F.,, III; Hotard, Daniel G.; Cope, Rachelle F.
Academy of Information and Management Sciences Journal , Vol. 4, No. 1-2
In this paper, we explore the pedagogical concerns of integer resource allocation problems. A natural, ongoing question from students following lectures on integer resource allocation problems asks, "How can I obtain other optimal or non-optimal solutions for comparison purposes?" It has been our experience that students enjoy the decision analysis phase regarding resource tradeoffs after obtaining a solution to these problems by traditional means. Hence, we investigate an alternative algorithm to solve an integer resource allocation problem in terms of its isomorphically equivalent Linear Diophantine Equation (LDE).
An LDE is a linear equation with solutions in the set of integers (Barnett, 1969). Unlike most other Diophantine equations, LDEs can be solved algorithmically (Rowe, 1986; Stewart, 1992). We present an alternate, computer applicable approach to formulate the general solution of an LDE. The algorithm developed in this paper to find the general solution of an LDE involves three steps. Step one involves finding an initial solution to the LDE using Blankinship's Version of the Euclidean Algorithm as its basis. In the second step, the general solution to a Homogeneous LDE (HLDE) is determined. Finally, the general solution of the LDE is found by advancing the initial solution of the LDE found in step one with the general solution of the HLDE obtained in step two through addition. Since the use of general solutions to LDEs is an alternate approach for finding multiple solutions to integer allocation problems, the methodology is compared to the more traditional approach of finding an optimal solution using branch and bound enumeration. A comparison of both methodologies as tools for quantitative decision analysis are discussed.
AN EXAMPLE INTEGER RESOURCE ALLOCATION PROBLEM
To illustrate the students' question, we explore an integer resource allocation problem where an integer quantity must be allocated in integer amounts to two or more entities (Ibaraki and Katoh, 1988). Thus, the following integer allocation problem is posed.
Problem: A real estate developer has a parcel of land with a frontage of 1,000 ft. The property is to be subdivided into lots having frontages of 60 ft. and 80 ft., respectively. In how many ways can this task be done?
A typical model used to represent the problem is the linear equation
60[X.sub.1] + 80[X.sub.2] = 1,000, (1)
where [X.sub.1] and [X.sub.2] respectively represent the number of lots with 60 ft. and 80 ft. frontages. The solution set for the problem is restricted to a subset of integers.
BRANCH AND BOUND LITERATURE
Literature concerning branch and bound enumeration is wide in scope and crosses into many Operations Research topics. According to Salkin (1975), the classic enumeration algorithm and many of its variations were developed by Land and Doig (1960). Their specialized methodology was designed for the traveling salesman problem by Little, Murty, Sweeney, and Karel (1963). They termed the specialized procedure as branch and bound. Later, Thompson (1964) presented an algorithm for the integer program called "The Stopped Simplex Method" which was a consequence of Land and Doig's work. A year later, Dakin (1965) proposed a simple, yet interesting, variation which employed the use of integer solution space inequalities at each node of Land and Doig's branch and bound algorithm. Shortly there after, Beale and Small (1965) extended the Dakin method to include the linear programming post optimization procedures suggested by Driebeek (1966). Finally, Tomlin (1970; 1971), described a refined version of the Beale and Small algorithm.
THE BRANCH AND BOUND APPROACH
In an effort to show the value of the LDE approach, we compare it to an equivalent integer resource allocation problem formulated as an integer programming (IP) problem. There are many software packages on the market to solve IP problems, and many of these packages generally employ a branch and bound algorithm. …