Solution for integer linear bilevel programming problems using orthogonal genetic algorithm

An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.

An Exact Virtual Network Embedding Algorithm Based on Integer Linear Programming for Virtual Network Request with Location Constraint

Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.

Short-Term Scheduling of Combined Cycle Units Using Mixed Integer Linear Programming Solution

Combined cycle plants (CCs) are broadly used all over the world. The inclusion of CCs into the optimal resource scheduling causes difficulties because they can be operated in different operating configuration modes based on the number of combustion and steam turbines. In this paper a model CCs based on a mixed integer linear programming approach to be included into an optimal short term resource optimization problem is presented. The proposed method allows modeling of CCs in different modes of operation taking into account the non convex operating costs for the different combined cycle mode of operation.

A new heuristic algorithm for general integer linear programming problems

A new heuristic algorithm is proposed for solving general integer linear programming problems. In the algorithm, the objective function hyperplane is used as a cutting plane, and then by introducing a special set of assistant sets, an efficient heuristic search for the solution to the integer linear program is carried out in the sets on the objective function hyperplane. A simple numerical example shows that the algorithm is efficient for some problems, and therefore, of practical interest.

Application of Optimization Principle in Landmark University Project Selection under Multi-Period Capital Rationing Using Linear and Integer Programming

The current structure of Landmark University (LU) was induced by raising a generation of solution providers through a qualitative and life-applicable training system that focuses on values and creative knowledge by making it more responsive and relevant to the modern-day demands of demonstration, industrialization and development. The challenge facing Landmark University is the question of which of its numerous projects they should invest to give maximum output with minimum input. In this paper, we maximize the Net Present Value (NPV) and maintain the net discount cash overflow of each project per period as contained and extracted as the secondary data of cash inflows of the Landmark University (LU) monthly financial statement and annual reports from 2012 to 2017 of which the documents have been regrouped as small and large scale projects as many enterprises make more use of the trial-and-error method and as such firms have been finding it difficult in allocating scarce resources in a manner that will ensure profit maximization and/or cost minimization with a simple and accurate decision making by the company through an optimization principle in selecting LU project under multi-period capital rationing using linear programming (LP) and integer programming (IP). The annual net cash flow which is the difference between the cash inflows and cash outflows during each period for the project was estimated and recorded. The discount factors were estimated at cost of capital of 10% for each cash flow per period with the corresponding NPV at 10% which revealed that the optimal decision achieves maximum returns of $110 × 102 and this assisted the project manager to select a large number of the variable projects that can maximize the profit which is far better than relying on an ad-hoc judgmental approach to project investment that could have cost 160 × 102 for the same project. Sensitivity analysis on the project parameters are also carried out to test the extent to which project selection is sensitive to changes in the parameters of the system revealed that a little reduction and or addition of reduced cost by certain amount or percentages to its corresponding coefficient in the objective function effect no changes in the shadow prices with solution values for variables (x1), (x4), (x5) and the optimal objective function.

Multi-Document Summarization Model Based on Integer Linear Programming

This paper proposes an extractive generic text summarization model that generates summaries by selecting sentences according to their scores. Sentence scores are calculated using their extensive coverage of the main content of the text, and summaries are created by extracting the highest scored sentences from the original document. The model formalized as a multiobjective integer programming problem. An advantage of this model is that it can cover the main content of source (s) and provide less redundancy in the generated sum- maries. To extract sentences which form a summary with an extensive coverage of the main content of the text and less redundancy, have been used the similarity of sentences to the original document and the similarity between sentences. Performance evaluation is conducted by comparing summarization outputs with manual summaries of DUC2004 dataset. Experiments showed that the proposed approach outperforms the related methods.

A mixed integer linear programming approach for municipal solid waste management

ＡｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈｆｏｒｍｕｎｉｃｉｐａｌｓｏｌｉｄｗａｓｔｅｍａｎａｇｅｍｅｎｔＧｏｒｄｏｎＧｕｏＨｅＨｕａｎｇＥｎｖｉｒｏｎｍｅｎｔａｌＳｙｓｔｅｍｓＥｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒ...

Combining Geographic Information Systems for Transportation and Mixed Integer Linear Programming in Facility Location-Allocation Problems

In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.

Solving Integer Programming by Evolutionary Soft Agent

Many practical problems in commerce and industry involve finding the best way to allocate scarce resources a-mong competing activities. This paper focuses on the problem of integer programming, and describes an evolutionary soft a-gent model to solve it. In proposed model, agent is composed of three components: goal, environment and behavior. Experimental shows the model has the characters of parallel computing and goal driving.

Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks

Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.

耦合调峰与通航需求的梯级水电站群短期多目标优化调度的MILP方法

电网调峰任务与河道通航需求间的矛盾是水电航运梯级调度时所面临的突出问题,区间回水的顶托作用增大了该问题的复杂性。建立考虑回水影响的梯级水电站群短期多目标优化调度的混合整数线性规划模型,模型以剩余负荷平均距与下游尾水位平均距最小为目标,在将非线性约束通过函数聚合后,利用六面体栅格化技术与第二类特殊有序集约束方法实现该约束的线性化。利用法线边界交叉方法对模型进行求解。算例结果表明,所提方法可以充分计及回水顶托的影响,兼顾调峰与通航需求,高效求解多目标调度问题并获得较理想的结果。

The Linear Formulation of Thermal Unit Commitment Problem with Uncertainties through a Computational Mixed Integer

The solar and wind renewable energy is developing very rapidly to fulfill the energy gap. This specific increasing share of renewable energy is a reaction to the ecological trepidations to conciliate economics with security due to the new challenges in power system supply. In solar and wind renewable energy, the only partially predictable is the output with very low controllability which creates unit commitment problems in thermal units. In this research paper, a different linear formulation via mixed integer is presented that only requires “binary variables” and restraints concerning earlier stated models. The framework of this model allows precisely the costs of time-dependent startup & intertemporal limitations, for example, minimum up & down times and a ramping limit. To solve the unit commitment problem efficiently, a commercially available linear programming of mixed-integer is applied for sizeable practical scale. The results of the simulation are shown in conclusions.

分组密码复杂线性层可分性传播的MILP刻画方法

混合整数线性规划(MILP)作为一种自动化搜索工具,被广泛地应用于搜索分组密码的差分、线性、积分等密码性质.提出一种基于动态选取策略构建MILP模型的新技术,该技术在不同的条件下采用不同的约束不等式刻画密码性质的传播.具体地,从可分性出发根据输入可分性汉明重量的不同,分别采用不同的方法构建线性层可分性传播的MILP模型.最后,将该技术应用于搜索uBlock和Saturnin算法的积分区分器.实验结果表明:对于uBlock128算法,该技术可以搜索到比之前最优区分器多32个平衡比特的8轮积分区分器.除此之外,搜索到uBlock128和uBlock256算法比之前最优区分器更长一轮的9和10轮积分区分器.对于Saturnin256算法,同样搜索到比之前最优区分器更长一轮的9轮积分区分器.

SAILFISH-I、ASD算法基于MILP的积分分析

SAILFISH-I、ASD算法是近些年提出的基于Feistel和SPN结构的轻量级分组密码。根据密码的结构特点,分别构造了基于比特的混合整数线性规划(MILP)可分性质模型,并使用求解器Gurobi对MILP模型求解。本文首次得到SAILFISH-I算法的8、9、10轮积分区分器,ASD算法的7、8、9轮积分区分器。在SAILFISH-I的9轮积分区分器的基础上,向后扩展3轮,进行12轮积分攻击,攻击的数据复杂度约为2^(59.58)个选择明文,时间复杂度约为2^(109.99)次12轮加密,存储复杂度约为2^(57)个储存单元。在ASD的8轮积分区分器的基础上向后扩展2轮,进行10轮积分攻击,攻击的数据复杂度约为2^(57.39)个选择明文,时间复杂度约为2^(70.07)次10轮加密,存储复杂度约为2^(20)个储存单元。

Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New CuttingPlane Algorithm

Balas and Mazzola linearization (BML) is widely used in devising cutting plane algorithms for quadratic 0-1 programs. In this article, we improve BML by first strengthening the primal formulation of BML and then considering the dual formulation. Additionally, a new cutting plane algorithm is proposed.

A Hybrid Dynamic Programming Method for Concave Resource Allocation Problems

Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.

基于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算法的积分区分器攻击轮数,提高积分攻击效果。

基于多周期性MILP模型的新型配电系统拓扑辨识方法

在新兴低成本、非接触式的电流传感器的基础上,提出了基于多周期性混合整数线性优化的拓扑辨识方法。基于支路电流绝对值误差建立了拓扑辨识的混合整数非线性优化(MINLP)模型,采用线性化方法将MINLP模型转化为混合整数线性优化(MILP)模型,并通过多周期性测量数据建立多周期性优化模型,从而减小伪测量误差的影响。此外,证明了支路电流传感器优化配置条件,以确保拓扑辨识的准确性。在IEEE-33节点系统的仿真测试结果表明,所提出的拓扑辨识方法拓扑辨识精度高,随多周期性场景的增加,拓扑辨识精度逐渐增加,且受伪测量误差的影响比受支路电流测量误差更大。

Detection of gross errors using mixed integer optimization approach in process industry

A novel mixed integer linear programming (NMILP) model for detection of gross errors is presented in this paper. Yamamura et al.(1988) designed a model for detection of gross errors and data reconciliation based on Akaike information cri- terion (AIC). But much computational cost is needed due to its combinational nature. A mixed integer linear programming (MILP) approach was performed to reduce the computational cost and enhance the robustness. But it loses the super performance of maximum likelihood estimation. To reduce the computational cost and have the merit of maximum likelihood estimation, the simultaneous data reconciliation method in an MILP framework is decomposed and replaced by an NMILP subproblem and a quadratic programming (QP) or a least squares estimation (LSE) subproblem. Simulation result of an industrial case shows the high efficiency of the method.

基于MILP的应用服务器集群能耗与性能实时优化

在节能减排和激烈同行竞争的环境下,应用服务器集群的能耗与性能优化十分迫切.针对已有研究在性能指标和实时性方面的不足,提出一种集群能耗与性能实时优化方案.该方案结合采用线性加权法和主目标法优化集群功率与请求丢弃率这两个目标,将双目标优化转换成一个单目标约束优化.首先基于CPU频率等效连续调整模式下的服务器负载-功率模型,定义很少的变量将集群优化描述成混合整数二次规划问题,然后采用变量拆分和变量转换将其转化成混合整数线性规划(mixed integer linear programming,MILP)问题并引入特殊顺序集约束,最后采用Gurobi优化器求解该MILP.通过对CPU频率调整的进一步优化,大幅度减少了CPU频率的切换.多种场景下的测试表明,该方案的求解时间约在10 ms左右,特殊顺序集约束的引入使求解时间更为稳定,从而能够保证优化的实时进行.