求解最小支配集的线性混合整型规划算法

提出了一个高效的求解最小支配集问题的线性混合整数规划算法(MILP)。该算法主要针对最小支配集问题的特点建立整数规划模型,并通过Gurobi求解器进行优化求解。采用当前国际文献公开的共74个算例作为算法测试实验集,与FKW算法、传统的Grandoni算法以及改进的Grandoni算法进行比较。实验结果表明,该算法的计算效率明显优于其它的精确算法,且在所有算例上都能得到精确解。

虚拟电厂内部资源调度算法的对比分析及应用

分布式发电资源的广泛应用对各类分布式发电机组的协调并网运行及其与传统发电机组的联合调度提出了新的要求。结合微型热电联产机组等分布式发电机组的特性,引入通用虚拟电厂技术,分析虚拟电厂内部发电资源优化调度算法,基于传统调度方法提出三种改进的调度算法,并通过实例分析对比了三种算法的寻优结果及运行时间。结果表明,基于混合整数线性规划算法与启发式算法的启发式线性规划改进算法有利于虚拟电厂业主获得更好的经济与环保收益以及更快的运算时间。

耦合风光储及热泵的CCHP系统集成优化与运行特性研究

为提高可再生能源的有效利用和冷热电联供系统的综合性能,在天然气冷热电联供系统中引入光伏电池、风力发电、地源热泵和储能单元,构建一种耦合可再生能源的天然气冷热电联供(wind-solar-storage and heat pump,combined cooling,heating and power,WSSH-CCHP)系统,利用层次分析法(analytic hierarchy process,AHP)建立考虑能效、经济及环境性能的综合评价指标,采用混合整数线性规划(mixed integer linear programming,MILP)算法,对该系统进行设备选型、容量配置及运行策略协同优化,以分供系统(separate production,SP)为参照系统,以济南市某能源中心为例,分析该系统集成优化效果及其运行特性。研究结果表明,该系统的综合指标优化结果相比SP系统提高37.8%,具有较好的综合性能,为耦合风光储及热泵天然气CCHP系统的发展及其集成优化与运行特性研究提供了参考。

基于MILP的GIFT积分区分器搜索及优化

Banik等提出的轻量级分组密码GIFT算法已经入选了NIST针对国际轻量级密码算法开展的标准化竞赛的最终轮。目前已有针对其的线性分析、差分分析等的相关研究,但针对GIFT的积分分析仍待进一步研究。针对GIFT在积分密码分析过程中可分路径表达冗余的问题,提出了基于混合整数线性规划模型的积分区分器搜索求解和优化算法。首先对GIFT算法创建MILP积分分析模型,利用可分性质分别对GIFT算法的线性层和非线性层进行刻画。对线性层利用传播规则进行表达;对非线性S盒在传播规则的基础上使用贪心算法对表达式进行精简优化,得到了15个不等式作为约束条件。经过MILP求解后,得到64个9轮积分区分器。在此基础上,针对基于贪心算法的MILP求解模型精确度不足问题,引入MILP模型对S盒的可分性质进行重新表达,设计基于MILP的约简算法对GIFT积分区分器搜索进行优化,并重新求解MILP模型,最高得到了3个13轮的积分区分器。因此,基于MILP的S盒新约简算法可以优化S盒可分性质的表达,有效增加对GIFT算法的积分区分器攻击轮数,提高积分攻击效果。

作动器最优配置的柔性结构振动主动控制

柔性结构广泛应用于航空航天等领域,为了获得结构的最佳动力学性能,在主动振动控制中作动器或传感器位置优化成为关键。基于结构有限元动力学方程,在状态空间利用系统可控和可观Gramian矩阵考虑结构剩余模态的影响,推导一种新的作动器/传感器优化准则。根据优化准则结合非线性整数规划遗传算法对作动器的位置进行配置。以悬臂板为研究对象,采用基于状态反馈的线性二次型调节器研究悬臂板的振动控制效果。与其他配置方法进行比较,验证了新方法的优越性。

A Modified Algorithm for Nonliear Integer Programming

Based on the analysis to the random sear ch algorithm of LUUS, a modified random directed integer search algorithm (MRDI SA) is given for first time. And a practical example is given to show that the adva ntage of this kind of algorithm is the reliability can’t be infuenced by the ini tial value X (0) and the start search domain R (0) . Besides, i t can be applied to solve the higher dimensional constrained nonlinear integer p rogramming problem.

含微电网群的主动配电网双层联合优化调度

主动配电网下分布式能源系统的调度优化是实现经济及安全运行的重要保障,也是提高分布式能源有效利用率的重要途径。基于泛在电力互联网需求,针对含有风电、光伏和储能装置的微电网群,构建含微电网群的主动配电网双层联合调度模型,提出了一种考虑微电网群共同参与主动电网运行的双层联合调度模式,实现双层优化:上层模型以配电网为研究对象,优化目标为提高电能质量、减少线损;下层模型以微电网为研究对象,优化目标为微电网运行成本最低。应用遗传算法求解上层优化模型,应用混合整数线性规划求解下层优化模型。以调整后的IEEE-33节点配电网系统为例,进行相应仿真实验,从而验证其应用在含微电网群的主动配电网优化领域的合理性与有效性。

充电场站光储充控制策略

针对充电需求带来的负荷具有不确定性,以及在不控制的情况下会在高峰期造成充电场站变压器过载等问题,本文提出了一种通过配置光伏和储能来提升充电场站的有效充电功率或服务能力的方法,并通过优化控制算法达到负荷跟踪的效果。该方法以每日光伏发电功率、用户负荷功率和每日分时电价为输入量。通过对3种应用场景的对比,可以定量计算出光伏和储能协同控制所带来的收益。为了对模型进行有效求解,本文提出和对比了两种不同的算法:粒子群算法和混合整数线性规划算法。这两种算法均可以用于确定储能控制策略并优化光储能系统的出力,但各有优缺点。计算结果表明,简单的低价充电、高价放电的充放电模式,不能快速应对变化的负荷功率;基于粒子群算法的储能控制策略能解决负荷跟踪问题并求得局部最优解,但达不到储能的最大利用率;而基于混合整数线性规划算法,可求得全局的最优解,达到接近100%的储能利用率,同时降低用户的日运行成本。通过动态调整储能充放电功率,可实现跟踪负荷功率、降低负荷峰值以避免变压器过载的功能,同时达到灵活应对复杂、多变的电力需求侧和供给侧的动态变化场景的目的。

One-parameter quasi-filled function algorithm for nonlinear integer programming

A definition of the quasi-filled function for nonlinear integer programming problem is given in this paper. A quasi-filled function satisfying our definition is presented. This function contains only one parameter. The properties of the pro- posed quasi-filled function and the method using this quasi-filled function to solve nonlinear integer programming problem are also discussed in this paper. Numerical results indicated the efficiency and reliability of the proposed quasi-filled function algo- rithm.

基于智慧能源的光纤通信网过载检测与升级优化

智慧能源带来了新的信息传输需求,如何优化传统电力光纤通信网络,在服务智慧能源的前提下尽量节约投资,是需要深入研究的课题。文章研究了新的信息传输业务出现后电力光纤通信环网的平滑升级,设计了光纤通信环网的过载检测及升级优化方案,提出了多环过载检测、业务路由和升级优化的整数线性规划(Integer Linear Programming,ILP)算法。该算法以增长后的业务为输入,形式化环内和环间业务路由,各环流量过载检测和升级优化节点设置为线性规划的约束条件,并最小化过载环个数和升级优化成本,以减少需升级的环和环上设备。以中国东部某城市的电力光纤网络为例,给出了业务增加后的过载环直接升级和重新优化升级2种方案,结果表明,过载环直接升级能保持环结构不变但成本高,重新优化升级能在较大程度上减少升级成本。

Efficient Algorithm for K-Barrier Coverage Based on Integer Linear Programming

Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest.However,in certain applications,barrier coverage cannot be satisfied after random deployment.In this paper,we study how mobile sensors can be efficiently relocated to achieve k-barrier coverage.In particular,two problems are studied:relocation of sensors with minimum number of mobile sensors and formation of k-barrier coverage with minimum energy cost.These two problems were formulated as 0–1 integer linear programming(ILP).The formulation is computationally intractable because of integrality and complicated constraints.Therefore,we relax the integrality and complicated constraints of the formulation and construct a special model known as RELAX-RSMN with a totally unimodular constraint coefficient matrix to solve the relaxed 0–1 ILP rapidly through linear programming.Theoretical analysis and simulation were performed to verify the effectiveness of our approach.

Modeling and Optimization for Short-term Scheduling of Multipurpose Batch Plants

In the past two decades, short-term scheduling of multipurpose batch plants has received significant attention. Most scheduling problems are modeled using either state-task-network or resource-task-network(RTN) process representation. In this paper, an improved mixed integer linear programming model for short-term schedul-ing of multipurpose batch plants under maximization of profit is proposed based on RTN representation and unit-specific events. To solve the model, a hybrid algorithm based on line-up competition algorithm and linear programming is presented. The proposed model and hybrid algorithm are applied to two benchmark examples in literature. The simulation results show that the proposed model and hybrid algorithm are effective for short-term scheduling of multipurpose batch plants.

A hybrid algorithm based on ILP and genetic algorithm for time-aware test case prioritization

To solve the problem of time-awarc test case prioritization,a hybrid algorithm composed of integer linear programming and the genetic algorithm(ILP-GA)is proposed.First,the test case suite which cm maximize the number of covered program entities a d satisfy time constraints is selected by integer linea progamming.Secondly,the individual is encoded according to the cover matrices of entities,and the coverage rate of program entities is used as the fitness function and the genetic algorithm is used to prioritize the selected test cases.Five typical open source projects are selected as benchmark programs.Branch and method are selected as program entities,and time constraint percentages a e 25%and 75%.The experimental results show that the ILP-GA convergence has faster speed and better stability than ILP-additional and IP-total in most cases,which contributes to the detection of software defects as early as possible and reduces the software testing costs.

Improved Hybrid Differential Evolution-Estimation of Distribution Algorithm with Feasibility Rules for NLP/MINLP Engineering Optimization Problems

In this paper, an improved hybrid differential evolution-estimation of distribution algorithm (IHDE-EDA) is proposed for nonlinear programming (NLP) and mixed integer nonlinear programming (MINLP) models in engineering optimization fields. In order to improve the global searching ability and convergence speed, IHDE-EDA takes full advantage of differential information and global statistical information extracted respectively from differential evolution algorithm and annealing mechanism-embedded estimation of distribution algorithm. Moreover, the feasibility rules are used to handle constraints, which do not require additional parameters and can guide the population to the feasible region quickly. The effectiveness of hybridization mechanism of IHDE-EDA is first discussed, and then simulation and comparison based on three benchmark problems demonstrate the efficiency, accuracy and robustness of IHDE-EDA. Finally, optimization on an industrial-size scheduling of two-pipeline crude oil blending problem shows the practical applicability of IHDE-EDA.

基于遗传算法的多约束网格检查对策问题研究

综合考虑物品数量以及列容量约束,将隐藏成本与检查概率引入支付函数.建立一种新的多约束的网格检查对策模型.根据矩阵对策性质及Holder不等式,将对策论问题转化为非线性整数规划问题.提出一个基于遗传算法的模型求解方法,将归一化处理得到的变量进行二进制编码,通过数据变换将问题转化为无约束问题,采用轮盘赌选择、多点交叉及单点变异操作求解模型.仿真结果表明了模型及所提算法的有效性.

面向时间优化的“任务-人员”匹配逆最优值方法:以石化设备抢修为例

一旦重大装备突发故障,如不能及时抢修,小则生产中断,大则引发生命、环境、经济等方面的重大损失。抢修具有时间紧、任务急、高度复杂性等特征。针对此类抢修实际问题,本文以最小化设备紧急抢修实际损失与机会损失为目标,考虑关键任务与非关键任务的工艺逻辑串并联顺序,构建“任务-人员”匹配正优化模型。然而,在该模型参数下,即使该模型的最优值仍超出同业对标成本容忍值,在此情况下,通过逆向思维,由果导因,逆向推演作业时间,构建对标成本值驱动的双层规划逆最优值模型。针对其0-1混合整数、非线性、双层规划、NP-hard的特征,设计混合“遗传-整数线性规划”算法,该算法结合了遗传算法的并行化和整数线性规划较好的全局搜索能力。基于企业实际调研与访谈获得相关数据,数值分析结果表明:逆最优值方法能够确保对标成本实现,给出“任务-人员-时间”指派方案。智能算法求解速度具有显著优势,对于抢修这类时间紧、任务急、情况复杂的问题更加适用。本方法可以应用在更广泛的领域,例如:项目工期进度控制、人力资源绩效管理的标准工时制定、目标管理视角的资源配置决策等多个领域,以预期结果为源动力,同时获得决策参数和方案的一类问题,都可以得到方法启发和思路借鉴。