A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

We present a 0.5-approximation algorithm for the Multiple Knapsack Problem (MKP). The algorithm uses the ordering of knapsacks according to the nondecreasing of size and the two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on A × B (here A is the set of knapsacks and B is the set of indivisible items). Based on each of these lexicographic orderings, the algorithm creates a feasible solution to the MKP by looking through the pairs (a, b) ∈ A × B in the corresponding order and placing item b into knapsack a if this item is not placed yet and there is enough free space in the knapsack. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has runtime O(mn) (without sorting), where mand n are the sizes of A and B correspondingly.     

Multifactorial global search algorithm in the problem of optimizing a reactive force field

We present a new multifactorial global search algorithm (MGSA) and check the operability of the algorithm on the Michalewicz and Rastrigin functions. We discuss the choice of an objective function and additional search criteria in the context of the problem of reactive force field (ReaxFF) optimization and study the ranking of the ReaxFF parameters together with their impact on the objective function.     

A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version shifting bottleneck procedure (SBP) algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological-sequence algorithm is proposed to decompose the PMJSS problem in a set of single-machine scheduling (SMS) and/or parallel-machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.     

Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

A partial Latin square (PLS) is a partial assignment of n symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient \((p,\infty )\)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for \(p\in \{1,2,3\}\). The running time of the algorithm is \(O(n^{p+1})\). We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with \(p\le 2\). The proposed Trellis-neighborhood search algorithm runs in \(O(n^{3.5})\) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with \((p,\infty )\)-neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

Algorithms with high order convergence speed for blind source extraction

A rigorous convergence analysis for the fixed point ICA algorithm of Hyvärinen and Oja is provided and a generalization of it involving cumulants of an arbitrary order is presented. We consider a specific optimization problem OP(p), p>3, integer, arising from a Blind Source Extraction problem (BSE) and prove that every local maximum of OP(p) is a solution of (BSE) in sense that it extracts one source signal from a linear mixture of unknown statistically independent signals. An algorithm for solving OP(p) is constructed, which has a rate of convergence p?1.     

Packing circles in the smallest circle: an adaptive hybrid algorithm

The circular packing problem (CPP) consists of packing n circles C _i of known radii r _i , i∈N={1,?…,?n}, into the smallest containing circle ?. The objective is to determine the coordinates (x _i ,?y _i ) of the centre of C _i , i∈N, as well as the radius r and centre (x,?y) of ?. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

A Lagrangian search method for the <Emphasis Type="Italic">P</Emphasis>-median problem

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.     

The worst case analysis of strong knapsack facets

In this paper we identify strong facet defining inequalities for the master knapsack polytope. Our computational experiments for small master knapsack problems show that 1 / k-facets for small values of k (\(k\le 4\)) are strong facets for the knapsack polytope. We show that this finding is robust by proving that the removal of these facets from the master knapsack polytope significantly weakens the resulting relaxation in the worst case. We show that the 1 / k-facets for \(k = 1\) are the strongest in that their removal from the master knapsack polytope weakens the relaxation by a factor of 3 / 2 in the worst case. We then show that the 1 / k-facets with \(k = 3\) or 4 are the next strongest. We also show that the strength of the 1 / k-facets weakens as k grows and that the 1 / k-facets with k even are stronger than the 1 / k-facets with k odd.     

An improved branch and bound algorithm for a strongly correlated unbounded knapsack problem

An unbounded knapsack problem (KP) was investigated that describes the loading of items into a knapsack with a finite capacity, W, so as to maximize the total value of the loaded items. There were n types of an infinite number of items, each type with a distinct weight and value. Exact branch and bound algorithms have been successfully applied previously to the unbounded KP, even when n and W were very large; however, the algorithms are not adequate when the weight and the value of the items are strongly correlated. An improved branching strategy is proposed that is less sensitive to such a correlation; it can therefore be used for both strongly correlated and uncorrelated problems.     

Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ, μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.     

A stable algorithm for numerical evaluation of Hankel transforms using Haar wavelets

The purpose of the paper is to propose a stable algorithm for the numerical evaluation of the Hankel transform F _n (y) of order n of a function f(x) using Haar wavelets. The integrand \(\sqrt x f(x)\) is replaced by its wavelet decomposition. Thus representing F _n (y) as a series with coefficients depending strongly on the local behavior of the function \(\sqrt x f(x)\), thereby getting an efficient and stable algorithm for their numerical evaluation. Numerical evaluations of test functions with known analytical Hankel transforms illustrate the proposed algorithm.     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.     

A computational study of hybrid approaches of metaheuristic algorithms for the cell formation problem

In this paper we solve the 0–1 cell formation problem where the number of cells is fixed a priori and where the objective is to maximize the overall efficiency of a production system by grouping together machines providing service to similar parts into a subsystem (denoted cell). Three different methods are introduced and compared numerically. The first local search method is an implementation of simulated annealing (SA) where the definition of the neighbourhood is specific to the application and requires using a diversification and intensification strategies. The second local search method is an adaptive simulated annealing method where the neighbourhood is selected randomly at each iteration. The procedure is adaptive in the sense that the probability of selecting a neighbourhood is updated during the process. The third method is a hybrid method (HM) of a population-based method and a local search method. To improve the solution obtained with HM, we apply a SA method afterward. The best variants are very efficient to solve the 35 benchmark problems commonly used in the literature.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

A short note on Lq theory for Stokes problem with a pressure-dependent viscosity

We study higher local integrability of a weak solution to the steady Stokes problem. We consider the case of a pressure- and shear-rate-dependent viscosity, i.e., the elliptic part of the Stokes problem is assumed to be nonlinear and it depends on p and on the symmetric part of a gradient of u, namely, it is represented by a stress tensor T (Du, p):= v(p, |D|²)D which satisfies r-growth condition with r ∈ (1, 2]. In order to get the main result, we use Calderón-Zygmund theory and the method which was presented for example in the paper Caffarelli, Peral (1998).     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.