Solving Discrete Mathematics Problems Using Linear Programming and Assignment Matrices

Article excerpt

(ProQuest: ... denotes formulae omitted.)


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

. …