Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization

Cell flipping in VLSI design is an operation in which some of the cells are replaced with their “mirror images” with respect to a vertical axis, while keeping them in the same slot. After the placement of all the cells, one can apply cell flipping in order to further decrease the total area, approximating this objective by minimizing total wire length, channel width, etc. However, finding an optimal set of cells to be flipped is usually a difficult problem. In this paper we show that cell flipping can be efficiently applied to minimize channel density in the standard cell technology. We show that an optimal flipping pattern can be found in O(p(n/c)^c) time, where n, p and c denote the number of nets, pins and channels, respectively. Moreover, in the one channel case (i.e. when c = 1) the cell flipping problem can be solved in O(p log n) time. For the multi-channel case we present both an exact enumeration scheme and a mixed-integer program that generates an approximate solution very quickly. We present computational results on examples up to 139 channels and 65000 cells.     

Characterizing and decomposing classes of threshold,split, and bipartite graphs via 1-Sperner hypergraphs

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of $1$-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding $1$-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of $1$-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.     

Multivariate value at risk and related topics

Multivariate Value at Risk, or MVaR, is defined as the quantile set of a multivariate probability distribution. It has already been introduced and used in the literature under the name of p-Level Efficient Points, or pLEP’s, or briefly p-efficient points. Some of the topics connected with it are surveyed: discrete convexity, algorithmic generation, relation to logconcavity. A related notion: Multivariate Conditional Value at Risk, or MCVaR, is also introduced and some of its properties are explored. Finally, optimization problems, based on these notions, are presented and discussed, from the point of view of convexity and algorithmic solution.     

The discrete moment problem with fractional moments

Discrete moment problems (DMP) with integer moments were first introduced by Prékopa to provide sharp lower and upper bounds for functions of discrete random variables. Prékopa also developed fast and stable dual type linear programming methods for the numerical solutions of the problem. In this paper, we assume that some fractional moments are also available and propose basic theory and a solution method for the bounding problems. Numerical experiments show significant improvement in the tightness of the bounds.     

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

Optimal sequential inspection policies

We consider the problem of combining a given set of diagnostic tests into an inspection system to classify items of interest (cases) with maximum accuracy such that the cost of performing the tests does not exceed a given budget constraint. One motivating application is sequencing diagnostic tests for container inspection, where the diagnostic tests may correspond to radiation sensors, document checks, or imaging systems. We consider mixtures of decision trees as inspection systems following the work of Boros et al. (Nav. Res. Logist. 56:404?C420, 2009). We establish some properties of efficient inspection systems and characterize the optimal classification of cases, based on some of their test scores. The measure of performance is the fraction of all cases in a specific class of interest, which are classified correctly. We propose a dynamic programming algorithm that constructs more complex policies by iteratively prefixing devices to a subset of policies and thereby enumerating all of the efficient (i.e., undominated) inspection policies in the two dimensional cost-detection space. Our inspection policies may sequence an arbitrary number of tests and are not restricted in the branching factor. Our approach directly solves the bi-criterion optimization problem of maximizing detection and minimizing cost, and thus supports sensitivity analysis over a wide range of budget and detection requirements.     

Graph transformations preserving the stability number

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.     

Comprehensive vs. comprehensible classifiers in logical analysis of data

The main objective of this paper is to compare the classification accuracy provided by large, comprehensive collections of patterns (rules) derived from archives of past observations, with that provided by small, comprehensible collections of patterns. This comparison is carried out here on the basis of an empirical study, using several publicly available data sets. The results of this study show that the use of comprehensive collections allows a slight increase of classification accuracy, and that the “cost of comprehensibility” is small.     

On stages and consistency checks in stochastic programming

This paper gives a rigorous definition of a stage, usable for dynamic stochastic programs with both recourse and probabilistic constraints. Algebraic modelling languages can make use of this definition for automatic consistency checks.