Variable space search for graph coloring

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.     

A new filled function method for nonlinear equations

In this paper, a new global optimization approach based on the filled function method is proposed for solving box-constrained systems of nonlinear equations. We first convert the nonlinear system into an equivalent global optimization problem, and then propose a new filled function method to solve the converted global optimization problem. Several numerical examples are presented and solved by using different local minimization methods, which illustrate the efficiency of the present approach.     

Small-time local controllability and continuity of the optimal time function for linear systems

For a finite-dimensional linear system, in which the control is restricted to belong to a completely arbitrary setJ, we give a simple necessary and sufficient condition for small-time local controllability from a pointp. The condition is equivalent to a characterization of the property that the Bellman function for the corresponding minimum-time optimal control problem is continuous atp.This work was partially supported by the National Science Foundation, Grant No. MCS-78-02442.     

Use of the equivalent attribute technique in multi-criteria planning of local energy systems

This paper discusses how the equivalent attribute technique (EAT) can be used to improve the comprehensibility of a multi-attribute utility theory study. When using EAT, ‘vague’ expected total utility values are converted into equivalent values for one of the attributes being considered, often an economic attribute. Two models are considered: a simplified linear model, and a more advanced non-linear model that includes the DM’s strength-of-preference and risk attitude. EAT is particularly useful in distinguishing between alternatives with similar utility values. When the difference between utility values is larger, the choice among the alternatives should be clear, and EAT therefore becomes less useful. The technique can still be used, although extra care is needed when choosing the equivalent attribute. A local energy-planning problem is used as a case study to illustrate and exemplify the EAT approach.     

求解互补问题的一种序列二次规划方法

通过将互补问题转化为一种带非负约束的极小化问题 ,给出了求解互补问题的一种序列二次规划方法 .该方法中每一个子问题都是可解的 ,迭代产生的序列是非负的 ,在适当的条件下 ,分别证明了算法的全局收敛性、局部超线收敛性以及局部二次收敛性 .     

Heuristics for multi-period capacity expansion in local telecommunications networks

In this paper, different heuristics are devised to solve a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. This expansion is done by installing concentrators at the nodes and cables on the links of the network. The goal is to find a least cost capacity expansion strategy over a number of periods to satisfy the demand. A local search heuristic is first proposed to improve previously reported results on problem instances based on different cost and demand structures. This heuristic is then integrated into a genetic algorithm to obtain further improvements.     

On the classification of all self-dual additive codes over GF(4) of length up to 12

We consider additive codes over GF(4) that are self-dual with respect to the Hermitian trace inner product. Such codes have a well-known interpretation as quantum codes and correspond to isotropic systems. It has also been shown that these codes can be represented as graphs, and that two codes are equivalent if and only if the corresponding graphs are equivalent with respect to local complementation and graph isomorphism. We use these facts to classify all codes of length up to 12, where previously only all codes of length up to 9 were known. We also classify all extremal Type II codes of length 14. Finally, we find that the smallest Type I and Type II codes with trivial automorphism group have length 9 and 12, respectively.     

半连续格上的半基和局部半基

在完备格上引入了半基和局部半基的概念,给出了半基和局部半基的性质及若干等价刻画,证明了一个完备格是半连续格当且仅当它具有半基也当且仅当它每点有局部半基。在此基础上定义了半连续格的权和特征,探讨了半连续格的权和特征与其上赋予半Scott拓扑和半Lawson拓扑时的拓扑空间的权和特征的关系。解决了文献[8](赵彬,刘妮.连续Domain的特征和浓度,陕西师范大学学报,2002,30(2):1~6)中提出的一个问题。     

On local search for the generalized graph coloring problem

Given an edge-weighted graph and an integer k, the generalized graph coloring problem is the problem of partitioning the vertex set into k subsets so as to minimize the total weight of the edges that are included in a single subset. We recall a result on the equivalence between Karush-Kuhn-Tucker points for a quadratic programming formulation and local optima for the simple flip-neighborhood. We also show that the quality of local optima with respect to a large class of neighborhoods may be arbitrarily bad and that some local optima may be hard to find.     

A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033–1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile that VNS metaheuristic is extended to solve max-bisection problems. Unfortunately, comparing with max-cut problems, max-bisection problems have more complicated feasible region via the linear constraint e^Tx=0. It is hard to directly apply the typical VNS metaheuristic to deal with max-bisection problems. In this paper, we skillfully combine the constraint e^Tx=0 with the objective function, obtain a new optimization problem which is equivalent to the max-bisection problem, and then adopt a distinct greedy local search technique to the resulted problem. A modified VNS metaheuristic based on the greedy local search technique is applied to solve max-bisection problems. Numerical results indicate that the proposed method is efficient and can obtain high equality solution for max-bisection problems.     

Characterization of local sampling sequences for spline subspaces

The sampling theorem is one of the most powerful tools in signal analysis. It says that to recover a function in certain function spaces, it suffices to know the values of the function on a sequence of points. Most of known results, e.g., regular and irregular sampling theorems for band-limited functions, concern global sampling. That is, to recover a function at a point or on an interval, we have to know all the samples which are usually infinitely many. On the other hand, local sampling, which invokes only finite samples to reconstruct a function on a bounded interval, is practically useful since we need only to consider a function on a bounded interval in many cases and computers can process only finite samples. In this paper, we give a characterization of local sampling sequences for spline subspaces, which is equivalent to the celebrated Schönberg-Whitney Theorem and is easy to verify. As applications, we give several local sampling theorems on spline subspaces, which generalize and improve some known results.     

ON THE GLOBAL STABILITY CONJECTURE OF THE GENOTYPE SELECTION MODEL

In 1994, Grove, Kocic, Ladas, and Levin conjectured that the local stability and global stability conditions of the fixed point y = 1/2 in the genotype selection model should be equivalent. In this article, we give an affirmative answer to this conjecture and prove that local stability implies global stability. Some illustrative examples are included to demonstrate the validity and applicability of the results.     

Equivalent conditions of local asymptotics for the solutions of defective renewal equations, with applications

The paper obtains some equivalent conditions of local asymptotics for the solutions of defective renewal equations in the heavy-tailed case. As applications, the paper gives a different proof of a classical result about the local distribution of the supremum of a random walk. These results are also applied in examples involving the renewal function for terminating renewal processes and the age-dependent branching processes.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.     

LOCAL CLASSICAL SOLUTION OF FREE BOUNDARY PROBLEM FOR A COUPLED SYSTEM

This paper considers a two-phase free boundary problem for coupled system including one parabolic equation and two elliptic equations. The problem comes from the discussion of a growth model of self-lnaintaining protocell in multidimensional case. The local classical solution of the problem with free boundary F : y = g(x,t) between two domains is being seeked. The local existence and uniqueness of the problem will be proved in multidimensional case.     

LOCAL AND PARALLEL FINITE ELEMENT ALGORITHMS FOR THE NAVIER-STOKES PROBLEM

Based on two-grid discretizations, in this paper, some new local and parallel finiteelement algorithms are proposed and analyzed for the stationary incompressible Navier-Stokes problem. These algorithms are motivated by the observation that for a solutionto the Navier-Stokes problem, low frequency components can be approximated well by arelatively coarse grid and high frequency components can be computed on a fine grid bysome local and parallel procedure. One major technical tool for the analysis is some locala priori error estimates that are also obtained in this paper for the finite element solutionson general shape-regular grids.     

Guided Local Search for Final Placement in VLSI Design

The design of a VLSI circuit consists of two main parts: First, the logical functionality of the circuit is described, and then the physical layout of the modules and connections is settled. In the latter process one wishes to place the modules such that the necessary wiring becomes as small as possible in order to minimize area usage and delays on signal paths. The placement problem is the subproblem of the layout problem which considers the geometric locations of the modules. A new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength. The heuristic is based on the Guided Local Search (GLS) metaheuristic. GLS modifies the objective function in a constructive way to escape local minima. Previous attempts to use local search on final (or detailed) placement problems have often failed as the neighbourhood quickly becomes too excessive for large circuits. Nevertheless, by combining GLS with Fast Local Search it is possible to focus the search on appropriate sub-neighbourhoods, thus reducing the time complexity considerably. Comprehensive computational experiments with the developed algorithm are reported on a broad range of industrial circuits. The experiments demonstrate that the developed algorithm is able to improve the estimated routing length of large-sized layouts with as much as 20 percent when compared to existing algorithms.     

Local properties of intertwining operators on the sphere

Blaschke?s original question regarding the local determination of zonoids (or projection bodies) has been the subject of much research over the years. In recent times this research has been extended to include intersection bodies and it has been shown that neither zonoids nor intersection bodies have local characterizations. However, it has also been proved that both these classes of bodies admit equatorial characterizations in odd dimensions, but not in even dimensions. The proofs of these results were mostly analytic using properties of associated spherical integral transforms, the Cosine transform and the Radon transform.Here we elaborate a general principle, showing that such local or equatorial characterization problems are equivalent to corresponding support properties of the spherical operators. We discuss this within a general framework, for intertwining operators on C^∞-functions, and apply the results to further geometric constructions, namely to certain mean section bodies, to Lq-centroid bodies and to k-intersection bodies.     

关于总体分布的矩确定

本文引进了局部分布、局部矩、局部矩法估计、样本局部矩和局部分布的矩确定等概念。从而为著名的经典矩量问题提供了新的研究途径与方法并获得了若干新结果。     

Parallel Information Algorithm with Local Tuning for Solving Multidimensional GO Problems

In this paper we propose a new parallel algorithm for solving global optimization (GO) multidimensional problems. The method unifies two powerful approaches for accelerating the search: parallel computations and local tuning on the behavior of the objective function. We establish convergence conditions for the algorithm and theoretically show that the usage of local information during the global search permits to accelerate solving the problem significantly. Results of numerical experiments executed with 100 test functions are also reported.