CaR: A Cutting and Repulsion-Based Evolutionary Framework for Mixed-Integer Programming Problems
CaR: A Cutting and Repulsion-Based Evolutionary Framework for Mixed-Integer Programming Problems
复制标题
DOI：
10.1109/tcyb.2021.3103778
复制
发表时间：
2021-09
影响因子：
11.8
通讯作者：
Jiao Liu;Yong Wang;Pei-qiu Huang;Shouyong Jiang
中科院分区：
文献类型：
--
作者：
Jiao Liu;Yong Wang;Pei-qiu Huang;Shouyong Jiang
混合整数规划（MIP）问题同时包含约束和整数约束。模糊约束将约束定义的可行域划分为多个不连续的可行部分。特别地，不连续可行部分的数量将随着整数决策变量的数量和/或每个整数决策变量的候选集的大小的增加而急剧增加。由于最优解位于不连续的可行部分之一，这是一个具有挑战性的任务来解决MIP问题。本文提出了一种基于切割和排斥的进化框架（称为CaR）来解决MIP问题。CaR包括两个主要策略：1）切割策略和2）排斥策略。在裁剪策略中，基于目前为止找到的最优个体的目标函数值构造一个附加约束，其目的是连续裁剪不具有前景的不连续可行部分。结果，可以降低种群进入错误的不连续可行部分的概率。此外，在排斥策略中，一旦检测到种群已经收敛到不连续的可行部分，种群将被重新初始化。此外，排斥函数的设计，以排斥以前探索的不连续可行部分。总体而言，切割策略可以显着减少不连续可行部分的数量，排斥策略可以探测剩余的不连续可行部分。本文开发的16个测试问题和两个真实案例被用来验证CaR的有效性。实验结果表明，CaR算法在求解MIP问题时具有较好的性能.
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.