EFFICIENT TREATMENT OF CONSTRAINTS IN LARGE-SCALE STRUCTURAL OPTIMIZATION

The paper presents a new concept for the treatment of large numbers of stress and displacement constraints in finite dimensional optimal structural design. The idea is to replace a large number of stress and displacement constraints by a small number of equivalent functional constraints. The genesis of this concept is the distributed parameter and transient response structural design formulations where it has been used quite effectively. The major advantage of this constraint formulation is that design sensitivity vectors need to be calculated for only the reduced number of equivalent stress and displacement constraints. Thus, there is substantial computational advantage with the new formulation. Implications of the formulation are studied and several example problems are presented to show its potential in practical design applications.     

带有二次约束二次规划问题的分枝定界方法

提出了一种解带有二次约束二次规划问题的新的分枝定界算法对该算法进行了收敛性分析。这种方法是用新的线性规划松弛定界技术确定最优值的下界，并且把分枝定界技术和外逼近方法有机地结合起来。     

A heuristic 0–1 integer programming method

Summary In this paper, we present a novel relaxation method for the integer programming problem:Ax=b,A {–1,0,+1}^m×N,x {0,1}^N, N>m. The report includes experimental results of problems with up tom=100 equations andN=400 variables.     

多核集群任务分配问题的0-1整数规划求解模型

研究了典型多核集群任务分配中的节点内通讯特性。基于0-1整数非线性规划模型和线性松弛技术,给出了一种0-1整数线性规划任务分配问题求解优化模型。由于节点内的通讯量与通讯延迟较大,以最小化计算代价和节点间通讯代价为研究目标的传统求解模型具有严重的局限性,而该求解模型考虑了节点内通讯代价,并采用了线性规划松弛技术,其目标是最小化计算代价、节点间通讯代价和节点内通讯代价。计算结果验证了提出的模型的有效性。     

单一尺寸长方体三维装箱问题的一种求解算法

目的研究单一尺寸长方体物品的三维装箱问题,即在一个给定的箱子中装入尽可能多的单一尺寸长方体物品。方法采用分层装载方案简化装载操作,首先运用动态规划技术确定所有层中长方体物品的排列方式;然后求解一维背包问题确定箱中层的最优组合,得到最优装载方案。将文中算法与文献中三维装箱算法进行对比。结果文中算法生成的装载方案箱体空间利用率由文献中三维装箱算法的98.10%提高到了99.14%。结论文中算法可以在合理的时间内得到装载操作简单、箱体空间利用率较高的装载方案。     

A pegging algorithm for separable continuous nonlinear knapsack problems with box constraints

This article proposes an efficient pegging algorithm for solving separable continuous nonlinear knapsack problems with box constraints. A well-known pegging algorithm for solving this problem is the Bitran–Hax algorithm, a preferred choice for large-scale problems. However, at each iteration, it must calculate an optimal dual variable and update all free primal variables, which is time consuming. The proposed algorithm checks the box constraints implicitly using the bounds on the Lagrange multiplier without explicitly calculating primal variables at each iteration as well as updating the dual solution in a more efficient manner. Results of computational experiments have shown that the proposed algorithm consistently outperforms the Bitran–Hax in all baseline testing and two real-time application models. The proposed algorithm shows significant potential for many other mathematical models in real-world applications with straightforward extensions.     

A Lagrangian heuristic for minimising risk using multiple heterogeneous metrology tools

Motivated by the high investment and operational metrology cost, and subsequently the limited metrology capacity, in modern semiconductor manufacturing facilities, we model and solve the problem of optimally assigning the capacity of several imperfect metrology tools to minimise the risk in terms of expected product loss on heterogeneous production machines. In this paper, metrology tools can differ in terms of reliability and speed. The resulting problem can be reduced to a variant of the Generalized Assignment Problem (GAP), the Multiple Choice, Multiple Knapsack Problem (MCMKP). A Lagrangian heuristic, including multiple feasibility heuristics, is proposed to solve the problem that are tested on randomly generated instances.     

0-1型二次规划的光滑函数法

本文针对工程设计、经济分析及计算机辅助设计等领域出现的0-1型二次规划问题,提出了Newton型的光滑迭代算法.首先利用NCP函数将0-1规划转化为不可微优化问题,然后通过构造不可微问题的光滑一致逼近,将组合优化问题转化成了可微的无约束优化问题,克服了已有算法收敛速度慢且计算结构复杂的缺点.文中给出了算法的迭代格式,证明了光滑函数的有关性质及其算法收敛性.通过理论分析及数值仿真证明了该算法对初始点不敏感,收敛速度快,且数值稳定,从而验证了模型和算法的可行性及有效性.     

A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization

The 0-1 quadratic knapsack problem (QKP) in wind farm layout optimization models possible turbine locations as nodes, and power loss due to wake effects between pairs of turbines as edges in a complete graph. The goal is to select up to a certain number of turbine locations such that the sum of selected node and edge coefficients is maximized. Finding the optimal solution to the QKP is difficult in general, but it is possible to obtain a tight upper bound on the QKP's optimal value which facilitates the use of heuristics to solve QKPs by giving a good estimate of the optimality gap of any feasible solution. This article applies an upper bound method that is especially well-suited to QKPs in wind farm layout optimization due to certain features of the formulation that reduce the computational complexity of calculating the upper bound. The usefulness of the upper bound was demonstrated by assessing the performance of the greedy algorithm for solving QKPs in wind farm layout optimization. The results show that the greedy algorithm produces good solutions within 4% of the optimal value for small to medium sized problems considered in this article.     

An investment plan for preventing child injuries using risk priority number of failure mode and effects analysis methodology and a multi-objective, multi-dimensional mixed 0-1 knapsack model

In this paper, a general framework for child injury prevention and a multi-objective, multi-dimensional mixed 0-1 knapsack model were developed to determine the optimal time to introduce preventive measures against child injuries. Furthermore, the model maximises the prevention of injuries with the highest risks for each age period by combining preventive measures and supervision as well as satisfying budget limits and supervision time constraints. The risk factors for each injury, variable, and time period were based on risk priority numbers (RPNs) obtained from failure mode and effects analysis (FMEA) methodology, and these risk factors were incorporated into the model as objective function parameters. A numerical experiment based on several different situations was conducted, revealing that the model provided optimal timing of preventive measures for child injuries based on variables considered.     

A 0-1 integer programming model and solving strategies for the slab storage problem

We consider the slab storage problem (SSP) in slab yard operations. A set of slabs enter a slab yard in a specific order. A proper stack needs to be selected for each inbound slab, so that the number of relocations in the subsequent retrieval stage is minimised. We present a 0-1 integer programming model of the SSP that minimises the lower bound of the number of relocations. Four solving strategies are derived from several interesting properties of the mathematical model to speed up the solving process of the model. Making use of randomly generated instances and practical instances, we testify the effectiveness of the solving strategies and study the influence of problem parameters on the computational time of the model. Computational results show that the solving strategies can effectively reduce the computational time of the model and is applicable in medium-sized practical instances.     

基于排队论和数学规划的资源配置优化方法

为解决零件加工系统资源优化配置问题,提出一种计算方法.针对零件加工系统的特点,总结出串联、循环、选择3种基本结构.在零件加工时间服从指数分布的假设下,根据排队论求出零件在系统中平均排队时间.优化目标是零件在系统中平均排队时间最短.在资源数量约束下,依次让各工序资源数量增一,使零件在系统中平均排队时间减少最大的工序首先分配资源.在资金约束情况下,通过0-1规划方法,列出目标函数和约束方程并求解.最后通过一个实例说明如何综合利用这两种方法进行资源优化配置.     

反渗透系统中膜元件位置优化的0-1整数规划算法

通过膜元件参数对系统产水含盐量的相关分析得出了相应的系统灵敏度参数,进而形成了反渗透系统膜元件优化排列的0-1整数规划模型.通过对整数规划的求解与膜元件全排列的系统模拟计算,验证了膜元件优化排列的数值优势与统计优势.     

An effective simultaneous approach with variable time nodes for dynamic optimization problems

An effective simultaneous approach with variable time nodes is proposed to solve the dynamic optimization problems with multiple control components, where the variable time nodes for each control component are considered as parameters directly and the interval between the neighbouring variable nodes is further refined uniformly to ensure accuracy. Consequently, the method does not treat all the nodes as parameters to ensure efficiency. The gradient formulae and the sensitivities of the states with respect to the controls and the variable time nodes are further derived to solve the nonlinear programming problem transformed from the original dynamic optimization problem. The complete framework and detailed steps of the proposed method are also given. Two classic constrained dynamic optimization problems have been tested as an illustration, and detailed comparisons of the reported literature methods are carried out. The research results show the characteristics and the effectiveness of the proposed approach.     

Cost optimization for series–parallel execution of a collection of intersecting operation sets

A collection of intersecting sets of operations is considered. These sets of operations are performed successively. The operations of each set are activated simultaneously. Operation durations can be modified. The cost of each operation decreases with the increase in operation duration. In contrast, the additional expenses for each set of operations are proportional to its time. The problem of selecting the durations of all operations that minimize the total cost under constraint on completion time for the whole collection of operation sets is studied. The mathematical model and method to solve this problem are presented. The proposed method is based on a combination of Lagrangian relaxation and dynamic programming. The results of numerical experiments that illustrate the performance of the proposed method are presented. This approach was used for optimization multi-spindle machines and machining lines, but the problem is common in engineering optimization and thus the techniques developed could be useful for other applications.     

虚拟企业管理中伙伴选择问题的数学模型

虚拟企业能够快速适应市场变化并能更有效地共享合作伙伴的资源,因此它正在成为越来越重要的组织管理单位。虚拟企业管理中的伙伴选择问题广泛出现在诸如企业动态结盟、任务指派、投资组合、敏捷制造和供应链管理等领域。本文建立了虚拟企业管理中伙伴选择问题的一个0-1规划数学模型。该模型涉及项目施工的先后次序和项目资金的动态支付,所建立的模型符合工程实际。它是进一步分析和解决伙伴选择问题的基础。     

追究根基的结构拓扑优化方法

结合作者在结构拓扑优化方面的研究工作,围绕了ICM(独立、连续、映射)方法涉及的基本概念上的突破,叙述了将本质上为0-1离散变量的拓扑优化问题转化为连续变量优化问题的具体做法,其中介绍了若干要点:以阶跃函数把离散问题化为连续问题即完成关键的等价性转换是第一步;定义磨光函数逼近阶跃函数的可操作的近似是第二步;引入作为磨光函数反函数的过滤函数实现映射性建模是第三步;采用某些光滑算法求解连续变量模型则是第四步。通过连续体结构的典型数值算例说明了将结构拓扑优化的模型转化为独立层次的拓扑优化过程。该方法对于纯数学的0-1离散变量优化的求解也适用,方法与数值都表明了这一点。