A Dynamical System Based Heuristic for a Class of Constrained Semi-Assignment Problems

We consider Constrained Semi-Assignment Problems, where one has to optimally assign discrete values to decision variables, and where furthermore logical constraints restrict the set of feasible assignments. We present a heuristic approach based on a continuous relaxation. More precisely, we consider a discrete dynamical system evolving in the interior of a polytope whose extremal points correspond to all possible (both feasible and infeasible) assignments. The constructed dynamical system combines the effects of two dynamics: The first one, being of gradient-type, has the task of attracting the system towards assignments with high objective value, the second dynamic should give a rejecting power to forbidden assignments. Local properties of the system and numerical experiments are discussed.