Solving Discrete Mathematics Problems Using Linear Programming and Assignment Matrices

By Jerome, Lawrence | Mathematics and Computer Education, Fall 2012 | Go to article overview

Solving Discrete Mathematics Problems Using Linear Programming and Assignment Matrices


Jerome, Lawrence, Mathematics and Computer Education


(ProQuest: ... denotes formulae omitted.)

INTRODUCTION

The use of assignment matrices and linear programming has been expanded from the usual binary assignment matrix to integer and decimal matrices for solving a wide variety of Discrete Mathematics problems that are usually approached using complex scan and label and other algorithms. Among the types of problems that can be solved using assignment matrices and linear programming are knapsack, bottleneck, independent set, matching, Travelling Salesman, and max flow problems. Four different examples are given to demonstrate the methodology and ease with which these problems can be set up and solved in Excel using Excel Solvers, thus making linear programming via assignment matrices accessible to Discrete Mathematics instructors and students.

The development of this article began with one-dimensional binary assignment matrices for solving knapsack problems, expanded to twodimensional binary matrices for solving independent sets, simple bottleneck, and simple matching problems. While studying the Travelling Salesman Problem, the author realized that a one-dimensional integer matrix with alldifferent constraints was yet another form of assignment matrix. Finally, the study of transportation time and cost problems with their decimal matrices and integer allocation matrices, led to the concept of generalized assignment matrices, each type useful for solving different Discrete Mathematics problems using different linear programming constraints.

Table 1 shows the various types of problems that can be solved using linear programming and assignment matrices along with their assignment matrix type.

Assignment matrix methodology in linear programming has been used for some years [1, 2, 3, 4, 5], but the method has been severely restricted because researchers programmed each individual problem, usually in Fortran. However, if a general linear programming software could be applied to these assignment problems, the methodology could become available to the wider Discrete Mathematics community. Excel Solver and Excel Premium Solver have been found to be quite suitable for this task, providing both an easy visual platform for matrices and their constraints, along with linear programming engines that can input answers directly into assignment matrices. Using Excel Solvers in conjunction with assignment matrices gives Discrete Mathematics instructors and students a valuable tool for solving a wide variety of Discrete Mathematics problems that normally are approached via complex scan and label algorithms.

ASSIGNMENT MATRICES

Assignment matrices traditionally have been restricted to binary constraints in the linear programming solutions of bottleneck and assignment problems. [1, 2, 3, 4, 5] A binary assignment matrix has the following mathematical definition:

... (1)

A binary matrix consists of just 0's and l's. In the case of a simple bottleneck problem [1], where a single item is assigned to a single unit, there is only one 1 per row and column, and the rest of the binary matrix is all zeros (simple binary assignment matrix in Table 1). A simple binary matrix looks like an identity matrix, except the 1 's aren't necessarily on the main diagonal. In the case of generalized bottleneck problems, where more than one item can be assigned to each unit, the binary assignment matrix can have more than one 1 per row (complex binary matrix in Table 1).

By applying this methodology to an ever widening range of problem types, it has been discovered that the assignment matrix methodology can be extended to include non-binary matrices, including integer and decimal entries. Table 1 summarizes the problem types which can be solved using assignment matrices and linear programming, along with the type of assignment matrix, while Table 2 shows the different linear programming constraints associated with each assignment matrix type.

Based on Tables 1 and 2, we can define the generalized assignment matrix as:

. …

The rest of this article is only available to active members of Questia

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.
Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

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

Solving Discrete Mathematics Problems Using Linear Programming and Assignment Matrices
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.
    Buy instant access 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.

    Buy instant access to save your work.

    Already a member? Log in now.

    Author Advanced search

    Oops!

    An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.