Inconsistent heuristics in theory and practice

In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term “inconsistent heuristic” has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for A^? (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA^?.This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the AI literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented.Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA^? and A^?. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA^?. Positive results are also presented for A^? searches.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

A heuristic search approach for solving a minimum path problemrequiring arc cost determination

Two generalizations of A*, BA* and DA*, are presented and analyzed. Both consider the problem of finding a minimum cost path from the start node to a finite goal node set in a directed OR-graph, assuming that estimates of the optimal costs from each node to the goal node set are given (as described by the heuristic function), estimates of all arc costs are given, but the actual arc costs require determination. DA* tends to determine a solution (not necessarily optimal) more rapidly than BA*. Improved admissible heuristics and arc cost estimates tend to reduce node expansions and arc cost determination steps for BA*; however, these results do not necessarily hold for DA*. We also show that BA* tends to require more arc cost determination steps and fewer node expansions than does DA*     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

The General Steiner Tree-Star problem

The Steiner tree problem is defined as follows—given a graph G=(V,E) and a subset X⊂V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a “switch” cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V?X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.     

An integer programming-based local search for the covering salesman problem

We consider a generalized version of the well known Traveling Salesman Problem called Covering Salesman problem. In this problem, we are given a set of vertices while each vertex i can cover a subset of vertices within its predetermined covering distance r_i. The goal is to construct a minimum length Hamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. The paper proposes an Integer Linear Programming based heuristic method which takes advantage of Integer Linear Programming techniques and heuristic search to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach.     

Range free localization technique under erroneous estimation in wireless sensor networks

Minkowski timespace has the capability to overcome the limited accuracy of L₂-norm based range-free localization methods. This paper proposes the concept of Minkowski triangulation uncertainty (MTU) in wireless sensor networks (WSNs) for localization of unknown target. To set up a localization framework, triangulation uncertainty parameter is defined using Lemma 3.1. A two-stage estimation algorithm is then presented: countLocalized and countAnchor. countLocalized computes the number of localized sensor nodes by leveraging the uncertainty strategy based upon indeterminate independent measurement. countAnchor designates the anchor nodes to triangulate the unknown target by formulating a convex hull model. The convex hull is the Minkowski sum of the actual and projected positions of the two vector node positions. The proposed MTU technique establishes that the number of triangulations formed by Minkowski method is inclusive of the triangulations formed by conventional L₂-norm range of sensor nodes in a WSN. Measurement strategies such as angle, distance and positioning error are compared in the simulation. The said technique links Minkowski space to localization by ensuring efficiency in large target areas and number of nodes in manifolds. Results confirm that the MTU technique is better than the existing models by at least 12%, 50%, 5.5% and 24% in terms of localization ratio, localization error, neighbour anchor nodes and network connectivity, respectively.

     

Positioning empty containers under dependent demand process

Owing to trade imbalance, shipping companies position empty containers between ports or depots periodically. The most difficult problem for positioning is that it is not possible to know the exact amounts of empty containers required in the future. The paper deals with the problem of positioning empty containers in a port area with multiple depots. Customer demands and returning containers in depots per unit time period are assumed to be serially-correlated and dependent random variables. Three options are considered to prepare the required extent of positioning: positioning from other overseas ports, inland positioning between depots, and leasing. The policies for empty-container management consist of three parts as follows: a coordinated, (s, S) inventory policy for positioning from other ports, (r_i, R_i) policy for inland positioning between depots; and a simple leasing policy with zero lead-time. For inland positioning policy, four heuristic methods are proposed to reposition empty containers between depots. The objective is to obtain optimal policies corresponding to different methods of inland positioning in order to minimize the expected total costs. A genetic-based optimization procedure is developed to find the optimal parameters (s, S) and (r_i, R_i). Some numerical examples and sensitivity analyses are given to demonstrate the results.     

An informal introduction to a high level language with applications to interval mathematics

The main problem of interval computations is as follows:given sets of possible valuesX _i for variablesx _i, and an algorithmf:R ⁿ → R, to.estimate the rangef(X ₁, ..,X _n ) of the possible values off(x ₁, ...,x _n ). In many real-life, situations setsX _i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show:

· that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations;

· and that bag languages can be also helpfully applied to traditional interval computations (where setsX _i are intervals).

     

Optimal interval scheduling with a resource constraint

We consider a scheduling problem where n jobs have to be carried out by m parallel identical machines. The attributes of a job j are a fixed start time s_j, a fixed finish time f_j, a resource requirement r_j, and a value v_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, we ask for a subset of jobs that can be feasibly scheduled with the maximum total value. For this strongly NP-hard problem, we first discuss an approximation result. Then, we propose a column generation scheme for the exact solution. Finally, we suggest some greedy heuristics and a restricted enumeration heuristic. All proposed algorithms are implemented and tested on a large set of randomly generated instances. It turns out that the column generation technique clearly outperforms the direct resolution of a natural compact formulation; the greedy algorithms produce good quality solutions in negligible time, whereas the restricted enumeration averages the performance of the greedy methods and the exact technique.     

Computation of thermodynamic properties of quarternary and higher order systems from binary data using shortest distance composition paths

Equations for the computation of integral and partial thermodynamic properties of mixing in quarternary systems are derived using data on constituent binary systems and shortest distance composition paths to the binaries. The composition path from a quarternary composition to the i-j binary is characterized by a constant value of (X_i ? X_j). The merits of this composition path over others with constant values for $\text{X}{}_{\mathrm{i}}\text{X}{}_{\mathrm{j}}$ or X_i are discussed. Finally the equations are generalized for higher order systems. They are exact for regular solutions, but may be used in a semiempirical mode for non-regular solutions.     

Reduction of Permutation-Invariant Polynomials: A Noncommutative Case Study

Let R be a commutative ring with 1, let RX₁,…,X_n/I be the polynomial algebra in the n≥4 noncommuting variables X₁,…,X_n over R modulo the set of commutator relations I={(X₁+···+X_n)*X_i=X_i*(X₁+···+X_n)|1≤i≤n}. Furthermore, let G be an arbitrary group of permutations operating on the indeterminates X₁,…,X_n, and let RX₁,…,X_n/I^G be the R-algebra of G-invariant polynomials in RX₁,…,X_n/I. The first part of this paper is about an algorithm, which computes a representation for any fRX₁,…,X_n/I^G as a polynomial in multilinear G-invariant polynomials, i.e., the maximal variable degree of the generators of RX₁,…,X_n/I^G is at most 1. The algorithm works for any ring R and for any permutation group G. In addition, we present a bound for the number of necessary generators for the representation of all G-invariant polynomials in RX₁,…,X_n/I^G with a total degree of at most d. The second part contains a first but promising analysis of G-invariant polynomials of solvable polynomial rings.     

A note on computing set overlap classes

Let V be a finite set of n elements and F={X₁,X₂,…,Xm} a family of m subsets of V. Two sets Xi and Xj of F overlap if Xi∩Xj≠∅, Xj?Xi≠∅, and Xi?Xj≠∅. Two sets X,Y∈F are in the same overlap class if there is a series X=X₁,X₂,…,Xk=Y of sets of F in which each XiXi+1 overlaps. In this note, we focus on efficiently identifying all overlap classes in time. We thus revisit the clever algorithm of Dahlhaus [E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. Algorithms 36 (2) (2000) 205-240] of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.     

Zonation of sequences of heteroscedastic multivariate data

A problem in the earth sciences is to reduce a sequence of observation vectors X₁, X₂, …, X_N to a set of internally homogeneous segments or zones. This paper uses the model that the observation vectors in the ith zone are a random sample from the multivariate normal N(ξ_i, Σ_i) distribution. It is demonstrated that the maximum likelihood estimates of the boundaries between zones may be determined by dynamic programming, and a FORTRAN algorithm to perform this estimation is given.     

Load Balanced Mapping of Distributed Objects to Minimize Network Communication

This paper introduces a new load balancing and communication minimizing heuristic used in theInverse Remote Procedure Call(IRPC) system. While the paper briefly describes the IRPC system, the focus is on the newIRPCassignment heuristic. The IRPC compiler maps a distributed program to a graph that represents program objects and their dependencies (due to invocations and parameter passing) as nodes and edges, respectively. In the graph, the system preserves conditional and iterative flows, records network transmission and execution costs, and marks nodes that have to reside at specific network sites. The graph is then partitioned by the heuristic to derive a (sub)optimal node assignment to network sites minimizing load balancing and network data transport. The resulting program partition is then reflected in the physical object distribution, and remote and local object communication is transparently implemented. The compiler and run-time system use efficient implementation techniques such as type prediction, inlining, splitting and subprogram passing. The last of these allows remote code to be copied to local data, as an alternative to copying data to the remote site, whenever this will reduce network data transport. The IRPC graph partitioning heuristic operates in timeO(E(logd+l+ logM)), whereMis the number of network sites,Eis the number of communication edges, anddis the maximum degree of a node;lis a parameter of the algorithm, and can vary between 1 andN, whereNis the number of communicating objects. This complexity is more nearly independent ofM, and considerably better in terms ofEandN, than that of previously known related algorithms, such as A*, which employs backtracking and is potentially exponential, or the max-flow/min-cut class of network flow algorithms or heuristics which tend to be at least of Ω(MN²E), and it can be made (by choosinglappropriately) as efficient as even such fast heuristics as heaviest-edge-first, minimal communication, and Kernighan–Lin. In an extensive quantitative evaluation, the heuristic has been demonstrated to perform very well, giving on the average 75% traffic cost reductions for over 95% of the programs when compared to random partitioning, and outperforming in cost reduction and actual execution time the three aforementioned fast heuristics, even with a largel. Thus, to the best of our knowledge, this is the first report of a well-performing assignment heuristic that is bothessentially linearin the number of communication edges, andbetterthan existing, established heuristics of no better complexity.     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

An alternative approach to non-linear filtering†

The following non-linear filtering problem is discussed. Consider a process {X_t, t≥0}, determined by the stochastic differential equation

with the noisy observations of this process given by dy = h(x) dt + y(x) dB, t> 0, y?R^r, where W and B are R^m valued and R^r valued Wiener processes respectively and q is a zero-mean Poisson random measure on [0, ∞) × R^m. An observer is required of the form dz = j(z) dt + G(z) (dy — h(z) dt), t>0, z?R^m, where the ‘ gain matrix ” G has yet to be determined. Let DeRIm be a given centrally symmetric open and bounded domain with the origin at its centre, and let t be the first time that (X_t; Z_i)D given that (X₀, Z₀)?D (Zt is the state of the observer). The approach adopted here is to choose a matrix G*, of a bang-bang type, in such a manner that tho expected value of A{t:0≤tt- Z_t≤?} is maximized on a class of admissible gain matrices. Here A is the Lebesgue measure on the real line and ?>0 is given. Sufficient conditions on the maximizing gain matrix are derived. These conditions can be applied off-line and can be used in the design of the observers. Several examples are solved numerically.