On heuristics for minimum length rectilinear partitions

The problem of partitioning a rectilinear figure into rectangles with minimum length is NP-hard and has bounded heuristics. In this paper we study a related problem,Elimination Problem (EP), in which a rectilinear figure is partitioned into a set of rectilinear figures containing no concave vertices of a fixed direction with minimum length. We show that a heuristic for EP within a factor of 4 from optimal can be computed in timeO(n ²), wheren is the number of vertices of the input figure, and a variant of this heuristic, within a factor of 6 from optimal, can be computed in timeO(n logn). As an application, we give a bounded heuristic for the problem of partitioning a rectilinear figure into histograms of a fixed direction with minimum length. An auxiliary result is that an optimal rectangular partition of a monotonic histogram can be computed in timeO(n ²), using a known speed-up technique in dynamic programming.     

A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

Load-balancing spatially located computations using rectangular partitions

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoffs.     

On greedy heuristics for steiner minimum trees

We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to3/2. We also propose a new conjecture.Supported in part by the National Science Foundation under Grant CCR-9208913.     

List partitions

By definition, apartition of a list is a division of that list into nonempty contiguous segments. Many programming and operations research problems can be specified in terms of list partitions, and we present a hierarchy of theorems for deriving programs from such specifications. Throughout, reasoning is conducted in an equational style using the calculus for program synthesis developed by Bird and Meertens.Supported by a BP research studentship.     

On Exact Solutions for the Rectilinear Steiner Tree Problem Part I: Theoretical Results

The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithms for this problem are based on dynamic programming and have a running time of O(n ² . . . 2.62 ⁿ ) (Ganley and Cohoon), resp. (Smith). The first algorithm can solve problems of size 27, the second one is highly impractical because of the large constant in the exponent. The best implementations perform poorly even on small problem instances; the best practical results can be reached using a Branch \& Bound approach (Salowe and Warme); this implementation can solve random problems of size 35 within a day, while the dynamic programming approach of Ganley and Cohoon can handle only 27 point examples. In this paper we improve the theoretical worst-case time bound to O(n ² . . . 2.38 ⁿ ) , for random problem instances we prove a running time of α ⁿ with a constant α < 2 . We have implemented our algorithms and can now solve problems of 40 points in a day using a provably good dynamic programming approach, and can solve problems of 55 points with a Branch \& Bound strategy. For exponential-time algorithms, this is an enormous improvement. Received April 2, 1997; revised January 5, 1998.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

The contour problem for rectilinear polygons

The union of a set of p, not necessarily disjoint, rectilinear polygons in the plane determines a set of disjoint rectilinear polygons. We present an O(n log n + e) time and O(n) space algorithm to compute the edges of the disjoint polygons, that is, the contour, where n is the total number of vertices in the original polygons and e the total number in the resulting set. This time-and space-optimal algorithm uses the scan-line paradigm as in two previous approaches to this problem for rectangles, but requires a simpler data structure. Moreover, if the given rectilinear polygons are rectilinear convex, the space requirement is reduced to O(p).     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Proximity problems for points on a rectilinear plane with rectangular obstacles

We consider the following four problems for a setS ofk points on a plane, equipped with the rectilinear metric and containing a setR ofn disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles inR): (a) find aclosest pair of points inS, (b) find anearest neighbor for each point inS, (c) compute the rectilinearVoronoi diagram ofS, and (d) compute a rectilinearminimal spanning tree ofS. We describeO ((n+k) log(n+k))-time sequential algorithms for (a) and (b) based onplane-sweep, and the consideration of geometrically special types of shortest paths, so-calledz-first paths. For (c) we present anO ((n+k) log(n+k) logn)-time sequential algorithm that implements a sophisticateddivide-and-conquer scheme with an addedextension phase. In the extension phase of this scheme we introduce novel geometric structures, in particular so-calledz-diagrams, and techniques associated with the Voronoi diagram. Problem (d) can be reduced to (c) and solved inO ((n+k) log(n+k) logn) time as well. All our algorithms arenear-optimal, as well as easy to implement. An extended abstract appeared inProc. 13th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Bombay, 1993, Springer-Verlag, pp. 218–227. Sumanta Guha was supported in part by a UW-Milwaukee Graduate School Research Committee Award. Ichiro Suzuki was supported in part by the National Science Foundation under Grants CCR-9004346 and IRI-9307506, the Office of Naval Research under Grant N00014-94-1-0284, and an endowed chair supported by Hitachi Ltd. at the Faculty of Engineering Science, Osaka University.     

On the entropy of partitions in product MV algebras

 Generalizing the entropy of fuzzy partitions, the entropy of a partition in recently introduced product MV algebra has been studied. The least common refinement of two partitions is defined and the algebraic properties of the entropies and conditional entropies are examined.     

On numerically decipherable codes and their homophonic partitions

We investigate the homophonic partitions of numerically decipherable (ND) codes in relationship with the notion of multivalued encodings. Moreover, we present a new class of codes, the class of homophonically decipherable (HD) codes, studying their Kraft-McMillan sum.     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming

We present an exact optimization algorithm for the Orienteering Problem with Time Windows (OPTW). The algorithm is based on bi-directional and bounded dynamic programming with decremental state space relaxation. We compare different strategies proposed in the literature to guide decremental state space relaxation: our experiments on instances derived from the literature show that there is no dominance between these strategies. We also propose a new heuristic technique to initialize the critical vertex set and we provide experimental evidence of its effectiveness.     

A linear time algorithm for the minimum Weighted Feedback Vertex Set on diamonds

Given an undirected and vertex weighted graph G, the Weighted Feedback Vertex Problem (WFVP) consists in finding a subset F⊆V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs is known to be NP-hard. In this paper we introduce a new class of graphs, namely the diamond graphs, and give a linear time algorithm to solve WFVP on it.     

Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints

In this paper, the problem of lot-sizing and scheduling of multiple product types in a capacitated flow shop with availability constraints for multi-period planning horizon is considered. In many real production systems, machines may be unavailable due to breakdowns or preventive maintenance activities, thus integrating lot-sizing and scheduling with maintenance planning is necessary to model real manufacturing conditions. Two variants are considered to deal with the maintenance activities. In the first, the starting times of maintenance tasks are fixed, whereas in the second one, maintenance must be carried out in a given time window. A new mixed-integer programming (MIP) model is proposed to formulate the problem with sequence-dependent setups and availability constraints. The objective is to find a production and preventive maintenance schedule that minimizes production, holding and setup costs. Three MIP-based heuristics with rolling horizon framework are developed to generate the integrated plan. Computational experiments are performed on randomly generated instances to show the efficiency of the heuristics. To evaluate the validity of the solution methods, problems with different scales have been studied and the results are compared with the lower bound. Computational experiments demonstrate that the performed methods have good-quality results for the test problems.