求解MINLP的几类罚函数方法的分析和探讨

针对混合整数非线性约束优化问题(MINLP)的一般形式,通过罚函数的方法,给出了它的几种等价形式,并证明了最优解的等价性.将约束优化问题转化成更容易求解的无约束非线性优化问题,并把混合整数规划转化成非整数优化问题,从而将MINLP的求解简化为求解一个连续的无约束非线性优化问题,进而可用已有的一般无约束优化算法进行求解.     

0-1非线性混合整数规划的罚函数解法

本文中我们对一类0-1非线性混合整数规划的解法进行了探讨,通过罚函数把有约束问题化为相应的无约束问题,我们证明了可通过求解一个无约束非线性规划问题得到原问题的ε近似极小解,数值试验表明算法是有效的.     

二维矩形件排样的切割式填充算法

针对二维矩形件排样困难的问题,提出了一种简单且高效的切割式填充矩形件排样算法.首先根据对矩形件进行优化排样的要求,建立起数学规划模型.然后采用降维的思想,对矩形行列虚拟化分割.在第一行(列)上进行矩形件排样,使其填充率最高.接着将此行(列)切割掉,形成新的矩形.最后重复上述步骤,直到矩形无法再填充下任何一种规格的矩形件为止.数值实验表明了切割式填充算法的可行性和高效性.     

有限维逼近无限维总极值的积分型方法

本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题．我们给出了新的最优性条件和用变测度方法求得的有限维解逼近总体最优解的算法．对于有约柬问题，我们用不连续罚函数法把有约束问题化为无约束问题来求解．最后，我们通过一个具有非凸状态约束的最优控制问可题的实例来说明算法的有效性．     

基于拟态物理学的约束多目标共轭梯度混合算法

在拟态物理学优化算法APO的基础上,将一种基于序值的无约束多目标算法RMOAPO的思想引入到约束多目标优化领域中.提出一种基于拟态物理学的约束多目标共轭梯度混合算法CGRMOAPA.算法采取外点罚函数法作为约束问题处理技术,并借鉴聚集函数法的思想,将约束多目标优化问题转化为单目标无约束优化问题,最终利用共轭梯度法进行求解.通过与CRMOAPO、MOGA、NSGA-II的实验对比,表明了算法CGRMOAPA具有较好的分布性能,也为约束多目标优化问题的求解提供了一种新的思路.     

求多目标优化问题Pareto最优解集的方法

主要讨论了无约束多目标优化问题Pareto最优解集的求解方法,其中问题的目标函数是C1连续函数.给出了Pareto最优解集的一个充要条件,定义了α强有效解,并结合区间分析的方法,建立了求解无约束多目标优化问题Pareto最优解集的区间算法,理论分析和数值结果均表明该算法是可靠和有效的.     

基于混合单亲遗传算法的车辆运输问题求解

本文运用混合单亲遗传算法(Hybrid Partheno Genetic Algorithm,)求解车辆运输问题.我们用罚函数法将约束优化问题转化为无约束优化问题,HPGA采用序号编码的方式进行运算.生成初始种群时,在拟染色体中插入车辆序号,尽可能生成符合约束的子路径,由子路径拼接成完整的运输路径,降低罚函数的计算量;选择操作中内嵌最优保存策略,保证算法全局收敛;取消双亲交叉操作,每条染色体上独立改变基因产生新的个体,避免发生早熟早收敛现象;提出邻域搜索,使得GA能对某些指定区域进行重点搜索,加快算法在最优解附近的寻优速度;以CVRP作为HPGA的测试模型,采用Christofides和Eilon提出的标准VRP测试算例进行数值实验,和其他算法进行对比分析,验证了HPGA计算量少、收敛速度快和不会产生早熟早收敛现象.     

改进填充算法在矩形件排样中的应用

矩形件排样的合理性直接影响板材利用率.考虑到下料过程中板材的纤维方向和"一刀切"等工艺约束,建立了以板材平均利用率最大为目标的数学模型.提出了一种改进填充算法,增加了矩形件的排列方式、扩大了矩形件试排范围,实现了排样的多样性.此外,在改进填充算法的基础上引入了遗传算子,利用遗传算法全局搜索能力强的特点,对矩形件排样顺序进行寻优.最后,采用不同规模的算例验证所建模型和所提算法的合理性与普适性,算例结果表明改进后的算法能够有效提高板材的利用率,可为实际作业提供技术支持及方法借鉴.     

球约束凸二次规划的一个新算法

首先利用Lagrange对偶 ,将球约束凸二次规划问题转化为无约束优化问题 ,然后运用单纯形法求解无约束优化问题 ,从而获得原问题的最优解     

关于非线性等式约束优化问题的一点注记

给出了一种求解非线性约束优化问题的算法.利用Lagrange函数,将非线性约束优化问题转化为无约束优化问题,从而得到解决.方法仅仅依靠求解一个线性方程组来求解,因此使得计算量减小,计算速度变快.在一定条件下,给出算法的收敛性证明.数值试验表明方法是有效的.     

Dynamic Programming Algorithms for Generating Optimal Strip Layouts

This paper presents dynamic programming algorithms for generating optimal strip layouts of equal blanks processed by shearing and punching. The shearing and punching process includes two stages. The sheet is cut into strips using orthogonal guillotine cuts at the first stage. The blanks are punched from the strips at the second stage. The algorithms are applicable in solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths not longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. Experimental computations show that the algorithms are efficient.     

A meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

A comparative numerical analysis for the guillotine two-dimensional cutting problem

In this work, the behavior of four algorithms in the resolution of the two-dimensional constrained guillotine cutting problem is analyzed. This problem is concerned about the way a set of pieces should be cut from a plate of greater dimensions, considering guillotine cutting and a constrained number of times a piece can be cut from the plate. In this study three combinatorial and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively generated based on Wang's algorithm. In addition, an evolutionary and an annealing type approach are considered. All of these models have been implemented on a high performance Silicon Graphics machine. Performance of each algorithm is analyzed both in terms of percentage waste and running time. In order to do that, a set of 1000 instances are classified according to their combinatorial degree and subsequently evaluated. This revised version was published online in June 2006 with corrections to the Cover Date.     

一类概率约束规划逼近最优解集的上半收敛性

对一类概率约束规划逼近最优解集的上半收敛性进行了研究.利用概率测度弱收敛的特征,给出了概率约束规划可行集的收敛性条件,得到了概率约束规划逼近最优解集的上半收敛性.     

Dynamic programming algorithms for the optimal cutting of equal rectangles

This paper presents dynamic programming algorithms for generating optimal guillotine-cutting patterns of equal rectangles. The algorithms are applicable for solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. The algorithms are able to generate the simplest optimal patterns to simplify the cutting process. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths no longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. The computational results indicate that the algorithms presented are more efficient than the branch-and-bound algorithms, which are the best algorithms so far that can guarantee the simplest patterns.     

An Improved Algorithm for the Non-Guillotine-Constrained Cutting-Stock Problem

A personal-computer-based algorithm to solve the non-guillotine-constrained two-dimensional cutting-stock problem is developed. The problem is constrained to single-sized rectangles placed orthogonally on a larger containing rectangle. The algorithm uses the linear combination of box lengths and widths that minimizes waste along the cutting stock's length and width to determine an optimal layout. The algorithm's performance is evaluated using two sets of test cases and compared to the results of other algorithms.     

概率约束规划逼近最优解集的上半收敛性

本文讨论了概率约束规划目标函数的连续收敛性,并利用概率测度弱收敛的特征给出了概率约束规划可行集的收敛性条件,得到了概率约束规划逼近最优解集的上半收敛性.     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Hybrid functions approach for nonlinear constrained optimal control problems

In this paper, a new numerical method for solving the nonlinear constrained optimal control with quadratic performance index is presented. The method is based upon hybrid functions approximation. The properties of hybrid functions consisting of block-pulse functions and Bernoulli polynomials are presented. The operational matrix of integration is introduced. This matrix is then utilized to reduce the solution of the nonlinear constrained optimal control to a nonlinear programming one to which existing well-developed algorithms may be applied. Illustrative examples are included to demonstrate the validity and applicability of the technique.     

On Smoothing l1 Exact Penalty Function for Constrained Optimization Problems

This article introduces a smoothing technique to the l₁ exact penalty function. An application of the technique yields a twice continuously differentiable penalty function and a smoothed penalty problem. Under some mild conditions, the optimal solution to the smoothed penalty problem becomes an approximate optimal solution to the original constrained optimization problem. Based on the smoothed penalty problem, we propose an algorithm to solve the constrained optimization problem. Every limit point of the sequence generated by the algorithm is an optimal solution. Several numerical examples are presented to illustrate the performance of the proposed algorithm.