Solving the clique partitioning problem as a maximally diverse grouping problem

In this paper we show that the clique partitioning problem can be reformulated in an equivalent form as the maximally diverse grouping problem (MDGP). We then modify a skewed general variable neighborhood search (SGVNS) heuristic that was first developed to solve the MDGP. Similarly as with the MDGP, significant improvements over the state of the art are obtained when SGVNS is tested on large scale instances. This further confirms the usefulness of a combined approach of diversification afforded with skewed VNS and intensification afforded with the local search in general VNS.     

Model-Based Search for Combinatorial Optimization: A Critical Survey

In this paper we introduce model-based search as a unifying framework accommodating some recently proposed metaheuristics for combinatorial optimization such as ant colony optimization, stochastic gradient ascent, cross-entropy and estimation of distribution methods. We discuss similarities as well as distinctive features of each method and we propose some extensions.     

A new local search for continuous location problems

This paper presents a new local search approach for solving continuous location problems. The main idea is to exploit the relation between the continuous model and its discrete counterpart. A local search is first conducted in the continuous space until a local optimum is reached. It then switches to a discrete space that represents a discretisation of the continuous model to find an improved solution from there. The process continues switching between the two problem formulations until no further improvement can be found in either. Thus, we may view the procedure as a new adaption of formulation space search. The local search is applied to the multi-source Weber problem where encouraging results are obtained. This local search is also embedded within Variable Neighbourhood Search producing excellent results.     

Design and dimensioning of hydrogen transmission pipeline networks

This work considers the problem of the optimal design of an hydrogen transmission network. This design problem includes the topology determination and the pipelines dimensioning problem. We define a local search method that simultaneously looks for the least cost topology of the network and for the optimal diameter of each pipe. These two problems were generally solved separately these last years. The application to the case of development of future hydrogen pipeline networks in France has been conducted at the local, regional and national levels. We compare the proposed approach with another using Tabu search heuristic.     

Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.     

New horizons in sphere-packing theory, part II: lattice-based derivative-free optimization via global surrogates

Derivative-free algorithms are frequently required for the optimization of nonsmooth scalar functions in n dimensions resulting, for example, from physical experiments or from the statistical averaging of numerical simulations of chaotic systems such as turbulent flows. The core idea of all efficient algorithms for problems of this type is to keep function evaluations far apart until convergence is approached. Generalized pattern search (GPS) algorithms, a modern class of methods particularly well suited to such problems, accomplish this by coordinating the search with an underlying grid which is refined, and coarsened, as appropriate. One of the most efficient subclasses of GPS algorithms, known as the surrogate management framework (SMF; see Booker et al. in Struct Multidiscip Optim 17:1–13, 1999), alternates between an exploratory search over an interpolating function which summarizes the trends exhibited by existing function evaluations, and an exhaustive poll which checks the function on neighboring points to confirm or confute the local optimality of any given candidate minimum point (CMP) on the underlying grid. The original SMF algorithm implemented a GPS step on an underlying Cartesian grid, augmented with a Kriging-based surrogate search. Rather than using the n-dimensional Cartesian grid (the typical choice), the present work introduces for this purpose the use of lattices derived from n-dimensional sphere packings. As reviewed and analyzed extensively in Part I of this series (see Belitz, PhD dissertation, University of California, San Diego, 2011, Chap. 2), such lattices are significantly more uniform and have many more nearest neighbors than their Cartesian counterparts. Both of these facts make them far better suited for coordinating GPS algorithms, as demonstrated here in a variety of numerical tests.     

Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems

In this paper, we propose a generic approach to find compromise solutions for multiple-objective scheduling problems using metaheuristics. As an illustration, we present a new hybrid tabu search/variable neighbourhood search application of this approach for the solution of a bi-objective scheduling problem. Through numerical experiments we demonstrate its efficiency and effectiveness. We have confirmed that compromise programming with the tabu-VNS metaheuristic generates solutions that approach those of the known reference sets.     

An empirical study of a new metaheuristic for the traveling salesman problem

We present a deceptively simple, yet empirically powerful metaheuristic, called jump search, for solving traveling salesman problems that has been found to be more effective than tabu search on both random and benchmark test problems from the literature. While the underlying philosophy of jump search — applying local search from different starting points — has been discussed in the literature previously (using random starting points), the use of construction-based heuristic solutions has heretofore not been considered. Extensive empirical analysis shows the method to be surprisingly effective vis a vis a randomized strategy and in comparison with tabu search. The approach is quite robust and suggests that a systematic search among neighborhoods of good, not random, solutions provides distinct advantages. This suggests that further research be focused on better construction heuristics and hybrid schemes that incorporate jump search in, for example, tabu search.     

Coordinated search for an object hidden on the line

We consider the coordinated search problem faced by two searchers who start together at zero and can move at speed one to find an object symmetrically distributed on the line. In particular we fully analyze the case of the negative exponential distribution given by the density f(x) = e^−|x|μ/(2μ), μ > 0. The searchers wish to minimize the expected time to find the object and meet back together (with the object) at zero. We give necessary and sufficient conditions for the existence of an optimal search strategy when the target density is continuous and decreasing. We show that for the negative exponential distribution the optimal time is between 4.728μ and 4.729μ. A strategy with expected time in this interval begins with the searchers going in opposite directions and returning to the origin after searching up to successive distances 0.745μ, 2.11μ, 3.9μ, 6μ, 8.4μ,…. These results extend the theory of coordinated search to unbounded regions. It has previously been studied for objects hidden on a circle (by Thomas) and on an interval (by the author).     

Locally averaged Bayesian Dirichlet metrics for learning the structure and the parameters of Bayesian networks

The marginal likelihood of the data computed using Bayesian score metrics is at the core of score+search methods when learning Bayesian networks from data. However, common formulations of those Bayesian score metrics rely on free parameters which are hard to assess. Recent theoretical and experimental works have also shown that the commonly employed BDe score metric is strongly biased by the particular assignments of its free parameter known as the equivalent sample size. This sensitivity means that poor choices of this parameter lead to inferred BN models whose structure and parameters do not properly represent the distribution generating the data even for large sample sizes. In this paper we argue that the problem is that the BDe metric is based on assumptions about the BN model parameters distribution assumed to generate the data which are too strict and do not hold in real settings. To overcome this issue we introduce here an approach that tries to marginalize the meta-parameter locally, aiming to embrace a wider set of assumptions about these parameters. It is shown experimentally that this approach offers a robust performance, as good as that of the standard BDe metric with an optimum selection of its free parameter and, in consequence, this method prevents the choice of wrong settings for this widely applied Bayesian score metric.     

Proximity search heuristics for wind farm optimal layout

A heuristic framework for turbine layout optimization in a wind farm is proposed that combines ad-hoc heuristics and mixed-integer linear programming. In our framework, large-scale mixed-integer programming models are used to iteratively refine the current best solution according to the recently-proposed proximity search paradigm. Computational results on very large scale instances involving up to 20,000 potential turbine sites prove the practical viability of the overall approach.     

The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems

We study both weighted and unweighted unconstrained two-dimensional guillotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-search procedure introducing two strategies: Depth-first search and Hill-climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH /KD algorithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm uses also the KD algorithm for constructing new lower bounds and uses another one-dimensional knapsack for constructing refinement upper bounds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s algorithm (the unweighted case), and to Beasley's [2] approach (the weighted case) on some examples taken from the literature as well as randomly generated instances.     

A Feasible Algorithm for Locating Concave and Convex Zones of Interval Data and Its Use in Statistics-Based Clustering

Often, we need to divide n objects into clusters based on the value of a certain quantity x. For example, we can classify insects in the cotton field into groups based on their size and other geometric characteristics. Within each cluster, we usually have a unimodal distribution of x, with a probability density ρ(x) that increases until a certain value x ₀ and then decreases. It is therefore natural, based on ρ(x), to determine a cluster as the interval between two local minima, i.e., as a union of adjacent increasing and decreasing segments. In this paper, we describe a feasible algorithm for solving this problem.     

Multi-Criteria Optimization for Filter Design of L1 Adaptive Control

This paper considers the problem of optimal trade-off between robustness, in terms of time-delay margin, and performance of the $\mathcal {L}_{1}$ adaptive controller. Although the architectures of the $\mathcal {L}_{1}$ adaptive control theory can be systematically tuned to trade-off performance for robustness, there is no practical methodology as of today for the design of the underlying filter toward obtaining the optimal performance. The only available results in this direction were given in the form of linear matrix inequalities (LMIs), which are numerically tractable but tend to yield conservative results similar to what one would obtain by applying methods from robust control theory. This paper presents design schemes that are based on search for the design parameters of the filter. We consider filters of certain structures to satisfy the design specifications and investigate their properties over the space of the design parameters. To handle uncertain variables in the design specifications, greedy randomized algorithms are adopted to analyze and synthesize the system performance and robustness in the presence of uncertainties. In addition, we compute approximate sets of allowable design parameters in both analytical and numerical ways. Illustrative examples are provided to demonstrate that these methods can achieve the desired performance and robustness specifications with reasonable degree of conservatism.     

Regularity criteria for almost every function in Sobolev spaces

In this paper we determine the multifractal nature of almost every function (in the prevalence setting) in a given Sobolev or Besov space according to different regularity exponents. These regularity criteria are based on local Lp regularity or on wavelet coefficients and give a precise information on pointwise behavior.     

Random walks and local cuts in graphs

For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.     

Exact boundary observability for a kind of second order quasilinear hyperbolic systems and its applications

In this paper, by means of a constructive method based on the existence and uniqueness of the semi-global C² solution, we establish the local exact boundary observability for a kind of second order quasilinear hyperbolic systems. As an application, we obtain the one-sided local exact boundary observability for a kind of first order quasilinear hyperbolic systems of diagonal form with boundary conditions in which the diagonal variables corresponding to the positive eigenvalues and those corresponding to the negative eigenvalues are decoupled.     

A bias corrected nonparametric regression estimator

In this article, we propose a new method of bias reduction in nonparametric regression estimation. The proposed new estimator has asymptotic bias order h⁴, where h is a smoothing parameter, in contrast to the usual bias order h² for the local linear regression. In addition, the proposed estimator has the same order of the asymptotic variance as the local linear regression. Our proposed method is closely related to the bias reduction method for kernel density estimation proposed by Chung and Lindsay (2011). However, our method is not a direct extension of their density estimate, but a totally new one based on the bias cancelation result of their proof.     

Fast neighborhood search for two- and three-dimensional nesting problems

In this paper we present a new heuristic solution method for two-dimensional nesting problems. It is based on a simple local search scheme in which the neighborhood is any horizontal or vertical translation of a given polygon from its current position. To escape local minima we apply the meta-heuristic method Guided Local Search.     

Non-uniform dependence on initial data for the periodic Degasperis-Procesi equation

In this paper, we show that the solution map of the periodic Degasperis-Procesi equation is not uniformly continuous in Sobolev spaces Hs(T) for s>3/2. This extends previous result for s?2 to the whole range of s for which the local well-posedness is known. Our proof is based on the method of approximate solutions and well-posedness estimates for the actual solutions.