Pure product polynomials and the Prouhet-Tarry-Escott problem

An -factor pure product is a polynomial which can be expressed in the form for some natural numbers . We define the norm of a polynomial to be the sum of the absolute values of the coefficients. It is known that every -factor pure product has norm at least . We describe three algorithms for determining the least norm an -factor pure product can have. We report results of our computations using one of these algorithms which include the result that every -factor pure product has norm strictly greater than if is , , , or .

     

Facets of the linear ordering polytope

LetD _n be the complete digraph onn nodes, and letP _LO ⁿ denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD _n (i.e. these are exactly the acyclic tournaments ofD _n ). We show that various classes of inequalities define facets ofP _LO ⁿ , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.     

On homogenization of solutions of the poisson equation in a perforated domain with different types of boundary conditions on different cavities

In this paper we consider boundary value problems in perforated domains with periodic structures and cavities of different scales, with the Neumann condition on some of them and mixed boundary conditions on others. We take a case when cavities with mixed boundary conditions have so called critical size (see [1]) and cavities with the Neumann conditions have the scale of the cell. In the same way other cases can be studied, when we have the Neumann and the Dirichlet boundary conditions or the Dirichlet condition and the mixed boundary condition on the boundary of cavities.There is a large literature where homogenization problems in perforated domains were studied [2];-[7];     

An Approach to the Subproblem of the Cutting Angle Method of Global Optimization

The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call “Dominating Subset with Minimal Weight”. This problem is also NP-Complete. An O(n²)-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.Mathematics Subject Classification (2000): 65K05, 90C27, 68Q25     

Localization Problem for General Filtration Equations

ＬｏｃａｌｉｚａｔｉｏｎＰｒｏｂｌｅｍｆｏｒＧｅｎｅｒａｌＦｉｌｔｒａｔｉｏｎＥｑｕａｔｉｏｎｓＹｕａｎＨｏｎｇｊｕｎ（袁洪君）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＪｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ，１３００２３）＆（Ｄｅ...     

Banach空间中的相补问题

本文在Ｂａｎａｃｈ空间中研究了三类相补问题解的存在性。所得结果是［４，５，６，９，１１－１４］中相应结果的深入和发展。     

Triangular derivations related to problems on affine -space

This paper studies the Cancellation Problem, the Embedding Problem, and the Linearization Problem. It shows how these problems can be related to a special class of locally nilpotent derivations.

     

On lexicographic optimal solutions in transportation problems

Lexicographic versions of the cost minimizing transportation problem (CMTP) and the time minimizing transportation problem (TMTP) are presented in this paper. In addition to minimizing the quantity sent on the costliest routes in a cost minimizing transportation problem. an attempt is made to minimize the quantity transported on the second-costliest routes. if the shipment on the costliest routes is as small as possible and the quantity shipped on the third-costliest routes, if the shipments on the costliest and the second- costliest routes are as small as possible. and so on. In a lexicographic time minimizing transportation problem one is not only interested in minimizing the transportation cost on the routes of the longest duration but also on the routes of second longest, third-longest duration and so on. For finding lexicographic optimal solutions (LOS) of lexicographic cost minimizing and time minimizing transportation problems a standard cost minimizing transportation problem is formulated whose optimal solution is shown to provide the answer. Some extensions are also discussed     

Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

The multiconstraint 0–1 knapsack problem is encountered when one has to decide how to use a knapsack with multiple resource constraints. Even though the single constraint version of this problem has received a lot of attention, the multiconstraint knapsack problem has been seldom addressed. This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxation of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.     

A Mixed Boundary Value Problem for Polyanalytic Function of Order n in the Sobolev Space Wn,p (D)

We discuss the construction of a polyanalytic function Φ of order n on a simple bounded domain D. The function satisfies n prescribed generalized Riemann-Hilbert boundary conditions on the boundary ?D and n generalized jump conditions on a simple closed smooth contour γ contained in D. The boundary conditions are transformed into n classical Riemann-Hilbert problems and the n jump conditions into n Riemann problems of conjugation for some 2n holomorphic functions. These transformed problems are solved using the standard methods from the literature.     

模糊均衡问题的求解及应用

根据实际均衡问题研究的需要,给出了模糊向量、模糊值函数、模糊矩阵等新概念,建立了模糊均衡问题的数学模型,即模糊线性互补问题。在引入新的模糊期望的基础上,研究了其性质,并据此给出了模糊线性互补问题的一种确定型等价式及此类问题的均衡解的概念。用实例说明了所提模型和方法的合理性及应用前景。     

Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.     

Steklov特征值问题的边界元近似

本文将Ｌａｐｌａｃｅ算子的Ｓｔｅｋｌｏｖ特征值问题归化为一个边界变分问题，从而使原问题的空间维数降低了一维，基于此变分问题给出了Ｓｔｅｋｌｏｖ特征值问题的边界元近似解，计算实例表明此方法是十分有效的。     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

Existence and Comparison Results for First Order Periodic Implicit Difference Equations with Maxima

In this paper, we establish comparison results (maximum principles) which allow us to use the monotone method and the method of upper and lower solutions in order to build convergent sequences to the solutions of difference equations of the type j u k = f k , u k +1 , max l ] { k m h +1,…, k +1} u l , k ] I , u 0 = u T , with j u k = u k +1 m u k , I ={0,1,…, T m 1} and f ] C ( I 2 R 2 R , R ).     

Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.     

The undirected m-Capacitated Peripatetic Salesman Problem

In the m-Capacitated Peripatetic Salesman Problem (m-CPSP) the aim is to determine m Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. This article introduces three formulations for the m-CPSP. Two branch-and-cut algorithms and one branch-and-price algorithm are developed. Tests performed on randomly generated and on TSPLIB Euclidean instances indicate that the branch-and-price algorithm can solve instances with more than twice the size of what is achievable with the branch-and-cut algorithms.     

On Nonlinear Evolution Equations with Nonmonotone Perturbations

51.Introduction'lnthispaperwedealwiththeexlstenceofsoluti0nsfortheinltialvalueproblemandtheperiodicproblemwhereAisamonotoneoperatorinaBanachspaceandGisnot.IfG=0,theexistenceofsolutionsfortheinitialvalueproblem(1.1)wasobtainedbythethe0ryofmonotoneoperators(cf-[1j,[2J).Hirano[3jprovedtheexistenceofsolutionsforGbeingcompact.AhmedandXiang['JextendedtheresultsofHirano[3JtoGsatisfyingthat(Gx.,x.-x)-Oifxnconvergestoxweakly.0urpurposeinthlspaperistofurtherextendtheirresultstoGsatisfyingamoregene…     

Stochastic Global Optimization: Problem Classes and Solution Techniques

There is a lack of a representative set of test problems for comparing global optimization methods. To remedy this a classification of essentially unconstrained global optimization problems into unimodal, easy, moderately difficult, and difficult problems is proposed. The problem features giving this classification are the chance to miss the region of attraction of the global minimum, embeddedness of the global minimum, and the number of minimizers. The classification of some often used test problems are given and it is recognized that most of them are easy and some even unimodal. Global optimization solution techniques treated are global, local, and adaptive search and their use for tackling different classes of problems is discussed. The problem of fair comparison of methods is then adressed. Further possible components of a general global optimization tool based on the problem classes and solution techniques is presented.