Optimisation d'allocation de ressources
Org: Binay Bhattacharya et Abraham Punnen (SFU)
- ROBERT BENKOCZI, Queen's University
Collection depots facility location problems
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
Joint work with Binay Bhattacharya, Sandip Das, Jeff Sember, and Arie
- HARVEY GREENBERG, University of Colorado, Department of Mathematical Sciences
Quadratic Binary Progamming Models in Computational Biology
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
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
Based on joint work with Richard J. Forrester, Dickinson College.
- DAVID KIRKPATRICK, University of British Columbia
Bit-Thrifty Algorithms for Facility Location
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
(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,
(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.
- KATTA G. MURTY, University of Michigan, Ann Arbor, MI 48109-2117, USA
New Algorithm for Linear Inequalities, Linear Programs
(LP), using no Matrix Inversions
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
>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
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.
- GODFRIED TOUSSAINT, McGill University
Facility Location and Assignment Problems with Applications
to Computational Musicology
In this lecture musical rhythm is represented symbolically, which
renders it eminently suitable for analysis from the
discrete-mathematical and computational points of view . Indeed a
rhythm timeline may be represented as a binary sequence in which each
bit denotes one unit of time, and the one-bits correspond to sounds
(striking an instrument such as a drum), whereas the zeros correspond
to silences. We consider cyclic rhythms, and thus the one-bits of the
binary sequence may be mapped to points on a circular lattice. In
this setting several problems in music theory, music information
retrieval, and computational musicology fall squarely in the domain of
operations research, as obnoxious facility location problems , ,
, as well as assignment problems defined on the circular lattice
. Here we review several obnoxious facility location problems
relevant to the design of desirable musical rhythms and scales, and
report recent results on several new versions of linear assignment
problems, from the points of view of their musical relevance and
computational efficiency , .
G. T. Toussaint,
The geometry of musical rhythm.
In: Discrete and Computational Geometry (eds. Jin Akiyama, Mikio Kano
and Xuehou Tan), Lecture Notes in Comput. Sci. 3742,
Springer-Verlag, Berlin-Heidelberg, 2005, 198-212.
J. Colannino, M. Damian, F. Hurtado, J. Iacono, H. Meijer,
S. Ramaswami and G. T. Toussaint, An O(n logn)-time
algorithm for the restriction scaffold assignment problem.
J. Comput. Biol. 13(2006), 979-989.
J. Colannino and G. T. Toussaint,
An algorithm for computing the restriction scaffold assignment
problem in computational biology.
Inform. Process. Lett. 95(2005), 466-471.
E. Erkut, T. Baptie and B. von Hohenbalken,
The discrete p-maxian location problem.
Comput. Oper. Res. 17(1990), 51-61.
S. S. Ravi, D. J. Rosenkrants and G. K. Tayi,
Heuristic and special case algorithms for dispersion problems.
Operations Research 42(1994), 299-310.
- S. P. Fekete and H. Meijer,
Maximum dispersion and geometric maximum weight cliques.
Algorithmica 38(2004), 501-511.