The Cross-Entropy Method for Continuous Multi-Extremal Optimization

In recent years, the cross-entropy method has been successfully applied to a wide range of discrete optimization tasks. In this paper we consider the cross-entropy method in the context of continuous optimization. We demonstrate the effectiveness of the cross-entropy method for solving difficult continuous multi-extremal optimization problems, including those with non-linear constraints.      

Exact Max-SAT solvers for over-constrained problems

We present a new generic problem solving approach for over-constrained problems based on Max-SAT. We first define a Boolean clausal form formalism, called soft CNF formulas, that deals with blocks of clauses instead of individual clauses, and that allows one to declare each block either as hard (i.e., must be satisfied by any solution) or soft (i.e., can be violated by some solution). We then present two Max-SAT solvers that find a truth assignment that satisfies all the hard blocks of clauses and the maximum number of soft blocks of clauses. Our solvers are branch and bound algorithms equipped with original lazy data structures, powerful inference techniques, good quality lower bounds, and original variable selection heuristics. Finally, we report an experimental investigation on a representative sample of instances (random 2-SAT, Max-CSP, graph coloring, pigeon hole and quasigroup completion) which provides experimental evidence that our approach is very competitive compared with the state-of-the-art approaches developed in the CSP and SAT communities. Research partially supported by projects TIN2004-07933-C03-03 and TIC2003-00950 funded by the Ministerio de Educación y Ciencia. The second author is supported by a grant Ramón y Cajal.     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous computers in an office environment, thus, drastically reducing the time required to find the solution.     

����Լ���������������MinimaxԤ��

本文研究了独立随机变量之和的绝对矩的几个性质, 其中包括$\ep|X+Y|-\ep|X-Y|$的表达式, 这里$X$和$Y$是相互独立的随机变量.     

超线性与二次收敛序列线性方程组算法

本文,在无严格互补条件下,对非线性不等式约束最优化问题提出了一个新的序列线性方程组(简称SSLE)算法．算法有两个重要特征:首先,每次迭代,只须求解一个线性方程组或一个广义梯度投影阵,且线性方程组可以无解．其次,初始点可以任意选取．在无严格互补条件下,算法仍有全局收敛性、强收敛性、超线性收敛性及二次收敛性．文章的最后,还对算法进行了初步的数值实验．     

动态环境约束下企业的资本积累

本文讨论动态环境约束下企业的动态投资行为,拓广了文献[4]的结果.为了使讨论的问题更符合实际情况,本文假设政府设定的污染排放上限是与企业的规模大小有关,即假设污染排放上限是生产资本的函数,讨论动态环境约束下企业的最佳动态投资行为,并为政府制定污染排放政策提供依据.     

多周期多种设备公用工程系统优化模型的改进及应用

本文提出了多周期多种设备公用工程系统改进的混合整数双线性优化模型,它含有两种优化变量和系统运行过程的离散动态约束,期望系统总设备投资(含设备折旧)与全周期运行操作费用之和最小。针对改进优化模型求解上的困难,给出将改进优化模型分解成有限多个关于连续变量的线性规划。论述了改进优化模型与分解模型的等价性以及两种模型的主要数学性质,并在此基础上提出了求解策略。最后将改进优化模型应用于某石化企业的蒸汽动力系统最优设计与运行优化集成实例。     

Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CF of constraints critical to feasibility.     

城镇居民非参数消费敏感度模型及应用——基于局部线性工具变量估计方法

建立了城镇居民非参数消费敏感度模型,该模型不需做任何形式假设,避免了线性及非线性模型的误设.采用局部线性工具变量方法对其进行估计,结果表明城镇居民消费敏感度是时变的,和居民收入变动保持同步,支持流动性约束假说.另外高通货膨胀时的负实际利率变动比低利率、温和通胀时造成的负实际利率变动对消费支出的冲击要大得多.因此在增加城镇居民收入,突破流动性约束瓶颈的同时,高度关注通货膨胀,使得其消费水平得到真实提高.     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.