Peter Butkovic - software for download

The codes below may freely be downloaded. They have been compiled by research students under my supervision. All programs offer the option of entering the data manually or by random generation.

All programs have to be downloaded before running.

1. Max-algebra toolbox enables easy calculations in max-algebra, that is basic matrix operations, computation of the unique eigenvalue of a real matrix, metric matrix containing the basis of the eigenspace and generates discrete event dynamic systems. Input constants can be changed dynamically. Works only when downloaded. Prepared by Seth Lewis in Microsoft Excel using Visual Basic.


Read more in my papers "Max-algebra: the linear algebra of combinatorics?", "Minimal (max, +) realization of convex sequences" or "Reducible spectral theory with applications to the robustness of matrices in max-algebra".

2. The job rotation problem (JRP), sometimes also called the best principal submatrix problem, is the task for a given n x n matrix A and positive integer k < n to find a k x k principal submatrix of A whose optimal assignment problem value (maximisation) is maximal.

To our knowledge no polynomial algorithm for this problem exists, neither it has been proved that JRP is NP-complete. We provide two algorithms, the first one finds an exact solution and will deliver the result within minutes for matrices of order up to 20. The second one is using a number of heuristics to find an optimal or suboptimal solution for matrices of order 200 within minutes. Our tests show that the error does not exceed 0.24% on average.

Prepared by Baptiste Nenert in Matlab 7.2.

JRP exact. Run with command "job_rotation_problem".

JRP heuristic. Run with command "heuristic_jrp".

Read more in my papers "Max algebra and the linear assignment problem" or "Finding all essential terms of a characteristic maxpolynomial,"

3. Two-sided max-linear systems are systems of linear equations when the pair of operations (+, . ) is replaced by (max, + ).

They are of the form Ax = Bx (homogenous), Ax = By (homogenous with separated variables), or Ax + c = Bx + d (non-homogenous).

Max-linear programs are of the form h'x --> min or max subject to Ax + c = Bx + d.

All codes have been prepared by Abdulhadi Aminu in Matlab 7.2.

Homogenous. Run with the command "homogeneous2".

Homogenous with separated variables. Run with the command "homogeneous1".

Non-homogenous. Run with the command "nonhomogeneous".

Max-linear program (minimisation). Download also an auxiliary program and place it in the same directory. Run with the command "minimisation".

Max-linear program (maximisation). Download also an auxiliary program and place it in the same directory. Run with the command "maximisation".

Read more in our paper "The equation Ax=By over (max, +)".