Ejection chain moves for automatic neighborhood synthesis in constrained cardinality-minimization problems

In this paper, we deal with the problem of automatically synthesizing "good" neighborhoods for a specific class of problems, namely constrained cardinality-minimization problems. Exploiting the peculiarity of the objective function of such problems, we develop automatic ejection chain moves that define neighborhood structures to be explored with a black-box solver. In particular, starting from a formulation of a cardinality-minimization problem and a feasible solution, our procedure automatically detects the "entities" involved in the problem and learns the strength of the relationships among them. This information is then used to define the characteristics of our moves that consist in ejecting one entity at a time from the solution. If one of such moves results in an infeasible solution, then feasibility is recovered by performing an additional step based on the solution of an auxiliary problem. The computational results show that, when assessed on four well-known constrained cardinality-minimization problems, our approach outperforms both a black-box mixed integer programming solver and a state-of-the-art model-based neighborhood search procedure with respect to both solution quality and computing times.