A facet generation and relaxation technique applied to an assignment problem with side constraints

The authors consider a solution method for combinatorial optimization problems based on a combination of Lagrangean relaxation and constraint generation techniques. The procedure is applied to a constrained assignment problem, where subsets of variables are specified, and variables belonging to the same subset must have the same value. The model can be applied to solve constrained job assignment or classroom assignment problems. The procedure the authors suggest requires only the solution of classical assignment subproblems. An illustrative numerical example is given.