Continuous quadratic programming formulations of optimization problems on graphs

Four NP-hard optimization problems on graphs are studied: The vertex separator problem, the edge separator problem, the maximum clique problem, and the maximum independent set problem. We show that the vertex separator problem is equivalent to a continuous bilinear quadratic program. This continuous formulation is compared to known continuous quadratic programming formulations for the edge separator problem, the maximum clique problem, and the maximum independent set problem. All of these formulations, when expressed as maximization problems, are shown to follow from the convexity properties of the objective function along the edges of the feasible set. An algorithm is given which exploits the continuous formulation of the vertex separator problem to quickly compute approximate separators. Computational results are given.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

Reconstruction of boundary regimes in the inverse problem of thermal convection of a high-viscosity fluid

A problem of reconstruction of boundary regimes in a model for free convection of a high-viscosity fluid is considered. A variational method and a quasi-inversion method are suggested for solving the problem in question. The variational method is based on the reduction of the original inverse problem to some equivalent variational minimum problem for an appropriate objective functional and solving this problem by a gradient method. When realizing the gradient method for finding a minimizing element of the objective functional, an iterative process actually reducing the original problem to a series of direct well-posed problems is organized. For the quasi-inversion method, the original differential model is modified by means of introducing special additional differential terms of higher order with small parameters as coefficients. The new perturbed problem is well-posed; this allows one to solve this problem by standard methods. An appropriate choice of small parameters gives an opportunity to obtain acceptable qualitative and quantitative results in solving the inverse problem. A comparison of the methods suggested for solving the inverse problem is made with the use of model examples.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

Solving the optimal control problem of the parabolic PDEs in exploitation of oil

In this paper, the optimal control problem is governed by weak coupled parabolic PDEs and involves pointwise state and control constraints. We use measure theory method for solving this problem. In order to use the weak solution of problem, first problem has been transformed into measure form. This problem is reduced to a linear programming problem. Then we obtain an optimal measure which is approximated by a finite combination of atomic measures. We find piecewise-constant optimal control functions which are an approximate control for the original optimal control problem.     

Problem difficulty of real instances of convoy planning

Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.     

On the complexity of recognizing a class of generalized networks

The problem of determining whether a given linear programming problem can be converted to a generalized network flow problem having no unit-weight cycles is shown to be NP-hard. The same argument also shows that the problem of determining whether a gain matroid is bicircular is NP-hard.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

Recovery of the unknown coefficients in a two-dimensional hyperbolic equation

In this paper, an inverse boundary value problem for a two-dimensional hyperbolic equation with overdetermination conditions is studied. To investigate the solvability of the original problem, we first consider an auxiliary inverse boundary value problem and prove its equivalence to the original problem in a certain sense. We then use the Fourier method to reduce such an equivalent problem to a system of integral equations. Furthermore, we prove the existence and uniqueness theorem for the auxiliary problem by the contraction mappings principle. Based on the equivalency of these problems, the existence and uniqueness theorem for the classical solution of the original inverse problem is proved. Some discussions on the numerical solutions for this inverse problem are presented including some numerical examples.     

On the uniqueness of a solution of a two-phase free boundary problem

In this paper, we study the uniqueness problem of a two-phase elliptic free boundary problem arising from the phase transition problem subject to given boundary data. We show that in general the comparison principle between the sub- and super-solutions does not hold, and there is no uniqueness of either a viscosity solution or a minimizer of this free boundary problem by constructing counter-examples in various cases in any dimension. In one-dimension, a bifurcation phenomenon presents and the uniqueness problem has been completely analyzed. In fact, the critical case signifies the change from uniqueness to non-uniqueness of a solution of the free boundary problem. Non-uniqueness of a solution of the free boundary problem suggests different physical stationary states caused by different processes, such as melting of ice or solidification of water, even with the same prescribed boundary data. However, we prove that a uniqueness theorem is true for the initial-boundary value problem of an ε-evolutionary problem which is the smoothed two-phase parabolic free boundary problem.     

On minimizing the duration of transportation

The problem of minimizing the duration of transportation has been studied. The problem has been reduced to a goal programming-type problem which readily lends itself to solution by the standard transportation method. This approach to the solution of the problem is very much different from all other existing ones.     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

Optimization of rod antennas of mobile phones

Two types of rod antennas of mobile phones are optimized so that the radiated energy absorbed by the head or body of the user is reduced and the radiation intensity to other areas especially to the receiver is increased. The mathematical modelling of this problem leads to an infinite dimensional bicriterial optimization problem. It is shown that this optimization problem and a discretized version of this problem are solvable. The relationship between the infinite and finite dimensional optimization problem is investigated. Numerical results are presented for mobile phones working with the GSM standards 900 and 1800.     

一类非单调互补问题的Canonical对偶问题研究

对于一类具有广泛应用背景的非单调互补问题,我们构建了这类问题的Canonical对偶问题。其对偶问题可以写成和原问题类似的互补问题。我们给出了对偶问题和原问题解之间的对偶关系,并且将对偶问题转化成一个一维优化问题,这不但可以方便的求解这类问题,也为研究这类问题性质提供了一个非常直观的研究工具。最后,本文给出了几个算例来演示对偶问题的性质。     

A numerical solution of the elasticity problem of settled of the wronkler ground with variable coefficients

In this paper, we have given numerical solution of the elasticity problem of settled on the wronkler ground with variable coefficient. The approximation solution of boundary value problem which is pertinent to this has been converted to integral equations, and then by using the successive approximation methods, has been reached. In addition to this, the approximation solution of the problem was put into Padé series form. We applied these methods to an example which is the elasticity problem of unit length homogeny beam, which is a special form of boundary value problem. First we calculate the successive approximation of the given boundary value problem then transform it into Padé series form, which give an arbitrary order for solving differential equation numerically.     

Strong convergence of difference approximations in the problem of transverse vibrations of thin elastic plates

The problem of transverse vibrations of a thin elastic plate is considered. It is proved that the differential operators of the boundary value problem are regularly elliptic, and weak solutions are estimated. For a previously developed difference method, the solution to the difference problem is proved to converge strongly to a weak solution of the original differential problem and the rate of convergence is estimated.     

Notes on the Problem of the Allocation of Resources to Activities in Discrete Quantities

The simple resource allocation problem (also called the distribution of effort problem) is generalized by allowing more than one resource constraint. It is shown that the generalized problem can be reduced to the simple one if the coefficients in the objective function are all unity. In general, however, the problem seems to become much more difficult; the difficulty is evidenced by the failure of the incremental method which is valid for the simple problem, and the NP-hardness of the generalized problem.     

The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

取油管振动方程解的整体不存在性

讨论推广的海底取油管振动方程的初边值问题和初值问题解的整体不存在性,对初边值问题推广了Gmira和Guedda得到的结果,对初值问题的结果是新的.