DIMACS Center, CoRE Building, Busch Campus, Rutgers University, Piscataway, NJ

**Organizers:****R. Ravi**, Carnegie Mellon University**Vijay V. Vazirani**, Georgia Tech.

May 27th: (Applications) -------------------------------------------------------------------- AM: George Nemhauser, Georgia Tech. -- Optimization in Airline Integrated Planning and Operations - Part I: Robust Planning Ellis Johnson, Georgia Tech. -- Optimization in Airline Integrated Planning and Operations - Part II: Recovery TITLE: Optimization in Airline Integrated Planning and Operations Part I: Robust Planning, Part II: Recovery SPEAKERS: George L. Nemhauser (Part I), Ellis L. Johnson (Part II) AFFILIATION: School of Industrial and Systems Engineering Georgia Institute of Technology ABSTRACT: The major airlines have been pioneers in the use of optimization for the allocation and scheduling of resources (both planes and crews). The formulation and solution of the crew scheduling problem and partitioning problem goes back to the 1960s. Moreover, many new ideas for large-scale optimization were first developed and tested on airlines problems. But until recently optimization was used only in planning, and under the assumption that the printed schedule would be flown without modifications. In reality, because of random events such as equipment failures and bad weather, there are almost always disruptions that cause changes in the schedule. Flights may be delayed, rerouted or canceled. Crews may miss connections or be illegal for an assigned flight because of government time restrictions. Reallocation and rescheduling, which is called the recovery problem, frequently must be done in almost real time. =20 Research on using optimization to solve the recovery problem is just emerging. Essentially, one can view the process as a two-stage stochastic programming problem with the recovery decisions being the recourse to the planning decisions. In the first part of this talk we will review the planning process, including both fleet assignment and crew scheduling, and then discuss some new approaches to robust planning, i.e. planning that attempts to be less sensitive to disruptions. In the second part, we model the recovery problem as an optimization problem and we also discuss a simulation that is used to evaluate new ideas and algorithms, and also can serve as a training tool. ---------------------------------------------------------------------------- Jitendra Malik, UC Berkeley -- Graph partitioning and matching problems in computer vision TITLE: Graph partitioning and matching problems in computer vision SPEAKER: Jitendra Malik AFFILIATION: Computer Science, UC Berkeley ABSTRACT: to be announced ---------------------------------------------------------------------------- PM: Prabhakar Raghavan, IBM Almaden -- Customer segmentation and collaborative filtering: a microeconomic view Title: Customer segmentation and collaborative filtering: a microeconomic view Abstract: In this talk we propose a microeconomic view of data mining, based on the premise that the value of patterns unearthed from legacy data is determined by their impact on an enterprise's objective. This leads us to optimization as a means for evaluting data mining operations. We focus on customer segmenatation, one of the few areas where data mining has (to date) met with consistent success. We then build on the basic framework to address the setting of collaborative filtering (sometimes also called "recommendation systems"): systems that, based on the past behavior of a group of users, will recommend to them books to read, movies to watch, and so on. This talk will include work from collaborations with Jon Kleinberg and Christos Papadimitriou, and with Sridhar Rajagopalan, S. Ravi Kumar and Andrew Tomkins. ---------------------------------------------------------------------------- Rajeev Motwani, Stanford University -- High-Dimensional Similarity Search in Large Databases High-Dimensional Similarity Search in Large Databases Rajeev Motwani Department of Computer Science Stanford University The nearest neighbor problem is the following: Given a set P of n points in some metric space X, preprocess P so as to efficiently answer queries which require finding the point in P closest to a query point q in X. This fundamental geometric problem is of growing importance as an abstraction of similarity search in areas such as information retrieval and image processing. We will focus on the particularly interesting case of the d-dimensional Euclidean space. Despite decades of effort, the current solutions are far from satisfactory; in fact, for large d, in theory or in practice, they provide little improvement over the brute-force algorithm which compares the query point to each data point. Of late, there has been some interest in the approximate nearest neighbors problem where we are only required to produce a point p' whose distance from the query q is within a factor (1+e) of the distance between q and its true nearest neighbor. We will present two algorithmic results for the approximate version that significantly improve the known bounds: (a) preprocessing cost polynomial in n and d, and a truly sublinear query time (for e>1); and, (b) query time polynomial in d and log n, and only a mildly exponential preprocessing cost O(n/e^d). Applying a classical geometric lemma on random projections, we show how to obtain the first known algorithm with polynomial preprocessing and query time polynomial in d and log n. Unfortunately, for small e, the latter is a purely theoretical result since the exponent depends on 1/e. On the other hand, experimental results indicate that the first algorithm offers extremely fast running times on real data sets. Its key ingredient is the notion of locality-sensitive hashing which may be of independent interest; in fact, we will give applications to information retrieval, pattern recognition, dynamic closest-pairs, and fast clustering algorithms. Time permitting, we will also touch upon a new abstraction of similarity search that leads to an interesting generalization of the nearest neighbors problem. (Joint work with Piotr Indyk.) ---------------------------------------------------------------------------- Eva Tardos, Cornell Unviersity -- Flows in Networks TITLE: Flows in Networks SPEAKER: Eva Tardos AFFILIATION: Department of Computer Science Cornell University ABSTRACT: In this talk we will consider the disjoint paths problem. This problem is one of the basic algorithmic problems underlying the management of high-speed communication networks, and is also one of the oldest and most the basic algorithmic questions, it is one of Karp's original NP-complete problems. Given a graph and a set of node-pairs that would like to be connected by disjoint paths, we can ask a number of natural questions: How many of the disjoint paths are simultaneously realizable? How many rounds are required to satisfy all connection requests, when all paths assigned in a single round must be disjoint? All these questions are NP-hard, and hence we cannot expect to have efficient algorithms for them. In this talk we will consider approximation algorithms for these questions in different classes of graphs. We will discuss efficient algorithms that are guaranteed to provide solutions close to optimal. ---------------------------------------------------------------------------- May 28th: (Tools) ---------------------------------------------------------------------------- AM: Kurt Mehlhorn, Max Planck Institute f"ur Informatik, Saarbr"ucken, Germany -- Secondary Memory Algorithms for Networks and Geometry TITLE: Secondary Memory Algorithms for Networks and Geometry SPEAKER: Kurt Mehlhorn AFFILIATION: Max Planck Institute f"ur Informatik, Saarbr"ucken, Germany ABSTRACT: In the theoretical part of the talk I will report on secondary memory algorithms for shortest paths and some geometric tasks (line segment intersection, convex hulls, ...). In the experimental part I will report on LEDA-SM, an extension of LEDA into the realm of secondary memory algorithms. ---------------------------------------------------------------------------- Andrew Goldberg, NEC -- Maximum Flows: New Techniques and New Algorithms TITLE: Maximum Flows: New Techniques and New Algorithms SPEAKER: Andrew V. Goldberg, NEC Research Institute, Inc. ABSTRACT The maximum flow problem is a classical optimization problem with many applications. Algorithms for this problem have been studied for over four decades. Recently, significant improvements have been made in theoretical performance of maximum flow algorithms. In this talk we put these results in perspective. We also outline major recent developments, including the use of adaptive length functions and, for undirected problems with unit capacities, the use of sparsification techniques. ---------------------------------------------------------------------------- John Hooker, Carnegie Mellon -- Mixed logical/linear programming TITLE: Mixed logical/linear programming SPEAKER: John Hooker AFFILIATION: Carnegie Mellon U ABSTRACT: I will cover three themes. a) The mathematical programming community has made an enormous investment in the use of integer variables for solving combinatorial problems. However, a rethinking and downsizing of their role improves both modeling and solution. Their main value is in supplying a continuous relaxation, but they can add a good deal of overhead without providing much in return. b) Replacing integer modeling with logic-based modeling forges a link between math programming and constraint satisfaction and in particular provides logical analogs of cutting planes, etc. c) The formulation of a framework for combining these two approaches raises a fundamental modeling question: how can a declarative framework allow and even compel the user to exploit specialized solvers, such as linear programming solvers? ---------------------------------------------------------------------------- PM: Bob Bixby, Rice University -- Recent developments in CPLEX Title: Recent Developments in CPLEX Abstract: CPLEX 1.0 was released in 1988. Following that release there were steady performance improvments in the core simplex and, later, barrier algorithms for linear optimization, with the last really significant LP improvments coming in the barrier implementations in CPLEX 4.0. In this talk I will describe some quite surprising, new performance improvements to be available in the next released version of CPLEX. For the barrier algorithms, these improvements apply to models of all sizes, but are particularly marked for instances in which the basic "factorization step" is the dominant expense. For the simplex implementations, both primal and dual, there will typically not be much improvement seen on smaller models (with, say, fewer than 5,000 constraints), but for larger models, the improvements are even more marked than for the barrier algorithms. These simplex improvements then translate into further significant improvments in the cost of the crossover step from a barrier "vector" solution to a simplex basic solution. This work is based upon a number of new ideas as well as earlier work of Rothberg, Hendrickson, Wunderling, and others. For the simplex method, we were particularly motivated by the idea of concentrating on larger models -- it is now not unusual for real applications to generate LPs with several hundreds of thousands of constraints -- and by the unpublished work of Zonghao Gu. The work described in this talk is joint with Irv Lustig (irv@dizzy.cplex.com), Ed Rothberg (rothberg@cplex.com), and Roland Wunderling (roland@cplex.com), all of the CPLEX Division of ILOG. ---------------------------------------------------------------------------- Martin Savelsbergh, Georgia Tech. -- PARINO, a PARallel INteger Optimizer TITLE: PARINO, a PARallel INteger Optimizer SPEAKER: Martin W.P. Savelsbergh AFFILIATION: School of Industrial and Systems Engineering Georgia Institute of Technology ABSTRACT: We describe the design and implementation of PARINO, a parallel integer optimizer. PARINO is portable across any message-passing parallel computing platform. It is written in C++ and developed using an ``entity-FSM''-based structure that greatly facilitates the modularity and extensibility of the functionality of the system and its portability to any message-passing interface. The current version of PARINO has been used on an 8-node IBM SP2 multicomputer and a cluster of 48 Intel machines, each one of with a quad PentiumPro running at a clock speed of 200Mhz. It has been able to solve most of the instances in the MIPLIB test set with linear and superlinear speedups. The implementation is based on a distributed version of the traditional linear programming based branch-and-bound approach to integer programming. In addition, several state-of-the-art techniques are incorporated, such as preprocessing and probing, reduced-cost fixing, global reduced-cost fixing, primal heuristics, SOS-branching and various types of cutting planes. Cut management is an important factor that can influence the performance of parallel mixed integer optimization. A key contribution of our work is the development of a novel architecture and associated techniques for distributed cut management, and addressing the issues arising in its implementation. ---------------------------------------------------------------------------- Sebastian Ceria, Columbia University -- Lift-and-project cuts: An efficient solution method for mixed integer programs TITLE: Lift-and-project cuts: An efficient solution method for mixed integer programs SPEAKER: Sebastian Ceria A disjunctive constraint (disjunction for short) for a mixed-integer program specifies that at least one linear constraint set among several be satisfied. The simplest disjunction in a general mixed-integer program states that a 0-1 constrained variable must either take the value 0 or 1. Disjunctions provide a natural tool for dividing a discrete problem into smaller, and hopefully simpler, subproblems and have been used extensively in branch-and-bound methods. In our work we use disjunctions to generate ``lift-and-project'' cutting planes for general mixed-integer programs. This type of cuts are strong, in the sense that they are facets of the polyhedron defined by the convex hull of the union of the disjunctive sets, which is a relaxation of the original mixed-integer program. Lift-and-project cuts have already been used effectively to solve many problems in the literature. In this talk we present new computational results with lift-and-project cuts. We focus on disjunctions that tend to be efficient when used as branching rules in branch-and-bound: our computational results show that these disjunctions also provide good cuts. We will discuss extensive computational testing of the test problems in MIPLIB, and provide ample evidence of the effectiveness of these cuts. This work is joint with Gabor Pataki. ---------------------------------------------------------------------------- Evening: "An hour with algorithms" by Kurt Mehlhorn over wine and cheese ---------------------------------------------------------------------------- May 29th: (Applications) ---------------------------------------------------------------------------- AM: Laurence Wolsey, University of Utrecht, on leave from CORE, Universite Catholique de Louvain, Belgium -- Production Planning Problems: Models and Software TITLE: Production Planning Problems: Models and Software SPEAKER: Laurence A. Wolsey AFFILIATION:University of Utrecht, on leave from CORE, Universite Catholique de Louvain ABSTRACT: We discuss ongoing work aimed at establishing a testbed of production planning models, and the development of a specialised modelling and branch-and-cut system incorporating several of the polyhedral results for lot-sizing models developed over the last ten years. The system is based upon the Extended Modelling and Optimisation Subroutine Library (EMOSL) of XPRESS. Several models and computational results will be presented. ---------------------------------------------------------------------------- Gary Miller, Carnegie Mellon -- Graph Embeddings in Scientific Computation Abstract: Graph embeddings have been used in computer science to analyze VLSI layouts, to analyze interconnection networks, to bound graph separator sizes, and to analyze mixing rates for Markov processes. The simplest case of a graph embedding is when we have two graphs over the same vertex set. In this case, we say a graph $G$ is embedded into a graph $H$ if every edge of $G$ is mapped to a path of $H$ with the same end points. The goal is to find an embedding that minimizes dilation, the length of the longest path, and minimizes congestion, the maximum number of paths using the same edge of $H$. In this talk I will show how graph embeddings can be used in Scientific Computation and Numerical Analysis. In particular, I will present new preconditioners and their analysis, and give new interpolation error bounds for the finite element method. Other applications include the analysis of old preconditioners such as the Incomplete Cholesky Factorization method. This talk represents joint work with many people including: Keith Gremban, Steve Guattery, Dafna Talmor, Shang-Hua Teng, Noel Walkington ---------------------------------------------------------------------------- Dana Randall, Georgia Tech. -- Markov chain methods from Physics TITLE: Markov chain methods from physics. SPEAKER: Dana Randall AFFILIATION: Georgia Tech, School of Mathematics and College of Computing ABSTRACT: Fundamental combinatorial questions lie at the heart of many physical systems studied in statistical mechanics. While in some cases elegant solutions have been discovered, in many cases the best tools currently available are Markov chain Monte Carlo methods. Monte Carlo algorithms allow us to sample large configurations and approximate important parameters of the system. Both rigorous Monte Carlo methods and ingenious heuristics have proven useful tools for many problems. We will survey some of the techniques used by computer scientists and physicists and highlight the differences between their approaches. ---------------------------------------------------------------------------- PM: Craig Tovey, Georgia Tech. -- Self-Organizing Social Structure in Fish Groups ABSTRACT: We employ discrete mathematical models to explore how two different kinds of structures arise in fish groups. The first structure is the ellipsoidal spatial arrangement of many fish schools, observed both in the laboratory and in the wild. Our model is the first to account for the imperfect packing observed in actual schools, and to predict the shape of the ellipsoid. The second structure is the acyclic set of pairwise dominance relationships observed in small groups (joint work with I. Chase). Recent experiments demonstrate that this social structure is self-organizing. How could the individual behaviors that generate such structure evolve? We hypothesize a behavioral trait, reactivity, which is consistent with laboratory experiment. For a simple model of hierarchy formation, the presence of this trait increases the probability of acyclicity. Moreover, there is positive selection pressure for reactivity, under realistic assumptions about the relation between fitness and hierarchy rank. ---------------------------------------------------------------------------- Michael Trick, Carnegie Mellon -- Adventures in Sports Scheduling TITLE: Adventures in Sports Scheduling SPEAKER: Michael Trick AFFILIATION: Carnegie Mellon University ABSTRACT: The problem of creating a reasonable, playable schedule for a sports league seems simple, but is surprisingly difficult. For three years I have been working with Major League Baseball and (with George Nemhauser and Kelly Easton at Georgia Tech) college basketball. Along the way, we have formulated and solved many large and interesting discrete optimization problems. I will discuss the problems and the difficulties that arise in this field. ---------------------------------------------------------------------------- Milena Mihail, Bellcore -- Network survivability and network evolution Abstract: Telecommunications and cable industries, as well as the government, are moving rapidly towards upgrading their networks to support massive use of broadband services. The design and operation of such broadband networks give rise to fundamental algorithmic questions such as survivability under element failure, cost and service effective covering of bandwidth demand with alterative and competing technological solutions, bandwidth allocation and the economics of network evolution. We survey techniques from the emerging theory of approximation algorithms that address the above questions and discuss implementations of suitable adaptations of these algorithms relevant to software of commercial toolkits for automated design of backbone SONET/WDM networks. We also discuss new combinatorial problems whose solution would have further impact in the design of backbone broadband networks.

Other Workshops

DIMACS Homepage

Contacting the Center

Document last modified on April 13, 1998.