An efficient algorithm for the three-guard problem

Given a simple polygon P with two vertices u and v, the three-guard problem asks whether three guards can move from u to v such that the first and third guards are separately on two boundary chains of P from u to v and the second guard is always kept to be visible from two other guards inside P. It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from u to v and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in O(nlogn) time, and if so generate a walk in O(nlogn+m) time, where n denotes the number of vertices of P and the size of the optimal walk. This improves upon the previous time bounds O(n²) and O(n²logn), respectively. Moreover, our results can be used to solve other more sophisticated geometric problems.     

An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

An efficient algorithm for the complete set partitioning problem

The complete set partitioning problem is the well known set partitioning problem with all possible nonzero binary columns in the constraint matrix. A highly specialized enumerative algorithm, which never requires the explicit maintenance of the constraint matrix, is presented. Computational results, with data reflecting a particular corporate tax payment scenario that can be modelled as a complete set partitioning problem, is also given.     

An efficient algorithm for the minimum capacity cut problem

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n ⁴) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.     

An efficient memetic algorithm for the graph partitioning problem

We consider the component testing problem of a device that is designed to perform a mission consisting of a random sequence of phases with random durations. Testing is done at the component level to attain desired levels of mission reliability at minimum cost. The components fail exponentially where the failure rate depends on the phase of the mission. The reliability structure of the device involves a series connection of nonidentical components with different failure characteristics. The optimal component testing problem is formulated as a semi-infinite linear program. We present an algorithmic procedure to compute optimal test times based on the column generation technique, and illustrate it with numerical examples.     

An efficient evolutionary algorithm for the ring star problem

This paper addresses the ring star problem (RSP). The goal is to locate a cycle through a subset of nodes of a network aiming to minimize the sum of the cost of installing facilities on the nodes on the cycle, the cost of connecting them and the cost of assigning the nodes not on the cycle to their closest node on the cycle. A fast and efficient evolutionary algorithm is developed which is based on a new formulation of the RSP as a bilevel programming problem with one leader and two independent followers. The leader decides which nodes to include in the ring, one follower decides about the connections of the cycle and the other follower decides about the assignment of the nodes not on the cycle. The bilevel approach leads to a new form of chromosome encoding in which genes are associated to values of the upper level variables. The quality of each chromosome is evaluated by its fitness, by means of the objective function of the RSP. Hence, in order to compute the value of the lower level variables, two optimization problems are solved for each chromosome. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time. A study to select the best configuration of the algorithm is presented. The algorithm is tested on a set of benchmark problems providing very accurate solutions within short computing times. Moreover, for one of the problems a new best solution is found.     

An efficient algorithm for solving the discrete minisum problem

For a simple nonsmooth minimization problem, the discrete minisum problem, an efficient hybrid method is presented. This method consists of an ‘inner algorithm’ (Newton method) for solving the necessary optimality conditions and a gradient-type ‘outer algorithm’. By this way we combine the large convergence area of the gradient technique with the fast final convergence of the Newton method.     

An efficient algorithm for a job shop problem

We study the problem of minimizing makespan in a two-machine job shop with unit processing time operations. An efficient algorithm with respect to a succinct encoding of the problem instances is proposed. The algorithm is an improvement of earlier algorithms proposed for the problem by Brucker [1,2], Hefetz and Adiri [7], and Timkovskiy [15]. The idea behind the algorithm has the potential of extension to job shops with parallel machines.This research is supported in part by NSERC Grants A4619, OGP0105675, OGP0104900, General Motors of Canada, and the Manufacturing Research Corporation of Ontario.     

An efficient local search algorithm for the winner determination problem

Combinatorial auction, which allows bidders to bid on combinations of items, is an important type of market mechanism. The winner determination problem (WDP) has extensive applications in combinatorial auctions, and attracts more and more attention due to its strong relevance to business. However, this problem is intractable in theory as it has been proven to be NP-hard, and is also a challenging combinatorial optimization problem in practice. This paper is devoted to designing an efficient heuristic algorithm for solving the WDP. This proposed heuristic algorithm dubbed abcWDP is based on an effective yet simple local search framework, and equipped with three novel strategies, i.e., configuration checking, free-bid exploiting, and pseudo-tie mechanism. Extensive computational experiments on a broad range of benchmarks demonstrate that abcWDP performs much better than state-of-the-art algorithms and CPLEX in terms of both revenue and running time. More encouragingly, our abcWDP algorithm as a sequential algorithm even achieves better computational results than the multi-thread implemented algorithm \(\hbox {CA}_\mathrm{RA}\), which confirms its efficiency.     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.     

An efficient heuristic algorithm for the capacitated p-\! median problem

The capacitated $p$ -median problem (CPMP) is one of the well-known facility-location problems. The objective of the problem is to minimize total cost of locating a set of capacitated service points and allocating a set of demand points to the located service points, while the total allocated demand for each service point is not be greater than its capacity limit. This paper presents an efficient heuristic algorithm based on the local branching and relaxation induced neighborhood search methods for the CPMP. The proposed algorithm is a heuristic technique that utilizes a general mixed integer programming solver to explore neighborhoods. The parameters of the proposed algorithm are tuned by design of experiments. The proposed method is tested on a large set of benchmark instances. The results show that the method outperforms the best method found in the literature.     

An algorithm and efficient data structures for the binary knapsack problem

A branch-and-bound algorithm for the binary knapsack problem is presented which uses a combined stack and deque for storing the tree and the corresponding LP-relaxation. A reduction scheme is used to reduce the problem size. The algorithm was implemented in FORTRAN. Computational experience is based on 600 randomly generated test problems with up to 9000 zero-one variables. The average solution times (excluding an initial sorting step) increase linearly with problem size and compare favorably with other codes designed to solve binary knapsack problems.     

An efficient tabu algorithm for the single row facility layout problem

The general goal of the facility layout problem is to arrange a given number of facilities to minimize the total cost associated with the known or projected interactions between them. One of the special classes of the facility layout problem is the Single Row Facility Layout Problem (SRFLP), which consists of finding an optimal linear placement of rectangular facilities with varying dimensions on a straight line. This paper first presents and proves a theorem to find the optimal solution of a special case of SRFLP. The results obtained by this theorem prove to be very useful in reducing the computational efforts when a new algorithm based on tabu search for the SRFLP is proposed in this paper. Computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

An efficient and numerically correct algorithm for the 2D convex hull problem

An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns.     

An efficient algorithm for sparse null space basis problem using ABS methods

We propose a way to use the Markowitz pivot selection criterion for choosing the parameters of the extended ABS class of algorithms to present an effective algorithm for generating sparse null space bases. We explain in detail an efficient implementation of the algorithm, making use of the special MATLAB 7.0 functions for sparse matrix operations and the inherent efficiency of the ANSI C programming language. We then compare our proposed algorithm with an implementation of an efficient algorithm proposed by Coleman and Pothen with respect to the computing time and the accuracy and the sparsity of the generated null space bases. Our extensive numerical results, using coefficient matrices of linear programming problems from the NETLIB set of test problems show the competitiveness of our implemented algorithm.