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

Jiao Liu, Yong Wang* (Corresponding Author), Pei Qiu Huang* (Corresponding Author), Shouyong Jiang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)13129 - 13141
Number of pages13
JournalIEEE Transactions on Cybernetics
Issue number12
Early online date14 Sept 2021
Publication statusPublished - Dec 2022

Bibliographical note

This work was supported by the National Natural Science
Foundation of China under Grant 61976225.

Data Availability Statement

This article has supplementary material provided by the
authors and color versions of one or more figures available at


  • Automobiles
  • Cutting
  • differential evolution (DE)
  • evolutionary algorithms (EAs)
  • Linear programming
  • mixed-integer programming (MIP) problems
  • Optimization
  • Programming
  • repulsion.
  • Sociology
  • Statistics
  • Upper bound


Dive into the research topics of 'CaR: A Cutting and Repulsion-Based Evolutionary Framework for Mixed-Integer Programming Problems'. Together they form a unique fingerprint.

Cite this