基于改进遗传算法的布局优化子问题

本针对子问题，构造了布局子问题(关于同构布局等价类)的改进遗传算法。将该算法应用于二维布局优化子问题，数值实验表明该算法能够在很好地保持图元的邻接关系的前提下找到子问题的最优解。由于布局优化问题可分解为有限个子问题，所以利用该算法可以找到整个布局优化问题的全局最优解。     

Solvability of the vector problem by the linear criteria convolution algorithm

Conditions are found under which a multicriteria problem with a finite set of vector estimates is solvable by means of the linear criteria convolution (LCC) algorithm, that is, any Pareto optimum for the problem can be obtained as an optimum solution to a one-criterion problem with an aggregated criterion defined as an LCC. Also, an algorithm is suggested that is polynomial in dimension and reduces any problem with minimax and minimin criteria to an equivalent vector problem with the same Pareto set solvable by the LCC algorithm. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 502–509, October, 1997. Translated by V. N. Dubrovsky     

Optimum control laws in a non-autonomous dynamic model of a gas field

A model of gas field development described as a nonlinear optimum control problem with an infinite planning horizon is considered. The Pontryagin maximum principle is used to solve it. The theorem on sufficient optimumity conditions in terms of constructions of the Pontryagin maximum principles is used to substantiate the optimumity of the extremal solution. A procedure for constructing the optimum solution by dynamic programming is described and is of some methodological interest. The obtained optimum solution is used to construct the Bellman function. Reference is made to a work containing an economic interpretation of the problem.     

流体流动中波状游动平板最优运动的数值方法

提出了一种求解波状游动平板最优运动方式的优化方法．最优化问题表述为固定推力的条件下,使得输入功率最小．由于存在不可见模态,使得该问题具有奇性,用通常的Lagrange乘子法计算得到的可能不是最优解,而是一个鞍点值．为了消除这一奇性,增加了一个关于幅值的不等式约束,并利用逐步二次规划的优化方法求解该问题．将该方法运用到二维和三维的波动板的几个例子上,获得了最优解．     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

Solving nonlinear bilevel programming models of the equilibrium network design problem: A comparative review

Nonlinear bilevel programming problems, of which the equilibrium network design problem is one, are extremely difficult to solve. Even if an optimum solution is obtained, there is no sure way of knowing whether the solution is the global optimum or not, due to the nonconvexity of the bilevel programming problem. This paper reviews and discusses recent developments in solution methodologies for nonlinear programming models of the equilibrium network design problem. In particular, it provides a primer for descent-type algorithms reported in the technical literature and proposes certain enhancements thereof.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

A central cutting plane algorithm for the convex programming problem

An algorithm is developed for solving the convex programming problem which iteratively proceeds to the optimum by constructing a cutting plane through the center of a polyhedral approximation to the optimum. This generates a sequence of primal feasible points whose limit points satisfy the Kuhn—Tucker conditions of the problem. Additionally, we present a simple, effective rule for dropping prior cuts, an easily calculated bound on the objective function, and a rate of convergence.     

Optimization of Batch Reactions in Series with Uncertainty

Certain types of chemical reactions, such as the global deprotection of a polypeptide, are extremely complex. As a result, it may be very difficult or expensive to develop accurate models of these chemical reactions. Without a satisfactory kinetic model for the reaction, it is difficult to develop an optimum operating policy that will maximize the profit. Stochastic optimization is applied in this work to an example process step to obtain the optimum reaction temperature and reaction time. In the case of the “here and now” problem, the optimal conditions are a lower reaction temperature and a longer reaction time than obtained from the deterministic problem. The average reaction time for the “wait and see” problem is also longer than the deterministic case, but the average reaction temperature is very close to that of the deterministic problem. Both normally and uniformly – distributed uncertain parameters are considered.     

An Optimal Chance Constraint Multivariate Stratified Sampling Design Using Auxiliary Information

When we are dealing with multivariate problem then we need an allocation which is optimal for all the characteristics in some sense because the individual optimum allocations usually differ widely unless the characteristics are highly correlated. So an allocation called “Compromise allocation” is to be worked out suggested by Cochran. When auxiliary information is also available, it is customary to use it to increase the precision of the estimates. Moreover, for practical implementation of an allocation, we need integer values of the sample sizes. In the present paper the problem is to determine the integer optimum compromise allocation when the population means of various characteristics are of interest and auxiliary information is available for the separate and combined ratio and regression estimates. This paper considers the optimum compromise allocation in multivariate stratified sampling with non-linear objective function and probabilistic non-linear cost constraint. The probabilistic non-linear cost constraint is converted into equivalent deterministic one by using Chance Constrained programming. The formulated multi-objective nonlinear programming problem is solved by Fuzzy Goal programming approach and Chebyshev approximation. Numerical illustration is also given to show the practical utility of the approaches.     

On the integer-valued variables in the linear vertex packing problem

Given a graph with weights on vertices, the vertex packing problem consists of finding a vertex packing (i.e. a set of vertices, no two of them being adjacent) of maximum weight. A linear relaxation of one binary programming formulation of this problem has these two well-known properties: (i) every basic solution is (0, 1/2, 1)-valued, (ii) in an optimum linear solution, an integer-valued variable keeps the same value in an optimum binary solution.As an answer to an open problem from Nemhauser and Trotter, it is shown that there is a unique maximal set of variables which are integral in optimal (VLP) solutions.This research was supported by National Research Council of Canada GRANT A8528 and RD 804.     

MAXIMUM INFORMATION AND OPTIMUM ESTIMATING FUNCTION

In order to construct estimating functions in some parametric models, this paper introduces two classes of information matrices. Some necessary and sufficient conditions for the information matrices achieving their upper bounds are given. For the problem of estimating the median, some optimum estimating functions based on the information matrices are acquired. Under some regularity conditions, an approach to carrying out the best basis function is introduced. In nonlinear regression models, an optimum estimating function based on the information matrices is obtained. Some examples are given to illustrate the results. Finally, the concept of optimum estimating function and the methods of constructing optimum estimating function are developed in more general statistical models.     

分派问题保持最优解不变的充分必要条件

进一步讨论了在保持分派问题最优解不变的情况下,效率矩阵元素的变化范围.这些变化范围是保持分派问题最优解不变的充要条件.     

Estimation of more than one parameters in stratified sampling with fixed budget

In a multivariate stratified sampling more than one characteristic are defined on every unit of the population. An optimum allocation which is optimum for one characteristic will generally be far from optimum for others. A compromise criterion is needed to work out a usable allocation which is optimum, in some sense, for all the characteristics. When auxiliary information is also available the precision of the estimates of the parameters can be increased by using it. Furthermore, if the travel cost within the strata to approach the units selected in the sample is significant the cost function remains no more linear. In this paper an attempt has been made to obtain a compromise allocation based on minimization of individual coefficients of variation of the estimates of various characteristics, using auxiliary information and a nonlinear cost function with fixed budget. A new compromise criterion is suggested. The problem is formulated as a multiobjective all integer nonlinear programming problem. A solution procedure is also developed using goal programming technique.     

树形广播网络的最佳源点和最佳源点对

广播就是通信风格中的某些已知消息的成员（称为源点）将消息传递给其它所有成员的过程．通信网络一般用图来描述．从不同的网络成员广播一条消息所需的最少时间一般是不同的．本文在树网络中设计了选取一个或一对源点使广播时间最短的算法，这样的一个或一对源点称为最佳源点或最佳源点对．     

Inverse Eigenvalue Problem in Structural Dynamics Design

1 Introduction Structural dynamics design is to design a structure subject to the dynamic characteristics re- quirement, i.e., determine physical and geometrical parameters such that the structure has the given frequencies and (or) mode shapes. This problem often arises in engineering connected with vibration. Recently, Joseph [1], Li et al. [2,3] converted the structural dynamics design to the following inverse eigenvalue problem. GIEP Let x = (x1, , xm)T , and let A(x) and B(x) be real n…     

Optimal cargo allocation on board a plane: a sequential linear programming approach

We examine a case study of an airline company whose problem is to plan cargo allocations on board a plane. Given the volume, weight, and structural constraints, the problem of finding the optimal load layout is formulated as a fractional programming problem. An algorithm is suggested to solve the linearized problem as a sequence of linear programming problems whose optimal solutions converge to the optimum (with a predetermined level of tolerance).     

中国邮路问题的一个解法

本给出中国邮路问题的一个解法。虽然它仍只是初始方案，但因考虑了问题的足够信息，因而这种方案至少拉近了与最优解的距离。     

Provably good solutions for the traveling salesman problem

The determination of true optimum solutions of combinatorial optimization problems is seldomly required in practical applications. The majority of users of optimization software would be satisfied with solutions of guaranteed quality in the sense that it can be proven that the given solution is at most a few percent off an optimum solution. This paper presents a general framework for practical problem solving with emphasis on this aspect. A detailed discussion along with a report about extensive computational experiments is given for the traveling salesman problem.