A theory for the optimal synthesis of heat-exchanger systems

The problem of the optimal synthesis of heat exchanger systems is treated here with an entirely new approach. It is formulated, using the heat spectrum diagram, as a problem of finding the combination of heat donors and receivers that will minimize a given criterion function. This function is the cost of the heat exchanger system, assumed to be proportional to the total heat-transfer area.The problem is a combinatorial problem for continuous elements. It is solved in general by applying the maximum principle of Pontryagin. The solution for a specific problem is shown to be obtainable by a simple graphical operation.     

New lower bounds for the facility location problem with clients’ preferences

A bilevel facility location problem in which the clients choose suppliers based on their own preferences is studied. It is shown that the coopertative and anticooperative statements can be reduced to a particular case in which every client has a linear preference order on the set of facilities to be opened. For this case, various reductions of the bilevel problem to integer linear programs are considered. A new statement of the problem is proposed that is based on a family of valid inequalities that are related to the problem on a pair of matrices and the set packing problem. It is shown that this formulation is stronger than the other known formulations from the viewpoint of the linear relaxation and the integrality gap.     

一类双层规划问题及其在矩阵对策中的应用

基于建设节约型社会和保护资源环境的需要,提出了一类特殊的双层规划问题,即B规划.给出了B规划的数学模型、有关理论和求解方法.最后还给出了B规划在矩阵对策中的一个应用.我们把局中人设有得失控制值的对策问题称为稳妥型对策.稳妥型矩阵对策可化为B规划问题求解.     

Design of electricity supply networks

The problem of designing a secure electricity supply network at minimal cost is formulated as a mathematical program. It is also shown how computationally convenient new constraints may be derived and these are added to the original set. The problem is dualized and solved approximately. It is indicated how this approach can be built into a Branch-and-Bound scheme for solving the original design problem, and an illustrative example is given.     

Laplace方程有孔椭圆区域边值问题的解析解

本文利用相似流动替换方法 ,解决了中心有圆孔的椭园形区域上 Laplace方程第一类边值问题 ;采用分区域解法 ,给出了中心有椭园孔的椭园形区域上 Laplace方程第一类边值问题的解析通解 .这一结果在许多工程领域有重要应用 ,本文给出了油藏工程实例     

A path relinking approach with ejection chains for the generalized assignment problem

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and supply chains. The problem has been studied since the late 1960s, and computer codes for practical applications emerged in the early 1970s. We propose a new algorithm for this problem that proves to be more effective than previously existing methods. The algorithm features a path relinking approach, which is a mechanism for generating new solutions by combining two or more reference solutions. It also features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. Computational comparisons on benchmark instances show that the method is not only effective in general, but is especially effective for types D and E instances, which are known to be very difficult.     

On Quantum Stochastic Differential Equations as Dirac Boundary-Value Problems

We prove that a single-jump unitary quantum stochastic evolution is unitarily equivalent to the Dirac boundary-value problem on the half-line in an extended space. It is shown that this solvable model can be derived from the Schrödinger boundary-value problem for a positive relativistic Hamiltonian on the half-line as the inductive ultrarelativistic limit corresponding to the input flow of Dirac particles with asymptotically infinite momenta. Thus the problem of stochastic approximation can be reduced to a quantum mechanical boundary-value problem in the extended space. The problem of microscopic time reversibility is also discussed in the paper.     

Numerical solution of Hopf bifurcation problems

We present two numerical methods for the solution of Hopf bifurcation problems involving ordinary differential equations. The first one consists in a discretization of the continuous problem by means of shooting or multiple shooting methods. Thus a finite-dimensional bifurcation problem of special structure is obtained. It may be treated by appropriate iterative algorithms. The second approach transforms the Hopf bifurcation problem into a regular nonlinear boundary value problem of higher dimension which depends on a perturbation parameter ?. It has isolated solutions in the ?-domain of interest, so that conventional discretization methods can be applied. We also consider a concrete Hopf bifurcation problem, a biological feedback inhibition control system. Both methods are applied to it successfully.     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

Minimizing the total completion time in a single-machine scheduling problem with a learning effect

This paper introduces a new time-dependent learning effect model into a single-machine scheduling problem. The time-dependent learning effect means that the processing time of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. In most related studies, the actual job processing time is assumed to be a function of its scheduled position when the learning effect is considered in the scheduling problem. In this paper, the actual processing time of a job is assumed to be proportionate to the length and position of the already scheduled jobs. It shows that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. It also shows that the shortest processing time (SPT) rule provides the optimum sequence for the addressed problem.     

Cost/time trade-off analysis for the critical path method: a derivation of the network flow approach

A well-known problem in critical path analysis involves normal and crash durations being provided for each activity, with corresponding costs, and requires a minimum cost schedule of durations to be determined for all possible durations of the project. It has long been known that an optimal solution to the problem can be obtained iteratively by constructing a minimum cost network flow problem and adjusting the durations of activities corresponding to a minimum capacity cut-set. A recent paper described this method, but gave no indication of how the method could be derived. It is shown here that a linear programming formulation and its dual enables this to be done very simply.     

A new algorithm for the small-field astrometric point-pattern matching problem

The small-field astrometric point-pattern matching problem is a fundamental problem in astronomy, that although considered a long time ago still lacks a formal definition. It can be textually stated as: given two lists of positions of stars, find the common stars between these lists, taking into account rotation, translation, reflection and scaling operations. It is expected that there might be missing stars between the lists. In this work, we give the astronomical context, review some heuristic methods adopted in the literature, present distance matrix formulations for the problem and propose a new algorithm to solve it.     

Variational principles and convergence of finite element approximations of a holonomic elastic-plastic problem

Summary It is shown that a boundary-value problem based on a holonomic elastic-plastic constitutive law may be formulated equivalently as a variational inequality of the second kind. A regularised form of the problem is analysed, and finite element approximations are considered. It is shown that solutions based on finite element approximation of the regularised problem converge.     

A posteriori joint detection of reference fragments in a quasi-periodic sequence

The problem of joint detection of quasi-periodic reference fragments (of given size) in a numerical sequence and its partition into segments containing series of recurring reference fragments is solved in the framework of the a posteriori approach. It is assumed that (i) the number of desired fragments is not known, (ii) an ordered reference tuple of sequences to be detected is given, (iii) the index of the sequence member corresponding to the beginning of a fragment is a deterministic (not random) value, and (iv) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is established that the problem consists of testing a set of hypotheses about the mean of a random Gaussian vector. The cardinality of the set grows exponentially as the vector dimension (i.e., the sequence length) increases. It is shown that the search for a maximum-likelihood hypothesis is equivalent to the search for arguments that minimize an auxiliary objective function. It is proved that the minimization problem for this function can be solved in polynomial time. An exact algorithm for its solution is substantiated. Based on the solution to an auxiliary extremum problem, an efficient a posteriori algorithm producing an optimal (maximum-likelihood) solution to the partition and detection problem is proposed. The results of numerical simulation demonstrate the noise stability of the algorithm.     

Solvability of Independent Systems of Equations in Finitely Generated Nilpotent Groups

Mathematical Notes - It is proved that the solvability problem for a finite independent system of equations in a finitely generated nilpotent group can effectively be reduced to a similar problem...     

Optimal control in a quantum cooling problem

The optimal control for cooling a quantum harmonic oscillator by controlling its frequency is considered. It is shown that this singular problem may be transformed with the proper choice of coordinates to an equivalent problem which is no longer singular. The coordinates used are sufficiently simple that a graphical solution is possible and eliminates the need to use a Weierstrass-like approach to show optimality. The optimal control of this problem is of significance in connection with cooling physical systems to low temperatures. It is also mathematically significant in showing the power and limitations of coordinate transformations for attacking apparently singular problems.     

Vehicle Routeing with Multiple Use of Vehicles

The vehicle routeing problem with multiple use of vehicles is a variant of the standard vehicle routeing problem in which the same vehicle may be assigned to several routes during a given planning period. A tabu search heuristic is developed for this problem. It is shown to produce high quality solutions on a series of test problems.     

A Discrete Chebyshev Approximation Problem by Means of Several Polynomials

The problem of approximation of a given function on a given set by a polynomial of a fixed degree in the Chebyshev metric (the Chebyshev polynomial approximation problem) is a typical problem of Nonsmooth Analysis (to be more precise, it is a convex nonsmooth problem). It has many important applications, both in mathematics and in practice. The theory of Chebyshev approximations enjoys very nice properties (the most famous being the Chebyshev alternation rule). In the present article the problem of approximation of a given function on a given finite set of points by several polynomials is studied. As a criterion function, the maximin deviation is taken. The resulting functional is nonsmooth and nonconvex and therefore the problem becomes multiextremal and may have local minimizers which are not global ones. A necessary and sufficient condition for a point to be a local minimizer is proved. It is shown that a generalized alternation rule is still valid. Sufficient conditions for a point to be a strict local minimizer are established as well. These conditions are also formulated in terms of alternants. An exchange algorithm for finding a local minimizer is constructed. An k -exchange algorithm, allowing to find a "better" local minimizer is stated. Numerical examples illustrating the theory are presented.     

Models with Network Duals

It is pointed out that a number of practical problems can be formulated as linear programmes whose duals are network flow models. The interpretation of these networks in relation to the original problem can be highly illuminating. If, as is frequently the case, the objective of the original problem is monetary, the network dual concerns the optimal pattern of re-allocation of money. It is suggested that the conceptual simplicity of a network makes this an attractive way to view problems as well as indicating efficient computational procedures.     

Decomposed enumeration of extreme points in the linear programming problem

In this paper we consider the problem of enumeration of extreme points in the linear programming problem when the matrix is of block-angular type. It is shown how decomposition methods can be used. Finally application of decomposed enumeration to the problem of computing equilibrium prices in a capital market network is given as an example.