No abstract available.

The title of t,his talk is too broad to be covered in one day nnd I realize that there are many experts of different backgrounds, 'as well as students, in the audience.Thus, I have selected a fern basic concepts and two numerical examples to supplement my slides.

Stochastic hill-climbing algorithms, particularly simulated annealing (SA) and threshold acceptance (TA), have become very popular for global optimization applications. Typical implementations of SA or TA use monotone temperature or threshold schedules, and are not formulated to accommodate practical time limits. We present a new threshold acceptance strategy called Old Bachelor Acceptance (OBA), which has three distinguishing features: (i) it is specifically motivated by the practical requirement of optimization within a prescribed time bound, (ii) the threshold schedule is self-tuning, and (iii) the threshold schedule is non-monotone, with threshold values even allowed to become negative. The standard implementation of the TA method of Dueck and Scheuer is a special case of OBA. Experiments using several classes of symmetric traveling salesman problem instances show that OBA can outperform previous hill-climbing methods for time-critical optimizations. A number of directions for future work are suggested. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimal algorithms due to Prim (1957) and Dijkstra (1959). Previous "shallow-light" techniques are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing.>

Graph partitioning is crucial in multiple-chip design, floorplanning and mapping large logic networks into multiple FPGA's. Replication logic can be used to improve the partitioning. Given a network G with only two-pin nets and a pair of nodes s and t to be separated, we introduce a replication graph and an O(mn log(n/sup 2//m)) algorithm for optimum partitioning with replication and without size constraints, where m and n denote the number of nets and the number of nodes in G, respectively. In VLSI designs, each partition has size constraints and the given network contains multiple-pin nets. A heuristic extension is adopted to construct replication graphs with multiple-pin nets. Then we use a directed Fiduccia-Mattheyses algorithm in the constructed replication graph to solve the replication cut problem with size constraints.>

Multi-chip module (MCM) technology has become an important means to package high performance systems. An important task during the packaging process is to check for possible open, short, and high resistance faults in the wiring networks of the bare MCM substrates, which is called substrate testing. After examining several substrate testing methodologies, we find that multi-probe or k-probe testers are cost-effective for substrate testing. However, the testing speed of this method is not high; hence, we focus on improving the throughput by reducing the number of tests and by deriving good probe routes. For test size reduction, we propose a routing tree model to capture the wiring structure of a given net; then by taking advantage of the routing tree, we generate a minimum number of tests while ensuring complete open fault coverage. Our algorithm reduces the number of tests by up to 50% compared to that of previous approaches. Given a routing tree with its node degree bounded by a constant, our test generation algorithm runs in linear time with respect to the number of leaves of the tree. For probe route scheduling, we observe that in order to obtain a balanced and efficient scheduling, the routes of different probes must be considered simultaneously, which motivates our Multi-Dimensional Traveling Salesman Problem (MDTSP) formulation. Our package has been installed on existing substrate testers and has achieved encouraging results.>

A block-oriented programmable design with switching network interconnect is proposed for fast turn-around, low manufacturing cost, and layout-independent high-speed systems. We introduce the architecture and investigate the constraints and properties originated from the architecture. We show that routability is the most crucial concern for a successful design, and propose objective functions as well as algorithms for switching network optimization. The mapping for the circuits is performed by partitioning, placement, and routing using a maximum matching method. The integration of the whole system demonstrates excellent results in terms of circuit usage.>

We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach that optimally solves the robust path planning problem using an efficient network flow formulation. Our algorithm represents a significant departure from conventional shortest-path or graph search based methods; it not only handles environments with solid polygonal obstacles, but also generalizes to arbitrary cost maps that may arise in modeling incomplete or uncertain knowledge of the environment. Simple extensions allow us to address higher dimensional problem instances and minimum-surface computations; the latter is a result of independent interest. We use an efficient implementation to exhibit optimal path-planning solutions for a variety of test problems. The paper concludes with open issues and directions for future work.>

The k-probe testing methodology is an effective approach to detect open and short faults in MCM substrates. An algorithm which generates the minimum number of tests for complete open fault coverage is proposed. For k equals two, the algorithm is able to reduce the test size by up to 50% compared with that generated by an ordinary approach. A multidimensional traveling salesman problem formulation is developed to optimize probe routes. The approach has been tested on substrate testers and has achieved excellent results.>

In the layout stage of VLSI and printed circuit board (PCB) design, after all circuit modules (rectangular) are placed, it is possible to flip the modules so as to reduce the total net length. The authors formulate the orientation of modules as a graph problem and prove it to be NP-complete. The orientation problem is shown to be equivalent to finding a minimum cut of a graph with some arcs of negative capacities. In many cases, the graph can be decomposed into subgraphs to reduce the search space for optimum orientation. Experiments with real cases show that module orientation reduces the total net length and improves the routability.>

Abstract The problem of compacting a programmable logic array is formulated as the following graph problem. Given a red‐edge bipartite graph, how to add maximum number of independent green edges such that there are no cycles formed by alternating red and green edges. For this NP‐complete problem, we present a polynomial heuristic algorithm which gives an optimum solution when the red bipartite graph satisfies certain conditions, e.g., a tree. When the bipartite graph does not satisfy these conditions, the heuristic algorithm gives a solution with worst‐case error bound. For a red bipartite graph with given cardinality, we give a tight upper bound on the number of green edges.

Given n records stored alphabetically on a tape, any comparison search procedure can be characterized by a binary tree. The complete binary tree (binary search) uses the minimum number of comparisons but not the minimum number of movements. The linear binary tree (sequential search) uses the minimum number of movements but not the minimum number of comparisons. A tape-optimal tree is a tree which minimizes the total cost of comparisons and movements. The tape-optimal tree is a “hybrid” of the linear tree and the complete binary tree, and is characterized for arbitrary n.

The folding of programmable logic array (PLA) is considered. We develop a heuristic algorithm for optimal block folding. The algorithm is based on the column intersection graph associated with the PLA. Then the techniques of graph partitioning and two-objective linear programming are applied. Test results will be demonstrated to show the effectiveness of the algorithm.

This paper considers the computation of matrix chain products of the form $M_1 \times M_2 \times \cdots \times M_{n - 1} $. If the matrices are of different dimensions, the order in which the matrices are computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. Some theorems about an optimum order of computing the matrices have been presented in Part I [SIAM J. Comput., 11 (1982), pp. 362–373]. Based on those theorems, an $O(n\log n)$ algorithm for finding the optimum order is presented here.

This paper considers the computation of matrix chain products of the form $M_1 \times M_2 \times \cdots \times M_{n - 1} $. If the matrices are of different dimensions, the order in which the product is computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. We present some theorems about an optimum order of computing the matrices. Based on these theorems, an $O(n\log n)$ algorithm for finding an optimum order will be presented in Part II.

This paper considers the computation of matrix chain products of the form M1 × M2 ×...× Mn-1. If the matrices are of different dimensions, the order in which the matrices are computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. We present some theorems about an optimum order of computing the matrices. Based on these theorems, an O(n log n) algorithm for finding the optimum order is presented.

A recently published algorithm shows how to assign modules to a two-processor computer system with distributed execution so as to minimize the total of execution costs and interprocessor communication costs. In this paper we consider the same problem except that one processor has limited memory capacity. Although this problem is NP-complete, techniques based on the Gomory–Hu tree from network flow theory can be applied to instances of the problem to obtain a reduction in complexity. A new technique based on a graph called the inclusive cut graph is shown to be an even more powerful tool. These two techniques can solve some instances of the problem completely; still others are reduced sufficiently to be susceptible to enumerative techniques. In the worst case, the techniques yield no reduction in problem size.

Abstract Decomposition algorithms have been proposed for finding the shortest paths between all pairs of nodes in a large network. The central idea is to treat the large network as several small networks overlapping each other. When the small networks overlap each other linearly, algorithms have been proposed to treat each small network individually. The present note treats the case of small networks overlapping each other like a tree.

We represent a binary tree by the level numbers of its leaves from left to right. Thus every binary tree of n leaves corresponds to a sequence of n numbers. We first give the necessary and sufficient conditions for a sequence to represent a binary tree; then we give an algorithm for generating all the feasible sequences lexicographically as a list. Also, algorithms are developed to determine the position of a given sequence, or to generate the sequence of a given position. Finally, it is shown that the average time per sequence generated is constant (independent of the length of the sequence).

Given a set of nodes $N_i (i = 1,2, \cdots ,n)$ which may represent cities and a set of requirements $r_{ij} $ which may represent the number of telephone calls between $N_i $ and $N_j $, the problem is to build a spanning tree connecting these n nodes such that the total cost of communication of the spanning tree is a minimum among all spanning trees. The cost of communication for a pair of nodes is $r_{ij} $ multiplied by the sum of the distances of arcs which form the unique path connecting $N_i $ and $N_j $ in the spanning tree. Summing over all $\begin{pmatrix} n \\ 2 \ \end{pmatrix}$ pairs of nodes, we have the total cost of communication of the spanning tree. Note that the problem is different from the minimum spanning tree problem solved by Kruskal and Prim.