Publications

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

We consider the problem of placing a limited number of sensors in a municipal water distribution network to minimize the impact over a given suite of contamination incidents. In its simplest form, the sensor placement problem is a p-median problem that has structure extremely amenable to exact and heuristic solution methods. We describe the solution of real-world instances using integer programming or local search or a Lagrangian method. The Lagrangian method is necessary for solution of large problems on small PCs. We summarize a number of other heuristic methods for effectively addressing issues such as sensor failures, tuning sensors based on local water quality variability, and problem size/approximation quality tradeoffs. These algorithms are incorporated into the TEVA-SPOT toolkit, a software suite that the US Environmental Protection Agency has used and is using to design contamination warning systems for US municipal water systems.

In a (future) quantum computer a single logical quantum bit (qubit) will be made of multiple physical qubits. These extra physical qubits implement mandatory extensive error checking. The efficiency of error correction will fundamentally influence the performance of a future quantum computer, both in latency/speed and in error threshold (the worst error tolerated for an individual gate). Executing this quantum error correction requires scheduling the individual operations subject to architectural constraints. Since our last talk on this subject, a team of researchers at Sandia National Labortories has designed a logical qubit architecture that considers all relevant architectural issues including layout, the effects of supporting classical electronics, and the types of gates that the underlying physical qubit implementation supports most naturally. This is a two-dimensional system where 2-qubit operations occur locally, so there is no need to calculate more complex qubit/information transportation. Using integer programming, we found a schedule of qubit operations that obeys the hardware constraints, implements the local-check code in the native gate set, and minimizes qubit idle periods. Even with an optimal schedule, however, parallel Monte Carlo simulation shows that there is no finite error probability for the native gates such that the error-correction system would be benecial. However, by adding dynamic decoupling, a series of timed pulses that can reverse some errors, we found that there may be a threshold. Thus finding optimal schedules for increasingly-refined scheduling problems has proven critical for the overall design of the logical qubit system. We describe the evolving scheduling problems and the ideas behind the integer programming-based solution methods. This talk assumes no prior knowledge of quantum computing.

Abstract not provided.

Abstract not provided.

Abstract not provided.

A mathematical program is an optimization problem expressed as an objective function of multiple variables subject to set of constraints. When the optimization problem has specific structure, the problem class usually has a special name. A linear program is the optimization of a linear objective function subject to linear constraints. An integer program is a linear program where some of the variables must take only integer values. A semidefinite program is a linear program where the variables are arranged in a matrix and for all feasible solutions, this matrix must be positive semidefinite. There are general-purpose solvers for each of these classes of mathematical program. There are usually many ways to express a problem as a correct, say, linear program. However, equivalent formulations can have significantly different practical tractability. In this poster, we present new formulations for two classic discrete optimization problems, maximum cut (max cut) and the graphical traveling salesman problem (GTSP), that are significantly stronger, and hence more computationally tractable, than any previous formulations of their class. Both partially answer longstanding open theoretical questions in polyhedral combinatorics.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Discrete models of large, complex systems like national infrastructures and complex logistics frameworks naturally incorporate many modeling uncertainties. Consequently, there is a clear need for optimization techniques that can robustly account for risks associated with modeling uncertainties. This report summarizes the progress of the Late-Start LDRD 'Robust Analysis of Largescale Combinatorial Applications'. This project developed new heuristics for solving robust optimization models, and developed new robust optimization models for describing uncertainty scenarios.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

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.