# 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:

. …

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

Highlights (0)
Some of your highlights are legacy items.
Citations (0)
Some of your citations are legacy items.
Notes (0)
Bookmarks (0)

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

#### Cited article

Style
Citations are available only to our active members.

(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 Reset View mode
Search within

Look up

#### Look up a word

• Dictionary
• Thesaurus
Please submit a word or phrase above.

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

Help
Full screen

### 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.

## Cited passage

Style
Citations are available only to our active members.

"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.

## 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.