Minimum cost Layout Decomposition and Legalization for Triple Patterning Lithography

With the need of 16/11nm cells, triple patterning lithography (TPL) has been concerned in lithography industry. Based on a new conflict projection technique to identify conflicts, we formulate in this paper the TPL layout decomposition problem as a minimum cost coloring problem. The problem is solved in two steps. First, it is relaxed to a … Read more

A Semidefinite Optimization Approach to the Parallel Row Ordering Problem

The $k$-Parallel Row Ordering Problem (kPROP) is an extension of the Single-Row Facility Layout Problem (SRFLP) that considers arrangements of the departments along more than one row. We propose an exact algorithm for the kPROP that extends the semidefinite programming approach for the SRFLP by modelling inter-row distances as products of ordering variables. For k=2 … Read more

The Checkpoint Ordering Problem

We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to … Read more

Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout

In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also … Read more

A Computational Study and Survey of Methods for the Single-Row Facility Layout Problem

The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange … Read more

Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear … Read more

A New Mathematical-Programming Framework for Facility-Layout Design

We present a new framework for efficiently finding competitive solutions for the facility-layout problem. This framework is based on the combination of two new mathematical-programming models. The first model is a relaxation of the layout problem and is intended to find good starting points for the iterative algorithm used to solve the second model. The … Read more

A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in … Read more