SEMI-ASSIGNMENT PROBLEM
Semi-assignment problem - 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 (C(i, j) X(i, j)): X >= 0, sumi X(i, j) = 1 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 assignedto more than one person and some jobs not assigned at all. A more realisticexample arises in biology. We are given a
rotamer library of side chain confirmations, and eachamino acid residue in a protein must be assigned some rotamer. The samerotamer could be assigned to more than one site, and some rotamers need notbe assigned at all.
