Incorporating Decision Analysis into Solutions to Integer Resource Allocation Problems

By Cope, Robert F.,, III; Hotard, Daniel G. et al. | Academy of Information and Management Sciences Journal, January-July 2001 | Go to article overview

Incorporating Decision Analysis into Solutions to Integer Resource Allocation Problems


Cope, Robert F.,, III, Hotard, Daniel G., Cope, Rachelle F., Academy of Information and Management Sciences Journal


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 rest of this article is only available to active members of Questia

Sign up now for a free, 1-day trial and receive full access to:

  • Questia's entire collection
  • Automatic bibliography creation
  • More helpful research tools like notes, citations, and highlights
  • A full archive of books and articles related to this one
  • Ad-free environment

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

Project items include:
  • Saved book/article
  • Highlights
  • Quotes/citations
  • Notes
  • Bookmarks
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited article

Incorporating Decision Analysis into Solutions to Integer Resource Allocation Problems
Settings

Settings

Typeface
Text size Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Help
Full screen

matching results for page

    Questia reader help

    How to highlight and cite specific passages

    1. Click or tap the first word you want to select.
    2. Click or tap the last word you want to select, and you’ll see everything in between get selected.
    3. You’ll then get a menu of options like creating a highlight or a citation from that passage of text.

    OK, got it!

    Cited passage

    Style
    Citations are available only to our active members.
    Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

    1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

    Cited passage

    Thanks for trying Questia!

    Please continue trying out our research tools, but please note, full functionality is available only to our active members.

    Your work will be lost once you leave this Web page.

    For full access in an ad-free environment, sign up now for a FREE, 1-day trial.

    Already a member? Log in now.