Proposal for a Workshop on

Novel Approaches to Hard Discrete Optimization

Organizers:

  • Kurt Anstreicher, The University of Iowa.
  • Panos Pardalos, University of Florida.
  • Franz Rendl, Universitaet Klagenfurt.
  • Tony Vannelli, University of Waterloo.
  • Henry Wolkowicz, University of Waterloo.

    Dates:

    Thursday to Saturday, April 26-28, 2001.

    Format/ Schedule:


    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:

    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:


    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.

    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:

    Total funding sought $ 23,764.:



    back to workshop home page