lamp

lamp, a FORTRAN77 code which implements algorithms for linear assignment and matching problems, including the linear sum assignment problem, the linear bottleneck assignment problem, the cardinality matching problem, the sum matching problem, the bottleneck matching problem, the Chinese postman problem, and the quadratic assignment problem, by Rainer Burkard, Ulrich Derigs.

The program printed in the reference is written in FORTRAN IV. People who think FORTRAN77 or FORTRAN66 was primitive should take a look at this source code, to understand the evolution of programming.

• The FORTRAN IV code does not use doubly dimensioned arrays; instead, MxN information is packed into a vector, and retrieved by computing the linear address I+J*M from the 2D (I,J) address.
• The index of a vector was required to be a variable, not a variable expression. Even an expression like "X(I+1)" was illegal, and a variable had to be set aside to store the value of I+1.
• Because a DO loop would always be executed at least once, many such loops had to be protected by conditional jumps around them, in case the lower limit of the loop was greater than the upper limit.
• Programmers thought nothing of running a DO loop with index I, say, and jumping out of it when some condition occurred, and assuming that the value of I was preserved and available. Many compilers now regard this as an unsafe assumption.
• Another "cultural" issue was that programmers thought nothing of jumping out of a loop via a GOTO statement, doing some calculation, and then jumping back into the loop. Modern compilers produce warnings that this is an unsafe practice.
• The only way to form a compound statement was with statement labels. There was no DO/ENDDO or IF/ENDIF structure; there were only GOTO's. The extraordinarily ugly appearance of the resulting code, and the difficulty of comprehending the bizarre-looking text, is impossible to suggest. One must look at such code and struggle to understand it and then realize the advantage of simple modern control structures.
• Typing in the code, I was reminded yet again of the biggest horror of old FORTRAN, namely the fixed format scheme in which columns 7 through 72 were for text, column 6 (remember not to use '0' for continuation!) was for continuation, and columns 1 through 5 for statement labels, and 73 to 80 sequence numbers (remember those?). Accidentally violating these rules could result in deadly but silent bugs.

To some extent, the code has been "cleaned up", so that it is not a straight copy of the printed text.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

lamp is available in a FORTRAN77 version.

Related Data and Programs:

lamp_test

apportionment, a FORTRAN90 library which studies the apportionment problem for the US House of Representatives.

CODEPACK, a FORTRAN90 library which computes "codes" that can determine if two graphs are isomorphic.

COMBO, a FORTRAN90 library which handles various combinatorial tasks and computations.

GENERALIZED_ASSIGNMENT, a dataset directory which contains test data for the generalized assignment problem;

GRAFPACK, a FORTRAN90 library which contains many routines for handling abstract graphs.

KNAPSACK, a FORTRAN77 library which solves a variety of knapsack problems.

LAU_NP, a FORTRAN90 library which handles various NP hard problems.

LAUPACK, a FORTRAN90 library which computes various quantities associated with a graph.

PARTIAL_DIGEST, a FORTRAN90 library which solves the partial digest problem.

PARTITION_PROBLEM, a FORTRAN77 library which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

SELECT, a FORTRAN90 library which generates various combinatorial objects.

SUBSET, a FORTRAN90 library which handles various combinatorial problems.

Author:

Rainer Burkard, Ulrich Derigs

Reference:

1. Rainer Burkard, Ulrich Derigs,
   Assignment and Matching Problems: Solution methods with FORTRAN programs,
   Lecture Notes in Economics and Mathematical Systems,
   Volume 184,
   Springer, 1980,
   ISBN: 0387102671,
   LC: QA402.5.B86.

Source Code:

• lamp.f, the source code.
• lamp.sh, commands to compile the source code.