基于半定规划的{0,1}-经济调度

摘要

基于内点半定规划,提出一种直接求解{0,1}-经济调度问题({0,1}-ED)的新方法.通过引入辅助变量,该方法将原整数变量约束转化为凸二次约束,进而将{0,1}-ED问题转化为半定规划问题,并用内点法进行求解.对于大系统整数变量的微小偏差,应用简单的启发式技术调整.ED-420等9个测试系统的仿真结果表明,所提方法能够有效地处理{0,1}-经济调度,对于大多数问题都可以得到较精确的结果,计算时间具有多项式复杂性.