lap.h File Reference

Linear assignment problem solver. More...

Go to the source code of this file.

Macros
#define	BIG   2147483647

Typedefs
typedef int	row
typedef int	col
typedef int	cost

Functions
int	LAP_lap (int dim, int **assigncost, int *rowsol, int *colsol, int *u, int *v)
void	LAP_checklap (int dim, int **assigncost, int *rowsol, int *colsol, int *u, int *v)

Detailed Description

Linear assignment problem solver.

This module solves linear assignment problems according to:

"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing 38, 325-340, 1987

by

R. Jonker and A. Volgenant, University of Amsterdam.

(Author: Roy Jonker, MagicLogic Optimization Inc.)

Function Documentation

void LAP_checklap	(	int	dim,
		int **	assigncost,
		int *	rowsol,
		int *	colsol,
		int *	u,
		int *	v
	)

Check linear assignment solution.

Check a linear assignment solution (?).

Parameters

dim	problem size
assigncost	cost matrix
rowsol	column assigned to row in solution
colsol	row assigned to column in solution
u	dual variables, row reduction numbers
v	dual variables, column reduction numbers

int LAP_lap	(	int	dim,
		int **	assigncost,
		int *	rowsol,
		int *	colsol,
		int *	u,
		int *	v
	)

Solve linear assignment problem.

Solve a linear assignment problem.

Parameters

dim	problem size
assigncost	cost matrix
rowsol	column assigned to row in solution
colsol	row assigned to column in solution
u	dual variables, row reduction numbers
v	dual variables, column reduction numbers