Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Preprocessing of rotamers for protein design calculations

We have developed a process that significantly reduces the number of rotamers in computational protein design calculations. This process, which we call Vegas, results in dramatic computational performance increases when used with algorithms based on the dead-end elimination (DEE) theorem. Vegas estimates the energy of each rotamer at each position by fixing each rotamer in turn and utilizing various search algorithms to optimize the remaining positions. Algorithms used for this context specific optimization can include Monte Carlo, self-consistent mean field, and the evaluation of an expression that generates a lower bound energy for the fixed rotamer. Rotamers with energies above a user-defined cutoff value are eliminated. We found that using Vegas to preprocess rotamers significantly reduced the calculation time of subsequent DEE-based algorithms while retaining the global minimum energy conformation. For a full boundary design of a 51 amino acid fragment of engrailed homeodomain, the total calculation time was reduced by 12-fold.     

Exact rotamer optimization for protein design

Computational methods play a central role in the rational design of novel proteins. The present work describes a new hybrid exact rotamer optimization (HERO) method that builds on previous dead-end elimination algorithms to yield dramatic performance enhancements. Measured on experimentally validated physical models, these improvements make it possible to perform previously intractable designs of entire protein core, surface, or boundary regions. Computational demonstrations include a full core design of the variable domains of the light and heavy chains of catalytic antibody 48G7 FAB with 74 residues and 10(128) conformations, a full core/boundary design of the beta1 domain of protein G with 25 residues and 10(53) conformations, and a full surface design of the beta1 domain of protein G with 27 residues and 10(60) conformations. In addition, a full sequence design of the beta1 domain of protein G is used to demonstrate the strong dependence of algorithm performance on the exact form of the potential function and the fidelity of the rotamer library. These results emphasize that search algorithm performance for protein design can only be meaningfully evaluated on physical models that have been subjected to experimental scrutiny. The new algorithm greatly facilitates ongoing efforts to engineer increasingly complex protein features.     

Bone Dimensional Change Following Immediate Implant Placement in Posterior Teeth with CBCT: A 6-Month Prospective Clinical Study

This prospective clinical study aimed to evaluate the peri-implant hard tissue dimensional change at 6 months of immediate implant placement with bone graft materials in the posterior area using cone-beam computed tomography (CBCT). Twelve dental implants were placed concurrently following tooth extraction in the posterior area and filled with xenograft particles. The CBCT images were taken immediately after surgical procedures and then at 6 months follow-up. To evaluate the hard tissue changes, the vertical and horizontal bone thickness were analyzed and measured using ImageJ software. Paired t-test or Wilcoxon match-pair signed-rank test was done to analyze the changes of hard tissue values at the same level between immediately and 6 months following immediate implant placement. Independent t-test or Mann–Whitney U test was used to analyze the dimensional change in the vertical and horizontal direction in buccal and lingual aspects. The level of significance was set at p value = 0.05. All implants were successfully osseointegrated. At 6 months follow-up, the vertical bone change at the buccal aspect was −0.69 mm and at the lingual aspect −0.39 mm. For horizontal bone thickness, the bone dimensional changes at 0, 1, 5, and 9 mm levels from the implant platform were −0.62 mm, −0.70 mm, −0.24 mm, and −0.22 mm, respectively. A significant bone reduction was observed in all measurement levels during the 6 months after implant placement (p value < 0.05). It was noted that even with bone grafting, a decrease in bone thickness was seen following the immediate implant placement. Therefore, this technique can be an alternative method to place the implant in the posterior area.     

孤对电子与赤道取向——sp3d杂化轨道中电子对排列的一种有趣现象

揭示了一种有趣的分子结构现象：在ABn型多原子分子或离子结构中,若中心原子A的轨道杂化方式为sp3d,且价层有孤电子对时,孤电子对总是呈三角双锥的赤道取向;若分子中A、B原子间有重键时,B原子也总是呈赤道取向。探讨了这一现象的内在原因,并通过归纳法论证了这一规律。     

Pole placement controllers for linear time-delay systems with commensurate point delays

This paper investigates the exact and approximate spectrum assignment properties associated with realizable output-feedback pole-placement type controllers for single-input single-output linear time-invariant time-delay systems with commensurate point delays. The controller synthesis problem is discussed through the solvability of a set of coupled diophantine equations of polynomials. An extra complexity is incorporated to the above design to cancel extra unsuitable dynamics being generated when solving the above diophantine equations. Thus, the complete controller tracks any arbitrary prefixed (either finite or delaydependent) closed-loop spectrum. However, if the controller is simplified by deleting the above mentioned extra complexity, then the robust stability and approximated spectrum assignment are still achievable for a certain sufficiently small amount of delayed dynamics. Finally, the approximate spectrum assignment and robust stability problems are revisited under plant disturbances if the nominal controller is maintained. In the current approach, the finite spectrum assignment is only considered as a particular case to the designer‘s choice of a (delay-dependent) arbitrary spectrum assignment objective.     

Parallelizing Tabu Search on a Cluster of Heterogeneous Workstations

In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation.     

$\Phi $-functions for complex 2D-objects

Within two-dimensional cutting and packing problems with irregular shaped objects, the concept of -functions has been proven to be very helpful for several solution approaches. In order to construct such -functions a previous work, in which so-called primary objects are considered, is continued. Now -functions are constructed for pairs of objects which can be represented as a finite combination (union, intersection, complement) of primary objects which allows the handling of arbitrary shaped objects by appropriate approximations of sufficient accuracy.Received: October 2002, Revised: October 2003, AMS classification: 65K05, 90C26, 90B06All correspondence to: Guntram Scheithauer     

A new multiobjective allocator of capacitor banks and distributed generations using a new investigated differential evolution

This article has investigated a new multiobjective allocation of optimal sizing and sitting of distributed generation (DG) units and capacitor banks in simultaneous mode to improve reliability and reduce energy losses. The proposed method consists of four objectives, that is, cost of energy not supplied, system average interruption duration index, costs of energy loss and investment. A novel structure differential evolution has been suggested to solve this nonlinear complex problem and its results are compared with related values of genetic algorithm and simple differential evolutionary algorithm. In addition to the novel objective function, the other contribution of this article is proposing a new model for load and energy cost. Three types of DGs, that is, wind turbine, solar cell, and diesel generator have been used in placement process. To verify the comprehensiveness of the proposed function, three scenarios have been introduced: scenario i: first, placement of DGs, then capacitor banks, scenario ii: first, placement of capacitor banks, and then DGs, and scenario iii: simultaneous placement of DGs and capacitor banks. Simulations have been carried out on one part of practical distribution network in Metropolitan Tabriz in North West of Iran. The results of simulations have been discussed and analyzed using the five novel indices. The obtained simulation results using proposed function shows that the simultaneous placement of DGs and capacitor banks results in more reduction of the energy losses and increase improvements of reliability indices as well as voltage profile. © 2013 Wiley Periodicals, Inc. Complexity 19: 40–54, 2014     

On Using Tabu Search for Design Automation of VLSI Systems

Tabu search is a meta-heuristic problem solving technique that, when applied carefully, provides near optimal solutions in a very short time. In this paper, we have described the use of tabu search for solving problems related to very large scale integrated (VLSI) circuit design automation. Specifically, we have demonstrated the use for VLSI circuit partitioning and placement. We present a tabu search based circuit bi-partitioning technique that partitions circuits with the goal of minimizing the size of the cutset between the partitions. Then, we use tabu search techniques along with force directed placement techniques to accomplish the physical placement of VLSI circuits on regular two-dimensional arrays with the goal of minimizing the placement time. We use empirical data from partitioning and placement of benchmark circuits to test our techniques. Our methods show improvement when compared to partitioning techniques from the literature and commercially available placement tools. Relative to the literature, our tabu search bi-partitioning technique improves on the best known minimum cuts for several benchmark circuits. Relative to commercially available computer aided design tools, our tabu search based placement approach shows dramatic (20×) speedup in execution time without negative impact on the quality of the solution.