LAMP
Linear Assignment and Matching Problems

LAMP is a FORTRAN77 program which implements various algorithms for linear assignment and matching problems, by Rainer Burkard, Ulrich Derigs.

The problems that are considered include:

• 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;
• the quadratic assignment problem;

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.

Languages:

LAMP is available in a FORTRAN77 version.

Related Data and Programs:

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.

Examples and Tests:

• lamp_prb.f, a sample calling program.
• lamp_prb.sh, commands to compile and run the sample program.
• lamp_prb_output.txt, the output file.

List of Routines:

• ALTKOS is used by QAP to determine alternative costs.
• BMP solves the bottleneck matching problem.
• CMP solves the cardinality matching problem.
• CONNECT checks the connectivity of a graph.
• CPP solves the Chinese Postman Problem.
• DREIER carries out the triple exchange routine for QAPH2.
• ERW expands a blossom for CPP.
• HEIDER examines the pairwise interchanges for QAPH2.
• KASU duplicates matching edges for CPP.
• LBAP solves the linear bottleneck assignment problem.
• LSAPI solves the linear sum assignment problem with integer data.
• LSAPR solves the linear sum assignment problem with real data.
• PROGNO is used by QAP to compute the linear subproblem cost matrix.
• PRUEF1 is used by CPP to scan node BB.
• PRUEF2 is used by CPP to scan nodes BB2 and BBB.
• QAP solves the quadratic assignment problem.
• QAPH1 is a heuristic solver for quadratic assignment problems.
• QAPH2 is a heuristic solver for quadratic assignment problems.
• R4_UNIFORM_01 returns a unit pseudorandom R4.
• REIHEN choose a start sequence for QAPH2'S pairwise exchange algorithm.
• SCAN1 scans a node for the SMP algorithm.
• SCAN2 scans a node for the SMP algorithm.
• SCHR shrinks a blossom for CPP.
• SMP solves the sum matching problem.
• SSORT sorts an integer vector, and rearranges a second one.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.
• TOUR determines an Eulerian tour for CPP.
• WEGSPE is used by QAP to order elements from the matrices A and B.
• ZUFALL determines a random permutation.

You can go up one level to the FORTRAN77 source codes.