Publications

Abstract not provided.

Abstract not provided.

We present a series of related robust optimization models for placing sensors in municipal water networks to detect contaminants that are maliciously or accidentally injected. We formulate sensor placement problems as mixed-integer programs, for which the objective coefficients are not known with certainty. We consider a restricted absolute robustness criteria that is motivated by natural restrictions on the uncertain data, and we define three robust optimization models that differ in how the coefficients in the objective vary. Under one set of assumptions there exists a sensor placement that is optimal for all admissible realizations of the coefficients. Under other assumptions, we can apply sorting to solve each worst-case realization efficiently, or we can apply duality to integrate the worst-case outcome and have one integer program. The most difficult case is where the objective parameters are bilinear, and we prove its complexity is NP-hard even under simplifying assumptions. We consider a relaxation that provides an approximation, giving an overall guarantee of near-optimality when used with branch-and-bound search. We present preliminary computational experiments that illustrate the computational complexity of solving these robust formulations on sensor placement applications.

Abstract not provided.

While it had been known for a long time how to transform an asymmetric traveling salesman (ATS) problem on the complete graph with n vertices into a symmetric traveling salesman (STS) problem on an incomplete graph with 2n vertices, no method was available for using this correspondence to derive facets of the symmetric polytope from facets of the asymmetric polytope until the work of E. Balas and M. Fischetti in [Lifted cycle inequalities for the asymmetric traveling salesman problem, Mathematics of Operations Research 24 (2) (1999) 273-292] suggested an approach. The original Balas-Fischetti method uses a standard sequential lifting procedure for the computation of the coefficient of the edges that are missing in the incomplete STS graph, which is a difficult task when addressing classes of (as opposed to single) inequalities. In this paper we introduce a systematic procedure for accomplishing the lifting task. The procedure exploits the structure of the tight STS tours and organizes them into a suitable tree structure. The potential of the method is illustrated by deriving large new classes of facet-defining STS inequalities.

Abstract not provided.

A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the metric STSP (Symmetric Traveling Salesman Problem) is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the metric ATSP (Asymmetric Traveling Salesman Problem). Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of "hard-to-round" solutions of the relaxations. © Springer-Verlag 2004.

In Combinatorial Optimization, one is frequently faced with linear programming (LP) problems with exponentially many constraints, which can be solved either using separation or what we call compact optimization. The former technique relies on a separation algorithm, which, given a fractional solution, tries to produce a violated valid inequality. Compact optimization relies on describing the feasible region of the LP by a polynomial number of constraints, in a higher dimensional space. A commonly held belief is that compact optimization does not perform as well as separation in practice. In this paper,we report on an application in which compact optimization does in fact largely outperform separation. The problem arises in structural proteomics, and concerns the comparison of 3-dimensional protein folds. Our computational results show that compact optimization achieves an improvement of up to two orders of magnitude over separation. We discuss some reasons why compact optimization works in this case but not, e.g., for the LP relaxation of the TSP. © Springer-Verlag 2004.

The maximum contact map overlap (MAX-CMO) between a pair of protein structures can be used as a measure of protein similarity. It is a purely topological measure and does not depend on the sequence of the pairs involved in the comparison. More importantly, the MAX-CMO present a very favorable mathematical structure which allows the formulation of integer, linear and Lagrangian models that can be used to obtain guarantees of optimality. It is not the intention of this paper to discuss the mathematical properties of MAX-CMO in detail as this has been dealt elsewhere. In this paper we compare three algorithms that can be used to obtain maximum contact map overlaps between protein structures. We will point to the weaknesses and strengths of each one. It is our hope that this paper will encourage researchers to develop new and improve methods for protein comparison based on MAX-CMO.

Abstract not provided.

Abstract not provided.

In this paper we introduce by means of examples a new technique for formulating compact (i.e. polynomial-size) LP relaxations in place of exponential-size models requiring separation algorithms. In the same vein as a celebrated theorem by Groetschel, Lovasz and Schrijver, we state the equivalence of compact separation and compact optimization. Among the examples used to illustrate our technique, we introduce a new formulation for the Traveling Salesman Problem, whose relaxation we show equivalent to the subtour elimination relaxation.

Abstract not provided.

The authors present a new technique for the design of approximation algorithms that can be viewed as a generalization of randomized rounding. They derive new or improved approximation guarantees for a class of generalized congestion problems such as multicast congestion, multiple TSP etc. Their main mathematical tool is a structural decomposition theorem related to the integrality gap of a relaxation.

A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the symmetric TSP is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the asymmetric TSP. This is surprising since no constant-factor approximation is known for the latter problem. Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of `hard-to-round' solutions of the relaxations.

Both the increased complexity of integrated circuits, resulting in six or more levels of integration, and the increasing use of flip-chip packaging have driven the development of integrated circuit (IC) failure analysis tools that can be applied to the backside of the chip. Among these new approaches are focused ion beam (FIB) tools and processes for performing chip edits/repairs from the die backside. This paper describes the use of backside FIB for a failure analysis application rather than for chip repair. Specifically, we used FIB technology to prepare an IC for inspection of voided metal interconnects (''lines'') and vias. Conventional FIB milling was combined with a super-enhanced gas assisted milling process that uses XeF{sub 2} for rapid removal of large volumes of bulk silicon. This combined approach allowed removal of the TiW underlayer from a large number of Ml lines simultaneously, enabling rapid localization and plan view imaging of voids in lines and vias with backscattered electron (BSE) imaging in a scanning electron microscope (SEM). Sequential cross sections of individual voided vias enabled us to develop a 3-d reconstruction of these voids. This information clarified how the voids were formed, helping us identify the IC process steps that needed to be changed.

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. © Springer-Verlag 1999.

Given a complete undirected graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where multiedges are allowed in the solution). A lower bound for the minimum cost 2-edge connected subgraph is obtained by solving the linear programming relaxation for this problem, which coincides with the subtour relaxation of the traveling salesman problem when the costs satisfy the triangle inequality. The simplest fractional solutions to the subtour relaxation are the (Formula presented)-integral solutions in which every edge variable has a value which is a multiple of (Formula presented). We show that the minimum cost of a 2-edge connected subgraph is at most four-thirds the cost of the minimum cost (Formula presented)-integral solution of the subtour relaxation. This supports the long-standing (Formula presented) Conjecture for the TSP, which states that there is a Hamilton cycle which is within (Formula presented) times the cost of the optimal subtour relaxation solution when the costs satisfy the triangle inequality.