Henry Wolkowicz, University of Waterloo.
Dates:
Thursday to Saturday, April 26-28, 2001.
Format/
Schedule:
10 plenary talks, 60 minute slots
20 contributed talks, 30 minute slots
Aim:
Linear Programming is the basis for the by now
classical approach to deal with hard combinatorial optimization problems.
This approach has turned out powerful for problems like the
Traveling Salesman Problem, but for other types of problems,
such as Graph Partition or Quadratic Assignment problems (QAP)), the linear
relaxations either seem too weak or too expensive.
On the other hand, the success
of interior point methods that deal with constrained nonlinear problems
has led to increased interest in
algorithmic nonlinear optimization in the last 15 years.
In the last few years, cone LP and in particular Semidefinite programming
(SDP) have turned out to be powerful tools in various branches of
applied mathematics, notably for combinatorial optimization
(Goemans-Williamson approximation for Max-Cut) and in System and
Control theory. SDP has become a bridge between combinatorial
optimization and nonlinear programming.
The breathtaking progress in algorithmic nonlinear optimization,
but also in computer hardware has thrown new light on the analysis
of NP-hard problems. Recently, a major break-through was achieved
to solve QAP of sizes (n=30) unthinkable by conventional methods.
This progress was due in part to a new nonlinear relaxation for QAP,
but also to new computing facilities, allowing for massive parallel
computation. Similar progress is also made in other areas, such as
clique and coloring on massive graphs.
The aim of the workshop is therefore to bring together researchers
from several communities, such as:
- algorithmic nonlinear optimization
- combinatorial optimization, dealing with computational methods for
NP-hard problems
- computer scientists interested in scientific parallel computing,
who share a common interest to do computations on (large-scale)
hard combinatorial optimization problems.
The workshop will follow in spirit previous workshops such as:
Topics:
-
Quadratic and multi-dimensional assignment problems
-
Boolean quadratic programming
-
Semidefinite programming and reformulation schemes
-
Massive graph problems
-
Massively parallel distributed processing
-
VLSI design
Related Experience:
We briefly give some of the related experience of the organizers. The
references can be found from clicking on their names
to get to their web pages.
-
Kurt Anstreicher
is well known for his work on interior point methods. His
recent interests have included methods for discrete nonlinear problems
based on nonlinear convex relaxations. A method of this type for the QAP
recently solved the famous "nug30" problem, posed in 1968.
-
Franz Rendl
is well known for his work in combinatorial optimization. He
is one of the best known researchers on QAP. He has been
involved in many of the early as well as
recent results, including
survey papers
(e.g.
on QAP with Pardalos and Wolkowicz), and
QAPLIB.
-
Panos Pardalos
has organized many workshops in combinatorial optimization. He
has developed
many algorithms for nonlinear assignment problems, maximum
clique problems and introduced novel continuous approaches to solve
discrete problems. Here is a list of some
relevant publications.
-
Tony Vannelli is currently
Chair, Department of Electrical and Computer Engineering. He has worked
on: Development of Circuit Layout Algorithms;
Interior Point Algorithms in Engineering Design;
Tabu Search and Annealing Approaches for Combinatorial Optimization;
and Cellular Manufacturing.
-
Henry Wolkowicz
is interested in semidefinite programming and also nonlinear programming
in general. He
(with Panos Pardalos) was an organizer of:
A proceedings of refereed invited papers is planned.
Invitees:
Invited speakers list
General invitations have been sent out over the various relevant
newsgroups on the internet.
Budget:
All Canadian participants are NSERC funded. So, we are
seeking travel funds and accomodation costs
for foreign speakers, a few student participants, a banquet,
coffee breaks, and a modest reception.
There are (as of January 23, 2001) 42
registered participants.
(However, we expect at least 20 more.)
We also plan on providing breakfast and lunch at
the conference. (This will encourage early arrival and participation.)
The plan is to pay travel expenses for just a few of the invited
speakers and concentrate on helping with accomodation costs at the
local conference center.
This will be at the University of Waterloo
Conference Centre, which is located on campus and is a short walking
distance to the talks.
There will be no conference registration. (This was announced in the
first advertisement, Sept/00).
The following estimates are made for 60 participants and 30 speakers:
-------------------------------------
Foreign speakers travel costs (14-16): 9000.00
Student participants travel costs (14-16): 3000.00
Accomodations for speakers for 4 nights at 41.90 per plus taxes: $ 5782.20
Reception at $5.65 per $ 339.00
Coffee at $1.85 per $
Breakfast at $5.05 per $ 909.00
Lunch at $11.55 per $ 2079.00
Banquet at $20.95 per plus $65 setup cost $ 1322.00
incidentals (publishing): 1000.00
-------------------------------------
Total costs 23764.20
Total funding sought $ 23,764.:
$ 10,000 from Faculty of Mathematics, University of Waterloo
$ 12,500 from Fields Institute (promised)
$ 1,000 from personal research operating grants.
back to workshop home page