The minimum weight triangulation problem with few inner points

We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem can be solved in O(n³) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6^kn⁵logn) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k=O(logn). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points.     

Approximating the minimum weight steiner triangulation

We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. InO(n logn) time we can compute a triangulation withO(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better thanO(logn).     

Approximated algorithms for the minimum dilation triangulation problem

The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the sequential parameter optimization toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.     

Greedy heuristics for the diameter-constrained minimum spanning tree problem

The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly, we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9.     

A new asymmetric inclusion region for minimum weight triangulation

As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (?2b){(sqrt{2}beta)} -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (?2b){(sqrt{2}beta)} -skeleton is proposed and it runs in O(n^4/3+e+min{klogn, n²logn}){O(n^{4/3+epsilon}+min{kappa log n, n^2log n})} time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set.     

Improved convergent heuristics for the 0-1 multidimensional knapsack problem

At the end of the seventies, Soyster et al. (Eur. J. Oper. Res. 2:195–201, 1978) proposed a convergent algorithm that solves a series of small sub-problems generated by exploiting information obtained through a series of linear programming relaxations. This process is suitable for the 0-1 mixed integer programming problems when the number of constraints is relatively smaller when compared to the number of variables. In this paper, we first revisit this algorithm, once again presenting it and some of its properties, including new proofs of finite convergence. This algorithm can, in practice, be used as a heuristic if the number of iterations is limited. We propose some improvements in which dominance properties are emphasized in order to reduce the number of sub problems to be solved optimally. We also add constraints to these sub-problems to speed up the process and integrate adaptive memory. Our results show the efficiency of the proposed improvements for the 0-1 multidimensional knapsack problem.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

Constructive heuristics for the canister filling problem

The canister filling problem arises when optimizing the spent nuclear fuel repository in hard rock. It is shown the problem is NP-hard. Constructive heuristics followed by remove and reinsert local optimization are considered. Additionally, some theoretical insight on the algorithm operation is provided. Several variants of the algorithm are compared on random and realistic datasets. The obtained results have shown that constructive heuristics give satisfactory results for both random and realistic input data, although there is still some room for improvements.     

A hybridized tabu search approach for the minimum weight vertex cover problem

The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases.     

Hybrid heuristics for the maximum diversity problem

The maximum diversity problem presents a challenge to solution methods based on heuristic optimization. We undertake the development of hybrid procedures within the scatter search framework with the goal of uncovering the most effective designs to tackle this difficult but important problem. Our research revealed the effectiveness of adding simple memory structures (based on recency and frequency) to key scatter search mechanisms. Our extensive experiments and related statistical tests show that the most effective scatter search variant outperforms state-of-the-art methods.     

New heuristics for the maximum diversity problem

The maximum diversity problem (MDP) consists of identifying, in a population, a subset of elements, characterized by a set of attributes, that present the most diverse characteristics among the elements of the subset. The identification of such solution is an NP-hard problem. Some heuristics are available to obtain approximate solutions for this problem. In this paper, we propose different GRASP heuristics for the MDP, using distinct construction procedures and including a path-relinking technique. Performance comparison among related work and the proposed heuristics is provided. Experimental results show that the new GRASP heuristics are quite robust and are able to find high-quality solutions in reasonable computational times. G.C. Silva’s work sponsored by CAPES MSc scholarship. L.S. Ochi’s work sponsored by CNPq research grants 304103/2003-9 and 550059/2005-9. S.L. Martins’s work sponsored by CNPq research grant 475124/03-0. A. Plastino’s work sponsored by CNPq research grants 300879/00-8 and 475124/03-0.     

Local search heuristics for the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s also have a large number of applications. We consider several known neighborhoods, generalize them and propose some new ones. The heuristics are evaluated both theoretically and experimentally and dominating algorithms are selected. We also demonstrate that a combination of two neighborhoods may yield a heuristics which is superior to both of its components.     

Constructive heuristics for the uncapacitated continuous location-allocation problem

The multisource location-allocation problem in continuous space is investigated. Two constructive heuristic techniques are proposed to solve this problem. Both methods are based on designing suitable schemes for the generation of the initial solutions. The first considers the furthest distance rule and is enhanced by schemes borrowed from tabu search such as constructing the forbidden regions and freeing strategy. The second considers the discrete solutions found when solving the p-median problem. Some results on existing test problems are presented.     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem

Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.     

An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions

We present a polynomial algorithm with time complexity O(n ⁵) and approximation ratio 4/3 (plus some additive constant) for the minimum 2-peripatetic salesman problem in a complete n-vertex graph with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1, 2)-min-2w). This result improves the available algorithm for this problem with approximation ratio 11/7.     

Parallel hybrid heuristics for the permutation flow shop problem

This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by Fm|prmu|C _max. In the permutational scenario, the sequence of jobs has to remain the same in all machines. The Flowshop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for medium and large scale instances, high-quality heuristics are needed to find good solutions in reasonable time. We propose and analyse parallel hybrid search methods that fully use the computational power of current multi-core machines. The parallel methods combine a memetic algorithm (MA) and several iterated greedy algorithms (IG) running concurrently. Two test scenarios were included, with short and long CPU times. The tests were conducted on the set of benchmark instances introduced by Taillard (Eur. J. Oper. Res. 64:278?C285, 1993), commonly used to assess the performance of new methods. Results indicate that the use of the MA to manage a pool of solutions is highly effective, allowing the improvement of the best known upper bound for one of the instances.