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

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.
Last revised on 18 October 2023.