秦 军,赵莎莎

(1.中国矿业大学 理学院,江苏 徐州 221116; 2.广西大学 电气工程学院,广西 南宁 530004)

一类无约束非线性整数规划的区间算法

秦 军1,赵莎莎2

(1.中国矿业大学 理学院,江苏 徐州 221116; 2.广西大学 电气工程学院,广西 南宁 530004)

讨论目标函数为Lipschitz连续函数的无约束整数规划的数值算法．通过构造目标函数的区间扩张和无解区域删除检验原则,建立了求解无约束非线性整数规划的区间算法,并进行了数值实验．理论证明和数值实验均表明算法是可靠和有效的．

整数规划; 区间扩张; 区间算法; 无约束优化问题

0 引言

整数规划问题是当今最优化问题研究的难点和重点,是数学规划中常见的、复杂的一大类问题．整数规划广泛应用于许多工程领域,如资源管理、生产调度、可靠性优化、目标分配、超大规模集成电路设计等．由于求解整数规划问题的难度远比求解一般规划问题要大,因此对于整数规划,特别是非线性整数规划问题目前仍缺乏有效的通用算法,而且单层整数规划的难以求解已经成为二层以及多层整数规划算法研究的瓶颈问题．对于一般的整数规划,可使用分支定界法、割平面法和枚举法等求解[1]．而对于较大规模的整数规划问题,近年来随着进化计算的发展许多学者运用遗传算法[2]、模拟退火算法[3]、粒子群优化算法[4]、蚁群算法[5]等方法来求解．遗传算法是一种群体性全局寻优方法,它吸取了生物进化和遗传论的研究成果,但算法执行……