带性能约束的矩形图元布局优化模型及不干涉性算法

本文讨论了以航天卫星仪器舱布局优化设计为背景的、带性能约束的矩形图元布局优化模型及不干涉性判别算法,主要讨论了模型的性质,并将这一模型转化为带反凸约束的凸规划问题。应用文献(4)给出的最优性条件及定界锥分拆算法,可求得带性能约束的矩形图元布局优化问题的全局最优解。     

具有动应力、位移和稳定性约束的离散变量桁架结构布局优化设计算法

给出了在动应力、动位移和动稳定约束下离散变量结构布局优化设计问题的数学模型,用“拟静力”算法,将具有动应力约束、动位移约束和动稳定约束的离散变量结构布局优化设计问题化为静应力、静位移和静稳定约束的优化问题,然后利用两级优化算法求解该模型．优化过程由两级组成,拓扑级优化和形状级优化．在每一级,都使用了综合算法,并且在搜索过程中都根据两类设计变量的相对差商值进行搜索．对包含稳定约束和不包含稳定约束的优化结果做了比较,结果显示稳定性约束对优化结果产生较大的影响．     

全局精确罚函数的一个充要条件

本文讨论有约束最优化问题全局解和相应的精确罚函数全局解之间的等价性，给出一个有限有效罚的准则，并证明这一准则是上述等价性的一个充要条件．在这个准则中不包含任何约束品性，这是最弱的条件之一     

判别线性约束下实二次型正定性的一个算法

本文对经济学中常见的判别线性约束下实二次型的正定性问题通过矩阵分解给出了一个简易且可行的算法，该算法不涉及行列式的计算。     

战斗对策:有约束极小极大途径(I)

本文把战斗对策归结为有约束极小极大问题，讨论解的存在性．引进不连续罚函数后，把有约束问题化为无约束极小极大问题。     

线性约束下的共轭投影梯度法及其超线性收敛性

本文考虑线性约束非线性规划问题，提出了一类共轭投影梯度法，证明了算法的全局收敛性，并对算法的二次终止性，超线性收敛特征进行了分析，算法的优点是（１）采用计算机上实现的Ａｒｍｉｊｏ线性搜索规则，（２）初始点不要求一定是可行点，可以不满足线性等式约束，（３）具有较快的收敛速度。     

刚性约束转子系统单点碰摩周期n运动的存在性

对一类刚性约束转子系统的碰摩映射讨论了单点碰摩周期2运动的存在性，给出其存在的参数范围和计算公式，并用实例验证本方法的正确性，最后研究了单点碰摩周期n运动的不存在性。     

某类等式约束二次规划问题的一个共轭方向法

本文提出了一种求解某类等式约束二次规划问题的一个共轭方向迭代法，并给出了算法的有限终止性证明．同时我们把此算法推广到不等式约束二次规划问题中，从而得到了一种求解不等式约束二次规划问题的算法．     

转动圆桌平衡摆盘——带平衡性能约束的Packing问题

转动圆桌平衡摆盘问题属带平衡性能约束的装填(Packing)布局优化问题,提出了其数学模型和启发式算法,包括模式迭换法和主布模法,用以构造布局拓扑模式,形成初始布局;推荐了在此初始布局下的寻优方法及技巧,以及给出了缓解组合爆炸的技巧,算法经算例验证。     

带性能约束布局问题的全局优化算法

以人造卫星仪器舱布局为例,应用图论,群对集合的作用,轨道与等价关系等刻划各种布局方案的同构,等价类等内在性质,从而首次给出带有性能约束二维布局问题的一个全局优化算法。     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.     

A MIP-based slicing heuristic for three-dimensional bin packing

The mixed-case palletization problem is a common problem in warehousing and logistics where boxes of rectangular shapes are stacked on top of each other to form pallets. The problem shares common features with three-dimensional bin packing but requires boxes to be adequately supported. We propose a mixed integer programming formulation that maximizes the density of the bottom layers and the compactness of the pallet to ensure stability for top layers. We use a relative-position formulation with slicing that minimizes height, maximizes the fill rate of slices, and pushes boxes towards the vertical axis in order to consolidate fragmented space. Apart from common non-overlap and dimension-related constraints, we explicitly model the fill rates and force lower slices to have an equal or higher density than upper slices. As expected, the formulation could only handle small instances. To tackle larger instances, we embedded the formulation in an iterative approach that packs subsets of boxes sequentially. The approach was found to provide stable pallets and to outperform the branch-and-bound approach of Martello et al. (Oper Res 48(2):256–267, 2000).     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

Single machine scheduling with symmetric earliness and tardiness penalties

This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.     

The global optimal solution to the three-dimensional layout optimization model with behavioral constraints

In this paper we study the problem of three-dimensional layout optimization on the simplified rotating vessel of satellite. The layout optimization model with behavioral constraints is established and some effective and convenient conditions of performance optimization are presented. Moreover, we prove that the performance objective function is locally Lipschitz continuous and the results on the relations between the local optimal solution and the global optimal solution are derived.     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.     

The capacitated single-allocation hub location problem revisited: A note on a classical formulation

In this paper a well-known formulation for the capacitated single-allocation hub location problem is revisited. An example is presented showing that for some instances this formulation is incomplete. The reasons for the incompleteness are identified leading to the inclusion of an additional set of constraints. Computational experiments are performed showing that the new constraints also help to decrease the computational time required to solve the problem optimally.     

The layout problem of two kinds of graph elements with performance constraints and its optimality conditions

This paper presents an optimization model with performance constraints for two kinds of graph elements layout problem. The layout problem is partitioned into finite subproblems by using graph theory and group theory, such that each subproblem overcomes its on-off nature about optimal variable. Furthermore each subproblem is relaxed and the continuity about optimal variable doesn’t change. We construct a min-max problem which is locally equivalent to the relaxed subproblem and develop the first order necessary and sufficient conditions for the relaxed subproblem by virtue of the min-max problem and the theories of convex analysis and nonsmooth optimization. The global optimal solution can be obtained through the first order optimality conditions.     

Applying the sequence-pair representation to optimal facility layout designs

We present a new formulation for the facility layout problem based on the sequence-pair representation, which is used successfully in VLSI design. By tightening the structure of the problem with this formulation, we have extended the solvable solution space from problems with nine departments to problems with eleven departments.     

The offshore wind farm array cable layout problem: a planar open vehicle routing problem

In an offshore wind farm (OWF), the turbines are connected to a transformer by cable routes that cannot cross each other. Finding the minimum cost array cable layout thus amounts to a vehicle routing problem with the additional constraints that the routes must be embedded in the plane. For this problem, both exact and heuristic methods are of interest. We optimize cable layouts for real-world OWFs by a hop-indexed integer programming formulation, and develop a heuristic for computing layouts based on the Clarke and Wright savings heuristic for vehicle routing. Our heuristic computes layouts on average only 2% more expensive than the optimal layout. Finally, we present two problem extensions arising from real-world OWF cable layouts, and adapt the integer programming formulation to one of them. The thus obtained optimal layouts are up to 13% cheaper than the actually installed layouts.