The ASSIGN Procedure

Overview

The ASSIGN procedure finds the minimum or maximum cost assignment of m sink nodes to n source nodes. The procedure can handle problems where m=,<,>n,.

When n = m, the number of source nodes equals the number of sink nodes and the procedure solves

${min(max)}\Sigma_{j=1}^m\Sigma_{i=1}^nc_{ij}x_{ij}$

subject to: $\Sigma_{j=1}^m x_{ij}$ = 1 for i=1,...,n

$\Sigma_{i=1}^n x_{ij}$ = 1 for j=1,...,m

where x=0 or 1 for i=1,...,n and j=1,...,m

When n < m, the number of source nodes is less than the number of sink nodes and the procedure solves

${min(max)}\Sigma_{j=1}^m\Sigma_{i=1}^nc_{ij}x_{ij}$

subject to: $\Sigma_{j=1}^m x_{ij}$ = 1 for i=1,...,n

$\Sigma_{i=1}^n x_{ij} \leq 1$ for j=1,...,m

where x=0 or 1 for i=1,...,n and j=1,...,m

When n > m, the number of source nodes is greater than the number of sink nodes and the procedure solves

${min(max)}\Sigma_{j=1}^m\Sigma_{i=1}^nc_{ij}x_{ij}$

subject to: $\Sigma_{j=1}^m x_{ij} \leq 1$ for i=1,...,n

$\Sigma_{i=1}^n x_{ij}$ = 1 for j=1,...,m

where x=0 or 1 for i=1,...,n and j=1,...,m

Chapter Contents
Previous
Next
Top

	${min(max)}\Sigma_{j=1}^m\Sigma_{i=1}^nc_{ij}x_{ij}$

subject to:	$\Sigma_{j=1}^m x_{ij}$ = 1 for i=1,...,n

	$\Sigma_{i=1}^n x_{ij}$ = 1 for j=1,...,m

where x=0 or 1 for i=1,...,n and j=1,...,m

	${min(max)}\Sigma_{j=1}^m\Sigma_{i=1}^nc_{ij}x_{ij}$

subject to:	$\Sigma_{j=1}^m x_{ij} \leq 1$ for i=1,...,n

	$\Sigma_{i=1}^n x_{ij}$ = 1 for j=1,...,m

where x=0 or 1 for i=1,...,n and j=1,...,m