CaR: A Cutting and Repulsion-Based Evolutionary Framework for Mixed-Integer Programming Problems

A mixed-integer programming (MIP) problem contains both constraints and integer restrictions. Integer restrictions divide the feasible region defined by constraints into multiple discontinuous feasible parts. In particular, the number of discontinuous feasible parts will drastically increase with the increase of the number of integer decision variables and/or the size of the candidate set of each integer decision variable. Due to the fact that the optimal solution is located in one of the discontinuous feasible parts, it is a challenging task to solve a MIP problem. This article presents a cutting and repulsion-based evolutionary framework (called CaR) to solve MIP problems. CaR includes two main strategies: 1) the cutting strategy and 2) the repulsion strategy. In the cutting strategy, an additional constraint is constructed based on the objective function value of the best individual found so far, the aim of which is to continuously cut unpromising discontinuous feasible parts. As a result, the probability of the population entering a wrong discontinuous feasible part can be decreased. In addition, in the repulsion strategy, once it has been detected that the population has converged to a discontinuous feasible part, the population will be reinitialized. Moreover, a repulsion function is designed to repulse the previously explored discontinuous feasible parts. Overall, the cutting strategy can significantly reduce the number of discontinuous feasible parts and the repulsion strategy can probe the remaining discontinuous feasible parts. Sixteen test problems developed in this article and two real-world cases are used to verify the effectiveness of CaR. The results demonstrate that CaR performs well in solving MIP problems.