Congrès conjoint MITACS-SMC 2007

In the collection depots facility location (CDFL) problem, we are given the positions of two types of centers: clients and collection depots. Every client must be serviced by a vehicle dispatched from a service center (also called a facility). The itinerary of the vehicle begins and ends at the facility and must include the client and one collection depot. The cost of serving the client is proportional to the distance travelled by the service vehicle. The CDFL problem asks for an optimal placement of the facility (-ies) that minimizes some global function of the service cost for all clients.

We distinguish several types of CDFL problems depending on the objective function (center and median problems), the transportation model (planar with the Euclidean distance and network problems), and the number of facilities that are available (single or multi-facility problems). For the center problem we seek to minimize the service cost of the most expensive client, and for the median problem we need the smallest total service cost. If every client location is equipped with a collection depot, then the CDFL problem becomes a standard facility location problem where the service cost is proportional only to the distance between the facility and the client. Therefore, the CDFL problem is at least as hard as the classic versions of the center and median problems.

In this presentation, I will review a set of results on the CDFL problem recently obtained in our group, which illustrate the difficulty of CDFL compared to the standard location model. In addition to finding efficient algorithms for certain new problems, our techniques are very interesting theoretically because they are generalisations of standard approaches which may prove useful to other problem types.

Joint work with Binay Bhattacharya, Sandip Das, Jeff Sember, and Arie Tamir.

In this presentation we formulate four problems in computational molecular biology as 0-1 quadratic programs. These problems are all NP-hard, and the current solution methods used in practice consist of heuristic or approximation algorithms tailored to each problem. Using test problems from scientific databases, we address the question, "Can a general-purpose solver obtain good answers in reasonable time?"

In addition, we use the latest heuristics as incumbent solutions to address the question, "Can a general-purpose solver confirm optimality or find an improved solution in reasonable time?" Our computational experiments compare three different reformulation methods: two forms of linearization and one form of quadratic convexification.

Based on joint work with Richard J. Forrester, Dickinson College.

Let S be a sequence of n points whose coordinates are given initially only to some limited precision, with additional precision available at some additional cost per bit. Suppose that we wish to determine some property P of S: for example, what is the 1-centre of S, or (even more simply) does one distinguished point of S lie in the interior of the convex hull of the rest. For some problem instances, many bits of all (or most) of the points need to be determined in order to establish P; for other instances P can be established with the knowledge of only a relatively small (total) number of bits. In general, we would like to design algorithms whose cost (number of bits examined) adapts to the intrinsic cost (shortest computation or "proof" of the property P) for a given instance.

This talk describes some results concerning a few very basic questions of this type, focusing primarily on facility-location type questions for point sets in low dimensions. In many cases we are able to define a notion of intrinsic cost c(I) of an instance (input set) I and show that

(i) any algorithm can be forced to examine c(I) bits in the worst case (over all presentations of I as an input sequence), even if I is known,
(ii) there is an algorithm that examines only O ( c(I) lgc(I) ) bits in the worst case, even if I is not known, and
(iii) any algorithm can be forced to examine O ( c(I) lgc(I) ) bits in the worst case (over all presentations of inputs with intrinsic cost c(I)), even if c(I) is known.

Based on joint work with Raimund Seidel.

The dawning of mathematics occurred with the first steps to model some problems faced in daily living, mathematically, perhaps 10,000 years ago. Earliest mathematical models constructed were small systems of linear equations, the elimination method for solving them was discovered over 2500 years ago in China and India; leading to the development of linear algebra. The ancient texts Chiu-Chang Suanshu (in Chinese) and Sulabhasuutrah (in Sanskrit) describe the method. The method was unknown in Europe until the 19th century when Gauss with his very favorite number 17 popularized it.

However, there was no computationally viable method until recently to solve systems of linear constraints including inequalities. Beginning in the 19th century, Fourier, De la Vallée Poussin, Farkas, Kantarovich, and others developed some methods or did initial work for solving such systems. This work culminated in the mid-20th century paper on the Simplex method for LPs and linear inequalities by Dantzig.

>From the nature of the simplex method, LP can be viewed as the 20th century extension of linear algebra to handle systems of linear constraints including inequalities. Dantzig very successfully promoted LP as an appropriate mathematical model for solving decision making problems with numerous applications in all areas of science, engineering, and business management.

Among the most successful methods used for solving LPs today are the simplex methods, primal-dual interior point methods, and the gravitational methods. All are descent methods based on matrix inversion operations, limiting applicability to problems with sparse data sets.

I will discuss the features of a new interior point method which is a descent method that does not need matrix inversions, and the nice geometric results on which it is based.