Optimizing thermal design of data center cabinets with a new multi-objective genetic algorithm

There is an ever increasing need to use optimization methods for thermal design of data centers and the hardware populating them. Airflow simulations of cabinets and data centers are computationally intensive and this problem is exacerbated when the simulation model is integrated with a design optimization method. Generally speaking, thermal design of data center hardware can be posed as a constrained multi-objective optimization problem. A popular approach for solving this kind of problem is to use Multi-Objective Genetic Algorithms (MOGAs). However, the large number of simulation evaluations needed for MOGAs has been preventing their applications to realistic engineering design problems. In this paper, details of a substantially more efficient MOGA are formulated and demonstrated through a thermal analysis simulation model of a data center cabinet. First, a reduced-order model of the cabinet problem is constructed using the Proper Orthogonal Decomposition (POD). The POD model is then used to form the objective and constraint functions of an optimization model. Next, this optimization model is integrated with the new MOGA. The new MOGA uses a “kriging” guided operation in addition to conventional genetic algorithm operations to search the design space for global optimal design solutions. This approach for optimal design is essential to handle complex multi-objective situations, where the optimal solutions may be non-obvious from simple analyses or intuition. It is shown that in optimizing the data center cabinet problem, the new MOGA outperforms a conventional MOGA by estimating the Pareto front using 50% fewer simulation calls, which makes its use very promising for complex thermal design problems. Recommended by: Monem Beitelmal     

多目标遗传算法及在过程优化综合中的应用

化工过程的多目标优化综合问题可归结为多目标混合整数非线性规划(MOMINLP)模型的求解,求解方法主要有数学规划法和多目标进化算法。以多目标遗传算法(MOGA)为代表的进化算法被认为是特别适合求解此类问题。遗传算法大多用于单目标问题的优化,近十几年来将遗传算法应用到多目标优化的研究得到了很大的发展。本文对多目标遗传算法的一些重要概念、发展历程进行了回顾。针对化工过程的模型特点,对MOGA在过程综合中的应用研究进行了讨论,并认为混合遗传算法应是求解此类问题的有效算法。     

一类混杂系统建模和优化控制的研究

为解决混杂系统优化控制的计算复杂性问题,针对结合逻辑规则的工业过程混杂模型,采用结合约束程序的混合整数非线性规划算法,求解这种混杂模型的优化控制。计算实例表明,通过混杂建模方法,可以充分利用工业对象的机理模型以及操作工经验或专家经验,建立系统的更精确模型;结合约束程序混合整数非线性规划算法可以较迅速地求解混杂模型优化控制问题,从而使该方法可以用于工业过程实时控制中。     

基于混合搜索的含逻辑“与”“或”的RM优化算法

相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.     

求解Web集群文档分布的混沌搜索算法

提出Web集群文档分布方案,用M/G/1/K PS排队模型对服务器进行建模,将文档分布问题转化为0-1整数规划问题,然后求解该规划问题。针对该类0-1整数规划问题,给出一种基于混沌搜索的求解算法,该算法让多个独立的混沌变量在其各自的轨道中搜索,使得对应生成的0-1矩阵能遍历任意一种可能的分布,从而能搜索到全局最优解。设计一种基于贪婪思想的文档分布算法。测试表明,混沌搜索算法能找到全局最优解,优于传统的贪婪算法。     

用鱼群算法求解通风系统风机定位优化问题

为了解决矿井通风系统风机定位优化问题,建立了该问题的大规模非线性最优规划模型。在优化模型中,在兼顾变量约束条件的空间限制和求解精度的情况下,在正交交叉算子中将求解空间离散化,离散方法是将每个连续因素离散化为一个有限值,量化每个变量连续空间区域为有限个水平。由于该问题维数太高,传统优化技术无法有效获取其最优解,采用改进的鱼群算法对该问题进行了求解。在算法中,为了消除优化模型的约束条件,大幅度压缩变量数,在算子中将变量分组;使用了基于邻域竞争进化的演化算法,有效地融合了全局搜索和局部搜索的本质属性,实现了算法效率与效果的平衡;使用了自适应学习和变异算子、正交交叉算子、邻域竞争算子等多种算子改进基本人工鱼群算法的各种行为。应用结果表明,该算法计算速度和稳定性大幅度提高,可在简单计算环境下稳定地获取该模型的最优解。     

OPTIMAL FEEDER RECONFIGURATION FOR LOSS REDUCTION BY ROBUST SEARCHING HYBRID DIFFERENTIAL EVOLUTION

This paper introduces a robust searching hybrid differential evolution (RSHDE) method to solve the optimal feeder reconfiguration for power loss reduction. The feeder reconfiguration of distribution systems is to recognize beneficially load transfers so that the objective function composed of power losses is minimized and the prescribed voltage limits are satisfied. Mathematically, the problem of this research is a nonlinear programming problem with integer variables. This paper presents a new approach, which uses the RSHDE algorithm with integer variables to solve the problem. Owing to handle the integer variables, the HDE may fail to find the initial search direction for large-scale integer system. This is because the HDE applies a random search at its initial stages. Therefore, two new schemes, the multidirection search scheme and the search space reduction scheme, are embeded into the HDE. These two schemes are used to enhance the search ability before performing the initialization step of the solution process. One three-feeder distribution system from the literature and one practical distribution network of Taiwan Power Company (TPC) are used to exemplify the performance of the proposed method. Moreover, the previous HDE, simulated annealing (SA) and genetic algorithms (GA) methods are also applied to the same example systems for the purpose of comparison. Numerical results show that the proposed method is better than the other methods.     

求解整数线性规划的一种高效隐数搜寻

提出了一种求解整数线性规划的新的隐数算法。首先,该算法引入了一组线性变换,将线性松弛问题的最优非基变量变换到一组新变量,使新变量有更小的取值范围。然后,在目标函数超平面上对非基变量和新变量进行隐数计算,从而大大提高了隐数搜寻的效率。     

The reduced cost branch and bound algorithm for mixed integer programming

A different branch and bound algorithm for mixed integer programming is presented. Unlike standard linear programming based branch and bound algorithms, where a single fractional variable (or Special Ordered Set) is selected for problem separation, the proposed method selects groups of variables for separation on the basis of their reduced cost in an LP relaxation. The proposed method restricts a large portion of the integer variables to zero on one branch. The net effect is that the original integer program is solved by optimizing a series of smaller, more tightly restricted, integer programs. The authors have programmed the algorithm using the Extended Control Language of the IBM MPSX/370-MIP/370 mixed integer programming package. Computational results are presented that demonstrate the efficiency of the method on problems where the $\text{0}\text{1}$ variables are partitioned into multiple choice constraints containing special ordered sets of variables. While the computational results are limited to this class of problems the algorithm can, in theory, be applied to any mixed integer programming problem.     

Entropy-based multi-objective genetic algorithm for design optimization

Obtaining a fullest possible representation of solutions to a multiobjective optimization problem has been a major concern in Multi-Objective Genetic Algorithms (MOGAs). This is because a MOGA, due to its very nature, can only produce a discrete representation of Pareto solutions to a multiobjective optimization problem that usually tend to group into clusters. This paper presents a new MOGA, one that aims at obtaining the Pareto solutions with maximum possible coverage and uniformity along the Pareto frontier. The new method, called an Entropy-based MOGA (or E-MOGA), is based on an application of concepts from the statistical theory of gases to a baseline MOGA. Two demonstration examples, the design of a two-bar truss and a speed reducer, are used to demonstrate the effectiveness of E-MOGA in comparison to the baseline MOGA.     

A hybrid method for the Probabilistic Maximal Covering Location–Allocation Problem

This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.     

混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.     

A hybrid metaheuristic approach for the capacitated p-median problem

The capacitated p-median problem (CPMP) seeks to obtain the optimal location of p medians considering distances and capacities for the services to be given by each median. This paper presents an efficient hybrid metaheuristic algorithm by combining a proposed cutting-plane neighborhood structure and a tabu search metaheuristic for the CPMP. In the proposed neighborhood structure to move from the current solution to a neighbor solution, an open median is selected and closed. Then, a linear programming (LP) model is generated by relaxing binary constraints and adding new constraints. The generated LP solution is improved using cutting-plane inequalities. The solution of this strong LP is considered as a new neighbor solution. In order to select an open median to be closed, several strategies are proposed. The neighborhood structure is combined with a tabu search algorithm in the proposed approach. The parameters of the proposed hybrid algorithm are tuned using design of experiments approach. The proposed algorithm is tested on several sets of benchmark instances. The statistical analysis shows efficiency and effectiveness of the hybrid algorithm in comparison with the best approach found in the literature.     

超导MRI主磁体优化设计的模拟退火算法

在进行MRI(magneticresonanceimaging)超导主磁体的设计时常采用优化设计的方法,将各设计参数看作连续变量处理,但实际上很多参数是离散变量,为了更符合工程实际,将超导MRI主磁体的设计作为一个含有离散变量的全局优化问题。建立了适用于多种超导MRI主磁体结构的数学模型,包括设计变量、目标函数、约束条件等,选用了适用于MRI超导主磁体优化设计的含有离散变量的模拟退火算法进行设计。算例结果表明,本文选取的数学模型和优化算法是有效的,能够达到超导MRI主磁体设计的要求。     

Logic-based solution methods for optimal control of hybrid systems

Combinatorial optimization over continuous and integer variables is a useful tool for solving complex optimal control problems of hybrid dynamical systems formulated in discrete-time. Current approaches are based on mixed-integer linear (or quadratic) programming (MIP), which provides the solution after solving a sequence of relaxed linear (or quadratic) programs. MIP formulations require the translation of the discrete/logic part of the hybrid problem into mixed-integer inequalities. Although this operation can be done automatically, most of the original symbolic structure of the problem (e.g., transition functions of finite state machines, logic constraints, symbolic variables, etc.) is lost during the conversion, with a consequent loss of computational performance. In this paper, we attempt to overcome such a difficulty by combining numerical techniques for solving convex programming problems with symbolic techniques for solving constraint satisfaction problems (CSP). The resulting "hybrid" solver proposed here takes advantage of CSP solvers for dealing with satisfiability of logic constraints very efficiently. We propose a suitable model of the hybrid dynamics and a class of optimal control problems that embrace both symbolic and continuous variables/functions, and that are tailored to the use of the new hybrid solver. The superiority in terms of computational performance with respect to commercial MIP solvers is shown on a centralized supply chain management problem with uncertain forecast demand.     

Multi-objective scheduling and a resource allocation problem in hospitals

This study addresses the issue of scheduling medical treatments for resident patients in a hospital. Schedules are made daily according to the restrictions on medical equipment and physicians who are being assigned at the same time. The problem is formulated as a multi-objective binary integer programming (BIP) model. Three types of metaheuristics are proposed and implemented to deal with the discrete search space, numerous variables, constraints and multiple objectives: a variable neighborhood search (VNS)-based method, scatter search (SS)-based methods and a non-dominated sorting genetic algorithm (NSGA-II). This paper also provides the results of computational experiments and compares their ability to find efficient solutions to the multi-objective scheduling problem.     

An integer programming formulation for the project scheduling problem with irregular time-cost tradeoffs

Four integer programming formulations are studied for the irregular costs project scheduling problem with time/cost trade-offs (PSIC). Three formulations using standard assignment type variables are tested against a more novel integer programming formulation. Empirical tests show that in many instances the new formulation performs best and can solve problems with up to 90 activities in a reasonable amount of time. This is explained by a reduced number of binary variables, a tighter linear programming (LP) relaxation, and the sparsity and embedded network structure of the constraint matrix of the new formulation.     

Searching for optimal integer solutions to set partitioning problems using column generation

In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation.     

Convex dynamic programming for hybrid systems

A classical linear programming approach to optimization of flow or transportation in a discrete graph is extended to hybrid systems. The problem is finite dimensional if the state space is discrete and finite, but becomes infinite dimensional for a continuous or hybrid state space. It is shown how strict lower bounds on the optimal loss function can be computed by gridding the continuous state space and restricting the linear program to a finite-dimensional subspace. Upper bounds can be obtained by evaluation of the corresponding control laws.     

An interactive approach based on a discrete differential evolution algorithm for a class of integer bilevel programming problems

This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn–Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.