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

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


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.


Rainer Burkard, Ulrich Derigs


  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:

Examples and Tests:

List of Routines:

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

Last revised on 10 December 2007.