Semi-assignment problem

From Glossary

Jump to: navigation, search

This is like the assignment problem, except only the rows or the columns (not both) of the assignment matrix is constrained to equal 1. With linear objective, the problem is:

\min \sum_{i, j} \mbox{C}(i, j) \mbox{ X}(i, j): \mbox{ X} \le 0, \sum_{i} \mbox{X}(i, j) = 1 \mbox{ for all } j.

(The sum constraint could be over j, for all i.) An example is to assign jobs to people, but allow some jobs to be assigned to more than one person and some jobs not assigned at all. A more realistic example arises in biology. We are given a rotamer library of side chain confirmations, and each amino acid residue in a protein must be assigned some rotamer. The same rotamer could be assigned to more than one site, and some rotamers need not be assigned at all.

Personal tools