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

The authors present a new procedure for solving the constrained assignment problem based on a combination of Lagrangean relaxation and constraint techniques. This procedure is applied to an assignment problem with side constraints, where subsets of variables are specified, and variables belonging to the same subset must have the same value. The procedure consists in adding of valid inequalities to the Lagrangean in order to get better bounds. Two classes of strong valid inequalities are described and it is shown how valid inequalities can be identified from infeasible solutions. The procedure is illustrated by a numerical example. The model can be applied to solve constrained job assignment or classroom assignment problems.