SOME COMBINATORIAL OPTIMIZATION PROBLEMS ARISING FROM VLSI CIRCUIT DESIGN

This paper is basically a survey to show a number of combinatorlal optimization problems arising from VLSI clrcult design.Some of them including the existence problem,minimax problem,net representation,bend minimization,area minimization,placement problem,routing problem,etc,are especially discussed with new results and theoretical ideas for treating them.Finally,a number of problems for further research are mentioned.     

Efficient Kriging-based robust optimization of unconstrained problems

A novel methodology, based on Kriging and expected improvement, is proposed for applying robust optimization on unconstrained problems affected by implementation error. A modified expected improvement measure which reflects the need for robust instead of nominal optimization is used to provide new sampling point locations. A new sample is added at each iteration by finding the location at which the modified expected improvement measure is maximum. By means of this process, the algorithm iteratively progresses towards the robust optimum. It is demonstrated that the algorithm performs significantly better than current techniques for robust optimization using response surface modeling.     

Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization

Interior-point methods are among the most efficient approaches for solving large-scale nonlinear programming problems. At the core of these methods, highly ill-conditioned symmetric saddle-point problems have to be solved. We present combinatorial methods to preprocess these matrices in order to establish more favorable numerical properties for the subsequent factorization. Our approach is based on symmetric weighted matchings and is used in a sparse direct LDL ^T factorization method where the pivoting is restricted to static supernode data structures. In addition, we will dynamically expand the supernode data structure in cases where additional fill-in helps to select better numerical pivot elements. This technique can be seen as an alternative to the more traditional threshold pivoting techniques. We demonstrate the competitiveness of this approach within an interior-point method on a large set of test problems from the CUTE and COPS sets, as well as large optimal control problems based on partial differential equations. The largest nonlinear optimization problem solved has more than 12 million variables and 6 million constraints.     

Efficient algorithms for orthogonal packing problems

The NP complete problem of the orthogonal packing of objects of arbitrary dimension is considered in the general form. A new model for representing objects in containers is proposed that ensures the fast design of an orthogonal packing. New heuristics for the placement of orthogonal packing are proposed. A single-pass heuristic algorithm and a multimethod genetic algorithm are developed that optimize an orthogonal packing solution by increasing the packing density. Numerical experiments for two- and three-dimensional orthogonal packing problems are performed.     

Efficient solutions for weight-balanced partitioning problems

We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constraints. The data points are weighted with respect to different features and the clusters adhere to given lower and upper bounds on the total weight of their points with respect to each of these features. Further the weight-contribution of a vector to a cluster can depend on the cluster it is assigned to. Our interest in these types of clustering problems is motivated by an application in land consolidation where the ability to perform this kind of balancing is crucial.Our framework maximizes an objective function that is convex in the summed-up utility of the items in each cluster. Despite hardness of convex maximization and many related problems, for fixed dimension and number of clusters, we are able to show that our clustering model is solvable in time polynomial in the number of items if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. We conclude our discussion with a new, efficient model and algorithm for land consolidation.     

Well-posedness for set optimization problems

In this paper, three kinds of well-posedness for set optimization are first introduced. By virtue of a generalized Gerstewitz’s function, the equivalent relations between the three kinds of well-posedness and the well-posedness of three kinds of scalar optimization problems are established, respectively. Then, sufficient and necessary conditions of well-posedness for set optimization problems are obtained by using a generalized forcing function, respectively. Finally, various criteria and characterizations of well-posedness are given for set optimization problems.     

Power optimization for connectivity problems

Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MPk-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MPk-CSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MPk-EDP). We give an O(log⁴ n)-approximation algorithm for MPb-EC. This gives an O(log⁴ n)-approximation algorithm for MPk-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an approximation algorithm for ECSS, and for its variant in directed graphs (i.e., MPk-EDP), we establish the following inapproximability threshold: MPk-EDP cannot be approximated within O(2^log1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time. This paper was done when V. S. Mirrokni was at Computer Science and Artificial Intelligence Laboratory, MIT.     

Efficient solutions schemes for interface problems

A computationally efficient two-level iterative scheme is proposed for the solution of the interface problems with Lagrange multipliers, where the oscillatory part of the solution is resolved by means off smoothing using a new, efficient preconditioner whereas the smooth component of the solution is captured by the collocation-based problem on the auxilliary grid, that is solved directly using a sparse direct solver. A simple adaptive feature is built into the proposed solution method in order to guarantee convergence for ill-conditioned problems. Nmerical results presented for example problems including that of a Boeing crown panel show that the proposed tww-level solution technique outperfrmsnce the standard, single level iterative and direect solvers.     

Multi-level optimization for multi-objective problems

A multi-level solution method is presented for multi-objective optimization of large-scale systems associated with the hierarchical structure of decision-making. The method, consisting of a multi-level problem formulation and an interactive algorithm, has distinct advantages in handling the difficulties which are often experienced in engineering. The method is illustrated by its application to an optimal design of a processing system.     

Exclusion regions for optimization problems

Branch and bound methods for finding all solutions of a global optimization problem in a box frequently have the difficulty that subboxes containing no solution cannot be easily eliminated if they are close to the global minimum. This has the effect that near each global minimum, and in the process of solving the problem also near the currently best found local minimum, many small boxes are created by repeated splitting, whose processing often dominates the total work spent on the global search. This paper discusses the reasons for the occurrence of this so-called cluster effect, and how to reduce the cluster effect by defining exclusion regions around each local minimum found, that are guaranteed to contain no other local minimum and hence can safely be discarded. In addition, we will introduce a method for verifying the existence of a feasible point close to an approximate local minimum. These exclusion regions are constructed using uniqueness tests based on the Krawczyk operator and make use of first, second and third order information on the objective and constraint functions.     

Efficient topology optimization of thermo-elasticity problems using coupled field adjoint sensitivity analysis method

We develop a unified and efficient adjoint design sensitivity analysis (DSA) method for weakly coupled thermo-elasticity problems. Design sensitivity expressions with respect to thermal conductivity and Young's modulus are derived. Besides the temperature and displacement adjoint equations, a coupled field adjoint equation is defined regarding the obtained adjoint displacement field as the adjoint load in the temperature field. Thus, the computing cost is significantly reduced compared to other sensitivity analysis methods. The developed DSA method is further extended to a topology design optimization method. For the topology design optimization, the design variables are parameterized using a bulk material density function. Numerical examples show that the DSA method developed is extremely efficient and the optimal topology varies significantly depending on the ratio of mechanical and thermal loadings.     

Efficient line search algorithm for unconstrained optimization

A new line search algorithm for smooth unconstrained optimization is presented that requires only one gradient evaluation with an inaccurate line search and at most two gradient evaluations with an accurate line search. It terminates in finitely many operations and shares the same theoretical properties as the standard line search rules like the Armijo-Goldstein-Wolfe-Powell rules. This algorithm is especially appropriate for the situation when gradient evaluations are very expensive relative to function evaluations.The authors would like to thank Margaret Wright and Jorge Moré for valuable comments on earlier versions of this paper.     

Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

Efficient numerical methods for entropy-linear programming problems

Entropy-linear programming (ELP) problems arise in various applications. They are usually written as the maximization of entropy (minimization of minus entropy) under affine constraints. In this work, new numerical methods for solving ELP problems are proposed. Sharp estimates for the convergence rates of the proposed methods are established. The approach described applies to a broader class of minimization problems for strongly convex functionals with affine constraints.     

Efficient Kansa-type MFS algorithm for elliptic problems

In this study we propose an efficient Kansa-type method of fundamental solutions (MFS-K) for the numerical solution of certain problems in circular geometries. In particular, we consider problems governed by the inhomogeneous Helmholtz equation in disks and annuli. The coefficient matrices in the linear systems resulting from the MFS-K discretization of these problems possess a block circulant structure and can thus be solved by means of a matrix decomposition algorithm and fast Fourier Transforms. Several numerical examples demonstrating the efficacy of the proposed algorithm are presented.