Incorporating decision analysis into solutions to integer resource allocation problems.

Cope, Robert F., III ; Hotard, Daniel G. ; Cope, Rachelle F. 等

INTRODUCTION

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.

The algorithmic implementation of the branch and bound procedure utilizes the simplex or dual simplex method to solve the linear program, ignoring any constraints of integer only values. In those cases where an optimal solution is found which is feasible for the integer program, then that solution is the optimal integer solution. However, if any of the variables constrained to be integers do not satisfy that constraint in the optimal solution found, then the solution set must be partitioned to continue to search for possible optima of the integer program. This is done by taking a decision variable having a non-integer value such as k < [X.sub.j] < (k+1) and branching from that point into one subset for which [X.sub.j] [less than or equal to] k and another for which [X.sub.j] [greater than or equal to] (k+1). The augmented linear program is solved for each case with the results leading to further partitioning of the subset or classifying the subset as fathomed (Hillier and Lieberman, 1974). A solution subset is said to be fathomed if it:

1 contains no feasible solutions;

2 the bound for its optimal solution is not as good as a current optimal solution;

3 it is a feasible solution for the integer program and has an optimal value which is better than the best current value.

When all subsets have been fathomed, the optimal solution (if one exists) is whatever the best current optimal solution happens to be. The process in effect eliminates subsets of possible solutions until it identifies the solutions which can be considered optimal. Many have considered this form of solution methodology to be rigid.

SOLVING THE EXAMPLE USING BRANCH AND BOUND ENUMERATION

Consider our original real estate developer's dilemma in integer programming form:

Maximize/Minimize: 60[X.sub.1] + 80[X.sub.2] Subject to: 60[X.sub.1] + 80[X.sub.2] = 1000, where [X.sub.1] and [X.sub.2] are nonnegative integers.

The branch and bound approach would first ignore the constraints that [X.sub.1] and [X.sub.2] be integers and an optimum solution to the linear program would be found at [X.sub.1] = 0 and [X.sub.2] = 12.5. Because this is not a feasible solution for the integer program, the solution set would be partitioned into two separate subsets identified by [X.sub.2] [less than or equal to] 12 and [X.sub.2] [greater than or equal to] 13, respectively. The latter of these contains no feasible solutions and is therefore fathomed and need be examined no further. The former, however, provides the linear program:

Maximize/Minimize: 60[X.sub.1] + 80[X.sub.2] Subject to: 60[X.sub.1] + 80[X.sub.2] = 1000; [X.sub.2] [less than or equal to] 12

and an optimum solution exists at [X.sub.1] = 2/3 and [X.sub.2] = 12. As this is not a feasible solution for the original integer program, the branching would continue with partitions identified by [X.sub.1] [less than or equal to] 0 and [X.sub.1] [greater than or equal to] 1, respectively. The branch for which [X.sub.1] [less than or equal to] 0 becomes fathomed as it contains no feasible solutions, while the branch for which [X.sub.1] [greater than or equal to] 1 produces an optimum solution at [X.sub.1] = 1 and [X.sub.2] = 11.75. The latter subset must again be partitioned over [X.sub.2] with [X.sub.2] [less than or equal to] 11 and [X.sub.2] [greater than or equal to] 12 identifying the two new subsets, respectively.

The linear program:

Maximize/Minimize: 60[X.sub.1] + 80[X.sub.2] Subject to: 60[X.sub.1] + 80[X.sub.2] = 1000; [X.sub.2] [greater than or equal to] 12; [X.sub.1] [greater than or equal to] 1

has no feasible solutions and that branch is therefore fathomed. However, the linear program:

Maximize/Minimize: 60[X.sub.1] + 80[X.sub.2] Subject to: 60[X.sub.1] + 80[X.sub.2] = 1000; [X.sub.2] [less than or equal to] 11; [X.sub.1] [greater than or equal to] 1

has an optimal solution at [X.sub.1] = 2 and [X.sub.2] = 11. Because that optimal solution of the linear program is also a feasible solution to the original integer program, it represents an optimal solution to the original integer programming problem.

The branch and bound enumeration approach therefore produces an optimum solution to our problem at [X.sub.1] = 2 and [X.sub.2] = 11, indicating the developer should create two of the 60 ft. wide lots and eleven of the 80 ft. wide ones.

THE LINEAR DIOPHANTINE EQUATION APPROACH

The framework necessary to employ the LDE methodology is presented in the following four sections. In the first section, a brief overview of two theorems found in elementary number theory is introduced. In the second section, Blankinship's version of the Euclidean Algorithm is demonstrated as an alternative to finding a greatest common divisor (gcd) and solution to a gcd equation of n integers. The next step of the process requires obtaining a solution to a HLDE. This step is discussed in the third section. If no unit coefficients exist in a HLDE, use of the Unit Coefficient Reduction Algorithm is demonstrated. Finally, use of the Additive Theorem for finding a general solution to an LDE is presented in the fourth section.

AN OVERVIEW OF THE LDE APPROACH

Two theorems, found in elementary number theory books, are given that involve the existence and determination of solutions to LDEs (Barnett, 1969; Stewart, 1952).

Theorem 1: Let [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = C (for n [greater than or equal to] 2) represent an LDE and D represent the gcd of [A.sub.1], [A.sub.2], ..., [A.sub.n]. If D divides C, then the LDE has a solution in the set of integers.

For example, if we are given the LDE:

3[X.sub.1] + 6[X.sub.2] = 12, (2)

then it has a solution in the set of integers because the gcd of 3 and 6 is 3 which divides 12.

Theorem 2: Assume the LDE [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = C has a solution and D is the gcd of [A.sub.1], [A.sub.2], ..., [A.sub.n]. If [X.sub.1]*, [X.sub.2]*, ..., [X.sub.n]* represents a solution to the gcd equation [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = D, then [X.sub.1]** = k*[X.sub.1]*, [X.sub.2]** = k*[X.sub.2]*, ..., [X.sub.n]** = k*[X.sub.n]* represents a solution to the LDE, where k = C/D.

Theorem 2 allows one to find a solution to an LDE given a solution to its gcd equation. For example, consider the LDE:

172[X.sub.1] + 20[X.sub.2] = 1000. (3)

The gcd of 172 and 20 is 4 and a specific solution to the gcd equation 172[X.sub.1] + 20[X.sub.2] = 4 is [X.sub.1]* = 2 and [X.sub.2]* = -17. Since k = C/D = 1000/4 = 250, then [X.sub.1]** = k*[X.sub.1]* = 250*2 = 500 and [X.sub.2]** = k*[X.sub.2]* = 250*(-17) = -4250 provide a solution to the LDE.

BLANKINSHIP'S VERSION OF THE EUCLIDEAN ALGORITHM

In the previous section, Theorem 2 implied that to find a solution to an LDE one could first solve its related gcd equation [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = D, where D is the gcd of [A.sub.1], [A.sub.2], ..., [A.sub.n]. In general, computer application is necessary for obtaining a solution to the related gcd equation of an LDE.

The typical method found in quantitative texts to solve a gcd equation with n = 2 variables involves two procedures (Barnett, 1969; Kurosaka, 1986; Stewart, 1952). First, the gcd of [A.sub.1] and [A.sub.2] must be found. This procedure employs the Euclidean Algorithm which involves repeated use of division until a zero remainder occurs. The second procedure involves finding a solution to the gcd equation. Completion of this task involves reversing the computations performed in computing the gcd of [A.sub.1] and [A.sub.2]. This method of solution can be tedious to employ. Furthermore, the algorithm is limited to solving gcd equations with only two variables. Repeated application of the process is required when there are more than two variables.

W.A. Blankinship's article unveiled an alternate method for finding the gcd for more than two integer variables and a solution to the corresponding gcd equation of n integers (Blankinship, 1963). Blankinship's Version of the Euclidean Algorithm (BVEA) is straight forward to execute and easily implemented using a computer.

Suppose we are interested in finding the gcd of [A.sub.1], [A.sub.2], ..., [A.sub.n] and solving the gcd equation [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = D. According to Blankinship's algorithm we first formulate an n by (n+1) matrix M defined as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The basis of this algorithm consists of performing elementary row operations on the matrix according to the following procedure.

Step #1: Select the row with the smallest non-zero first element. Call this row the operator row and its first element the operator.

Step #2: Find all rows with non-zero first elements. Call these rows operand rows and their first elements operands.

a. If one or more operand rows are found, then go to Step #3.

b. If no operand rows are found the process terminates with the solution set for the problem found in the operator row. The gcd D is the operator while the solution to the gcd equation defined by [X.sub.1]*, [X.sub.2]*, ..., [X.sub.n]* is found in the corresponding columns 2 to (n+1) of the operator row.

Step #3: For each operand row determine the integer quotient Q equal to the row's operand divided by the operator.

Step #4: For each operand row replace each element of the row with the corresponding difference between itself and Q times the corresponding element of the operator row.

Step #5: Return to Step #1.

To illustrate the algorithm, assume [A.sub.1] = 10, [A.sub.2] = 12 and [A.sub.3] = 8. Thus matrix M becomes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From matrix M we observe that row 3 is the operator row and its first element 8 is the operator. The operands are the first elements of rows 1 and 2. Table 1 that follows demonstrates the execution of the algorithm. In the table, Matrix Mi denotes the row equivalent matrix to matrix M after the ith iteration of Step #4 of the algorithm. From Table 1 we find the gcd of 10, 12, and 8 to be 2 and a solution to the gcd equation 10[X.sub.1] + 12[X.sub.2] + 8[X.sub.3] = 2 is [X.sub.1]* = 1, [X.sub.2]* = 0, and [X.sub.3]* = -1.

SOLVING HOMOGENEOUS LINEAR DIOPHANTINE EQUATIONS

A HLDE is one with its constant term C on the right hand side of the equation equal to zero. For example, 3[X.sub.1] + 5[X.sub.2] + 6[X.sub.3] = 0 is a HLDE. In this section, our goal is to find a method for determining the general solution of a HLDE.

It is important to note, if one of the coefficients of the HLDE is [+ or -]1, we can find a general solution by solving for that variable. For example 3[X.sub.1] + 6[X.sub.2] + 2[X.sub.3] + [X.sub.4] = 0 has a general solution [X.sub.4] = -3[X.sub.1] - 6[X.sub.2] - 2[X.sub.3] for arbitrary integer values of [X.sub.1], [X.sub.2], and [X.sub.3].

The question at this point is how do we find the general solution to a HLDE if it has no unit coefficients. The Unit Coefficient Reduction Algorithm, which is based on a similar algorithm generally found in textbooks involving the theory of equations, is used to resolve the question (MacDuffee, 1954).

Assume the HLDE [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... [A.sub.n]*[X.sub.n] = 0 with [A.sub.i] [not equal to] 0 for i = 1 to n and where the gcd of [A.sub.1], [A.sub.2], ..., [A.sub.n] is equal to 1. Then the process that follows defines the Unit Coefficient Reduction Algorithm:

Step #1: Choose Min = [A.sub.m] to be the smallest [A.sub.i] for
 i = 1 to n. Then let SMin = As represent the smallest
 of the remaining [A.sub.i]'s that is relative prime to
 Min (i.e. has gcd of 1).
Step #2: Apply the division algorithm and find the quotient q and
 the remainder r using Min as the divisor and SMin as the
 dividend. Namely, find integers q and r such that
 SMin = q * Min + r, (4)
 where 0 [less than or equal to] r < Min.
Step #3: Substitute [X.sub.m] = [X.sub.m]' - q * [X.sub.s] in the
 HLDE. It is easily seen that this substitution yields a
 coefficient of r for [X.sub.s]. Furthermore, repeated
 applications of Step #3 leads to the desired result of
 r = 1 or a unit for the HLDE.
Step #4: a If r is not 1, then return to Step #1.
 b If r = 1, then a general solution to the HLDE can be
 found by doing the following.
 1 First, solve the HLDE for the variable which has a
 unit coefficient.
 2 Next, utilize the substitutions performed in Step #3
 and the equation obtained in 1 above to determine
 the general solution of the HLDE.

To illustrate the algorithm let us consider the HLDE:

3[X.sub.1] + 5[X.sub.2] + 17[X.sub.3] + 156[X.sub.4] = 0. (5)

Because the gcd of 3, 5, 17, and 156 is 1, then the algorithm can be applied. Details of the Unit Coefficient Reduction Algorithm for the example are given in Table 2.

Since r = 1 we have a HLDE with a unit coefficient which we can solve as follows:

[X.sub.1]' = -2[X.sub.2]' - 17[X.sub.3] - 156[X.sub.4]. (6)

By combining [X.sub.2] = [X.sub.2]' - [X.sub.1]' from Iteration #2, Step #3 with equation 6 yields:

[X.sub.2] = [X.sub.2]' - [X.sub.1]' = [X.sub.2]' - (-2[X.sub.2]'-17[X.sub.3] - 156[X.sub.4]), which reduces to [X.sub.2] = 3[X.sub.2]' + 17[X.sub.3] + 156[X.sub.4]. (7)

Also by combining [X.sub.1] = [X.sub.1]' - [X.sub.2] from Iteration #1, Step #3 and equations 6 and 7 yields:

[X.sub.1] = [X.sub.1]' - [X.sub.2] = (-2[X.sub.2]' - 17[X.sub.3] - 156[X.sub.4]) - (3[X.sub.2]' + 17[X.sub.3] + 156[X.sub.4]), which also reduces to [X.sub.1] = -5[X.sub.2]' - 34[X.sub.3] - 312[X.sub.4]. (8)

Thus, for arbitrary integers [X.sub.2]', [X.sub.3], and [X.sub.4] and equations 7 and 8, one can find a solution to the HLDE 3[X.sub.1] + 5[X.sub.2] + 17[X.sub.3] + 156[X.sub.4] = 0.

USING THE ADDITIVE THEOREM

This section develops a method for finding a general solution to an LDE (Blankinship, 1963). The process formulated is dependent on Theorem 3 below, which is based on a similar concept used to solve ordinary linear differential equations (Kaplan, 1958). The theorem and its proof follows.

Theorem 3 (Additive Theorem): If [I.sub.1], [I.sub.2], ..., [I.sub.n] represents an initial solution to the LDE, [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = C, and [G.sub.1], [G.sub.2], ..., [G.sub.n] represents a general solution to its HLDE, [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = 0, then [X.sub.i]*= [G.sub.i] + [I.sub.i], for i = 1 to n, represents a general solution to the LDE [A.sub.1]*[X.sub.1] + [A.sub.2]*[X.sub.2] + ... + [A.sub.n]*[X.sub.n] = C.

Proof: To display that [X.sub.i]*= [G.sub.i] + [I.sub.i] for i = 1, ..., n represents a general solution, it is necessary to show that [X.sub.i]* satisfies the given LDE. To do so we obtain:

1 [SIGMA][A.sub.i]*[X.sub.i]* = [SIGMA][A.sub.i]*([G.sub.i] + [I.sub.i]) by substitution,

2 [SIGMA][A.sub.i]*[X.sub.i]* = [SIGMA]([A.sub.i]*[G.sub.i] + [A.sub.i]*[I.sub.i]) by the distributive law of multiplication, and

3 [SIGMA][A.sub.i]*[X.sub.i]* = [SIGMA]([A.sub.i]*[G.sub.i]) + [SIGMA]([A.sub.i]*[I.sub.i]) by the additive law for summations.

Since [G.sub.1], [G.sub.2], ..., [G.sub.n] is a general solution to the HLDE, then [SIGMA]([A.sub.i]*[G.sub.i]) = 0. In addition, since [I.sub.1], [I.sub.2], ..., [I.sub.n] is an initial solution to the LDE, then [SIGMA]([A.sub.i]*[I.sub.i]) = C. Thus from 3 above and the last two observations it follows that:

4 [SIGMA][A.sub.i]*[X.sub.i]* = [SIGMA]([A.sub.i]*[G.sub.i]) + [SIGMA]([A.sub.i]*[I.sub.i]) or 0 + C = C.

As an illustration let us consider the LDE:

3[X.sub.1] + 5[X.sub.2] + 17[X.sub.3] + 156[X.sub.4] = 2. (9)

An initial solution to the LDE is [I.sub.1] = 3, [I.sub.2] = 2, [I.sub.3] = -1, [I.sub.4] = 0. Furthermore, the general solution to its HLDE developed previously is [G.sub.1] = -5[X.sub.2]' - 34[X.sub.3] - 312[X.sub.4]; and [G.sub.2] = 3[X.sub.2]' + 17[X.sub.3] + 156[X.sub.4], where [X.sub.2]', [X.sub.3], and [X.sub.4] are integers. Since [X.sub.3] and [X.sub.4] are arbitrary, let [X.sub.3] = t and [X.sub.4] = s. Now by Theorem 3, and equations 7 and 8, a general solution to the LDE is represented as follows:

[X.sub.1] = (-5[X.sub.2]' - 34[X.sub.3] - 312[X.sub.4]) + 3, (10)

[X.sub.2] = (3[X.sub.2]' + 17[X.sub.3] + 156[X.sub.4]) + 2, (11)

[X.sub.3] = t - 1, (12)

[X.sub.4] = s + 0, (13)

where [X.sub.2]', t, and s are arbitrary integers.

SOLVING THE EXAMPLE PROBLEM USING THE LDE APPROACH

The algorithm advanced by the authors to find the general solution of the LDE requires:

1 an initial solution to the LDE be found,

2 a general solution to the model's corresponding HLDE be obtained, and

3 that the Additive Theorem be employed.

To find the initial solution of the LDE for the real estate developer's problem, we first use Blankinship's Version of Euclidean Algorithm (BVEA) to find a solution to the LDE's corresponding gcd equation. Employing BVEA requires we define the matrix M below.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Table 3 summarizes the actions of the BVEA.

From Table 3 we find the gcd of [A.sub.1] = 60 and [A.sub.2] = 80 is 20 and a solution to the gcd equation 60[X.sub.1] + 80[X.sub.2] = 20 is [X.sub.1]* = -1 and [X.sub.2]* = 1.

Now applying Theorem 2 we find an initial solution to our integer allocation problem modeled by 60[X.sub.1] + 80[X.sub.2] = 1,000. The value of k is found as k = C/D = 1,000/20 = 50. The initial solution to the LDE is [X.sub.1]** = k*[X.sub.1]* = 50*(-1) = -50 and [X.sub.2]** = k*[X.sub.2]* = 50*1 = 50.

Next, we determine a general solution to the HLDE:

60[X.sub.1] + 80[X.sub.2] = 0, (14)

by employing the Unit Coefficient Reduction Algorithm. The algorithm requires the coefficients of the HLDE to be relatively prime. This condition is satisfied by factoring 20 from the coefficients of the HLDE to yield 3[X.sub.1] + 4[X.sub.2] = 0. Table 4 contains the details of the algorithm.

Since 3[X.sub.1]' + [X.sub.2] = 0 has a unit coefficient, it can be solved as:

[X.sub.2] = -3[X.sub.1]'. (15)

By substituting [X.sub.1] = [X.sub.1]' - [X.sub.2] and employing equation 15 we obtain:

[X.sub.1] = 4[X.sub.1]'. (16)

Thus equations 15 and 16 for an arbitrary [X.sub.1]' yield a general solution to the HLDE. Now according to Theorem 3 the general solution to our LDE is defined by adding [X.sub.1]** and [X.sub.2]** to equations 15 and 16 respectively to obtain:

[X.sub.1] = 4[X.sub.1]' - 50, (17)

[X.sub.2] = -3[X.sub.1]' + 50. (18)

The mathematical model for the problem requires the values of [X.sub.1] and [X.sub.2] to be nonnegative. Thus the inequalities (4[X.sub.1]' - 50 [greater than or equal to] 0) and (-3[X.sub.1]' + 50 [greater than or equal to] 0) are solved. Applying basic algebra yields ([X.sub.1]' [greater than or equal to] 12.5) and ([X.sub.1]' [less than or equal to] 16.3) and the integer values satisfying these inequalities are [X.sub.1]' = 13, 14, 15, and 16.

Using these four values of [X.sub.1]' and the general formulas for [X.sub.1] (equation 17) and [X.sub.2] (equation 18) yields the following four sets of solutions:

1 [X.sub.1] = 2 and [X.sub.2] = 11,

2 [X.sub.1] = 6 and [X.sub.2] = 8,

3 [X.sub.1] = 10 and [X.sub.2] = 5, and

4 [X.sub.1] = 14 and [X.sub.2] = 2.

COMPARING THE SOLUTION METHODOLOGIES

In an effort to compare the two methodologies, the branch and bound algorithm was first employed to solve the real estate developer's dilemma. The following result was obtained:

[X.sub.1] = 2 and [X.sub.2] = 11.

The branch and bound methodology provided one of the four solutions the LDE approach produced. Any attempt to obtain other solutions would involve "seek and destroy" branching strategies with no guarantee of finding other integer solutions, indicating some rigidity with the enumeration technique. Additionally, offering an initial solution to a software package in an attempt to obtain an alternate solution on another branch proved unsuccessful.

Thus, a limitation of the branch and bound approach to solving integer allocation problems has been revealed. The use of branching algorithms to solve integral resource allocation problems offers little control in obtaining a solution much less a full set of multiple solutions. The use of such algorithms provides no mechanism for obtaining alternative solutions without an exhaustive search.

Although the LDE approach provides no single optimum solution, it does have the flexibility of providing all possible alternate solutions to an integer resource allocation problem. This gives decision-makers the choice of observing alternate solutions and performing their own sensitivity analysis, maybe even satisfying other less important objectives that are overlooked by the use of the branching technique. For our example, the real estate developer may feel that 60 ft. wide lots could be easier to sell and therefore wish to have more of them.

CONCLUDING REMARKS

The authors' purpose in exploring this topic is threefold. First, the purpose served by this research is to present a methodology to confront problems with alternative solutions incurred by decision makers. The authors, all of whom teach quantitative analysis (QA) courses, realize the need to incorporate the solution of integer allocation problems in QA curriculums. Students enrolled in QA for Management courses are encouraged to apply various techniques to organizational decision-making situations. However, analyzing the solution of integer allocation problems is not usually presented in great detail in most QA texts (Kurosaka, 1986). The methodologies presented in this paper would be welcomed by many students due to the simplicity and straightforward solution process.

Second, in exploring an alternate approach to solving LDEs, it has been found that a general solution to an LDE can be formulated for any LDE which has an initial solution. Naturally, the advancement of a general solution to LDEs is beneficial for any application in which multiple solutions are desirable. The integer allocation example cited here is just one of numerous applications which could benefit from this methodology. Problems in which integer solutions are desired have traditionally been explored as IP problems (Elmaghraby and Elimam, 1980). In a practical sense, the modeling of problems as LDEs in many cases can provide a more realistic view of decision tradeoffs.

The third purpose of this paper was a comparison of the methodology of the LDE approach to the results obtained by solving the same problem using the branch and bound approach. By utilizing the more traditional technique of branching in order to solve the developer's dilemma, it was shown that the branch and bound approach does not provide the flexibility of the LDE method.

The authors hope to continue to pursue a range of applications using this alternate approach to solving LDE's. Hopefully, this pursuit will lead to a greater realization for management's need to develop skills to solve problems with multiple solutions.

REFERENCES

Barnett, I.A. (1969). Elements of Number Theory. Boston, Massachusetts: Prindle, Weber & Scmidt, Inc.

Beale, E., and R. Small (1965). Mixed Integer Programming by a Branch and Bound Technique. Proceedings of the Third IFIP Congress, 2, 450-451.

Blankinship, W.A. (1963). A New Version of the Euclidean Algorithm. American Mathematical Monthly, 70(September), 742-745.

Dakin, R. (1965). A Tree Search Algorithm for Mixed Integer Programming Problems. Computer Journal, 8, 250-255.

Driebeek, N.(1966). An Algorithm for the Solution of Mixed Integer Programming Problems. Management Science, 12(7), 576-587.

Elmaghraby, S.E., and A.A. Elimam (1980). Knapsack-Based Approaches to the Makespan Problem on Multiple Processors. AIIE Transactions, 12(1), 87-96.

Hillier, F.S., and G.J. Lieberman (1974). Operations Research. San Francisco, California: Holdan-Day, Inc.

Ibaraki, T., and N. Katoh (1988). Resource Allocation Problems: Algorithmic Approaches. Cambridge, Massachusetts: The MIT Press.

Kaplan, W. (1958). Ordinary Differential Equations. Reading, Massachusetts: Addison-Wesley.

Kurosaka, R.T. (1986). Diophantine Equations. Byte Magazine, 11(March), 343-350.

Land, A., and A. Doig (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3), 497-520.

Little, J., K. Murty, D. Sweeney, and C. Karel (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972-989.

MacDuffee C.C. (1954). Theory of Equations. New York City, New York: John Wiley.

Rowe, N.C. (1986). Diophantine Inference on a Statistical Database. Information Processing Letters, 18(1), January 20, 25-31.

Salkin, H.M. (1975). Integer Programming. Reading, Massachusetts: Addison-Wesley.

Stewart, B.M. (1952). Theory of Numbers. New York City, New York: The MacMillan Company.

Stewart, I. (1992). The Riddle of the Vanishing Camel. Scientific American, 266(June), 122-124.

Thompson, G. (1964). The Stopped Simplex Method: I. Basic Theory for Mixed Integer Programming; Integer Program. Revue Francaise de Recherche Operationnelle, 155-182.

Tomlin, J. (1970). Branch and Bound Methods for Integer and Non-Convex Programming. In Abadie (Ed.), Integer and Nonlinear Programming. North Holland.

Tomlin, J. (1971). An Improved Branch-and-Bound Method for Integer Programming. Operations Research, 19(4), 1070-1075.

Robert F. Cope III, Southeastern Louisiana University

Daniel G. Hotard, Southeastern Louisiana University

Rachelle F. Cope, Southeastern Louisiana University

Table 1: Illustration of BVEA for [A.sub.1] = 10, [A.sub.2] = 12
and [A.sub.3] = 8

i Operator Operand Q Matrix Compute
 [M.sub.i]

1 8 10 1 2 1 0 -1 [M.sub.1j] -
 Q * [M.sub.3j]
 12 1 4 0 1 -1 [M.sub.2j] -
 Q * [M.sub.3j]
 (Operator Row) ==> 8 0 0 1 for j = 1 to 4
2 2 (Operator Row) ==> 2 1 0 -1 for j = 1 to 4
 4 2 0 -2 1 1 [M.sub.2j] -
 Q * [M.sub.1j]
 8 4 0 -4 0 5 [M.sub.3j] -
 Q * [M.sub.1j]

Table 2: Illustration of the Unit Coefficient Reduction Algorithm

HLDE Iteration Step

3[X.sub.1]+5[X.sub.2]+ 1 1
17[X.sub.3]+
156[X.sub.4] = 0

 2

3([X.sub.1]'-[X.sub.2])+ 3
5[X.sub.2]+17[X.sub.3]+
156[X.sub.4] = 0
3[X.sub.1]'+2[X.sub.2]+
17[X.sub.3]+
156[X.sub.4] = 0

3[X.sub.1]'+2[X.sub.2]+ 2 1
17[X.sub.3]+
156[X.sub.4] = 0 2

3[X.sub.1]'+2([X.sub.2]'- 3
[X.sub.1]')+17[X.sub.3]+
156[X.sub.4] = 0
[X.sub.1]'+2[X.sub.2]'+
17[X.sub.3]+156[X.sub.4] = 0

HLDE Action

3[X.sub.1]+5[X.sub.2]+ Min = [A.sub.1] = 3
17[X.sub.3]+ SMin = A1 = 5
156[X.sub.4] = 0
 Use Div. Algorithm
 5 = 3q + r
 q = 1; r = 2

3([X.sub.1]'-[X.sub.2])+ [X.sub.1] = [X.sub.1]' - [X.sub.2]
5[X.sub.2]+17[X.sub.3]+ Substitute
156[X.sub.4] = 0 Simplify
3[X.sub.1]'+2[X.sub.2]+ r [not equal to] 1
17[X.sub.3]+
156[X.sub.4] = 0

3[X.sub.1]'+2[X.sub.2]+ Min = [A.sub.2] = 2
17[X.sub.3]+ SMin = [A.sub.1] = 3
156[X.sub.4] = 0 Use Div. Algorithm
 3 = 2q + r
 q = 1; r = 1

3[X.sub.1]'+2([X.sub.2]'- [X.sub.2] = [X.sub.2]' - [X.sub.1]'
[X.sub.1]')+17[X.sub.3]+ Substitute
156[X.sub.4] = 0 Simplify
[X.sub.1]'+2[X.sub.2]'+ r = 1
17[X.sub.3]+156[X.sub.4] = 0

Table 3: BVEA Applied Using [A.sub.1] = 60 and [A.sub.2] = 80

Pass i Operator Operand Q

1 60 80 1

2 20 60 3

Pass i Matrix [M.sub.1] Compute

1 60 1 0 for j = 1 to 3
 20 -1 1 [M.sub.2j] - Q * [M.sub.1j]
2 0 4 -3 [M.sub.1j] - Q * [M.sub.2j]
 20 -1 1 for j = 1 to 3

Table 4: Unit Coefficient Reduction Algorithm Applied to
3[X.sub.1] + 4[X.sub.2] = 0

HLDE Iteration Step Action

3[X.sub.1]+ 1 1 Min = [A.sub.1] = 3
4[X.sub.2] = 0 SMin = [A.sub.2] = 4

 2 Use Div. Algorithm
 4 = 3q + r
 q = 1; r = 1

3([X.sub.1]'- 3 [X.sub.1] = [X.sub.1]'
[X.sub.2])+ - [X.sub.2]
4[X.sub.2] = 0 Substitute
3[X.sub.1]'+ Simplify
[X.sub.2] = 0 r = 1