Recent News and Developments

From: Kurt Anstreicher 

Dear colleagues:

We are pleased to announce the exact solution of the "nug30" quadratic
assignment problem (QAP). This problem was first posed in the paper

C.E. Nugent, T.E. Vollman, and J. Ruml, "An experimental comparison of
techniques for the assignment of facilities to locations," Operations
Research 16 (1968) pp. 150-173,

and has long been considered an outstanding open "challenge problem" in the
optimization literature. The problem data is available from QAPLIB
(http://www.imm.dtu.dk/~sk/qaplib).

The problem was solved using the branch-and-bound algorithm described
in the paper "Solving quadratic assignment problems using convex
quadratic programming relaxations," N.W. Brixius and K.M. Anstreicher,
available at http://www.biz.uiowa.edu/faculty/anstreicher/qapqp2.ps. It was
implemented using the Master-Worker (MW) distributed processing system
developed in the metaNEOS project and described in the paper 
"An enabling framework for master-worker computing applications on the
computational grid," J.-P. Goux, S. Kulkarni, J. Linderoth, and M. Yoder,
available from http://www.mcs.anl.gov/metaneos/papers/mw2.ps.

The computation was performed on a dynamic grid of workstations, massively
parallel processors, and other CPUs using the Condor high-throughput
computing system developed at the University of Wisconsin, together 
with tools from the Globus toolkit. The total wall-clock time was 
approximately 6.9 days. The number of worker machines averaged 
approximately 650, and peaked at 1009. Machines from the following 
institutions participated in the computation (listed in order of CPU 
seconds contributed):

University of Wisconsin, 
Argonne National Laboratory, 
Georgia Institute of Technology Interactive High Performance Computing
Laboratory, 
National Center for Supercomputing Applications (NCSA), 
Italian Istituto Nazionale di Fisica Nucleare (INFN), 
Albuquerque High Performance Computing Center, 
Northwestern University, 
Columbia University. 

A total of 3.46E8 CPU seconds was expended by worker machines. The
equivalent computation time on a single HP-C3000 workstation would be
approximately 6.9 years.

According to QAPLIB a permutation with an objective value of 6124 was first 
obtained by J. Skorin-Kapov, see

J. Skorin-Kapov, "Tabu search applied to the quadratic assignment problem," 
ORSA J. Computing 2 (1990), pp. 33-45.

The branch-and-bound computation was initialized with an incumbent
objective value of 6126, and required 11,892,208,412 nodes. The B&B
process verified that 6124 is the optimal value for the problem, and
found the following permutation with this value:

14,5,28,24,1,3,16,15,10,9,21,2,4,29,25,22,13,26,17,30,6,20,19,8,18,7,27,12,1
1,23

Full details of the distributed branch-and-bound implementation
using the MW system will be given in a paper under preparation.

Further information can be found at the following URLs:
Condor:   http://www.cs.wisc.edu/condor/
metaNEOS: http://www.mcs.anl.gov/metaneos/
MW :      http://www.cs.wisc.edu/condor/mw
Globus:   http://www.globus.org/

We are extremely grateful to Steve Wright of Argonne National Lab, and
Miron Livny of the University of Wisconsin, for their ongoing support of
this research.

Kurt Anstreicher, University of Iowa
Nathan Brixius,   University of Iowa
Jean-Pierre Goux, Northwestern University and Argonne National Lab
Jeff Linderoth,   Argonne National Lab

Dear Colleagues,

The Krarup 30b instance of the Quadratic Assignment Problem was just
solved at the University of Pennsylvania using the dual procedure
branch-and-bound algorithm (Hahn-Grant bound) in the equivalent of 182
days (15,737,136 seconds) on a single cpu HP-3000 workstation.   Actual
runtimes were;

13,806,183 seconds on the HP-3000
  3,861,905 seconds on a 350 MHz UltraSparc 10 (about 1/2 as fast as the
HP-3000)

A total of 183,659,980 nodes were evaluated.

This compares to the parallel solution of this problem instance by
Kurt Anstreicher, University of Iowa
Nathan Brixius,   University of Iowa
Jean-Pierre Goux, Northwestern University and Argonne National Lab
Jeff Linderoth,   Argonne National Lab
which took the equivalent of 2.7 years on a single cpu HP-3000
workstation and required the evaluation of 5,136,036,412 nodes.

Peter Hahn
Systems Engineering Department
School of Engineering and Applied Science

Monique Guignard-Spielberg
Operations and Information Management Department
The Wharton School

Announcing the technical report:

  Maximum Stable Set Formulations and Heuristics
       Based on Continuous Optimization

By Sam Burer, Renato Monteiro, Yin Zhang

Technical Report TR00-34
Department of Computational and Applied Mathematics,
Rice University, Houston, Texas 77005

The postscript file can be obtained from:
http://www.caam.rice.edu/~zhang/reports/tr0034.ps

Thank you.

-- Yin Zhang
zhang@caam.rice.edu


Abstract:

The stability number for a given graph $G$ is the size of a maximum
stable set in $G$.  The Lovasz theta number provides an upper bound on
the stability number and can be computed as the optimal value of the
Lovasz semidefinite program.  In this paper, we show that restricting
the matrix variable in the Lovasz semidefinite program to be rank-one
or rank-two yields a pair of continuous, nonlinear optimization
problems each having the global optimal value equal to the stability
number.  We propose heuristics for obtaining large stable sets in $G$
based on these new formulations and present computational results
indicating the effectiveness of the heuristics.

Announcing a new report....

Computational experience with Stable Set Relaxations


Gerald Gruber, Franz Rendl 

Research Report, Department of Mathematics,
University of Klagenfurt, Austria, December 2000

We investigate relaxations for the maximum stable set
problem based on the Lov$\acute{{\rm a}}$sz number 
$\vartheta (G)$ as an initial upper bound.  
We strengthen this relaxation by adding two
classes of cutting planes, odd circuit and triangle 
inequalities.  We present computational results using 
this tighter model on many classes of graphs. 


URL of the dvi file: -
URL of the ps file: http://www.uni-klu.ac.at/groups/math/optimization/pub_en.html/

Contact: gerald.gruber@uni-klu.ac.at

From Tamas Terlaky, terlaky@mcmaster.ca Sat Dec 23 11:09:15 2000
Date: Wed, 29 Nov 2000 23:42:06 -0500
Subject: Conference announcement


  1st Annual McMaster Optimization Conference:
            Theory and Applications
                  (MOPTA 01)
      August 2-4, 2001, McMaster University
            Hamilton, Ontario, Canada


The 1st annual McMaster Optimization Conference, (MOPTA 01)
will be held at the campus of McMaster University. It will
be hosted by the Advanced Optimization Lab at the
Department of Computing and Software.

 
SCOPE
The conference is planned as an annual event aiming to
bring together a diverse group of people from both discrete
and continuous optimization, working on both theoretical
and applied aspects. The format will consist of a small
number of invited talks from distinguished speakers and a
set of selected contributed talks, spread over three days
with no parallel sessions. Our target is to present a
diverse set of exciting new developments from different
optimization areas while at the same time providing a
setting which will allow increased interaction among the
participants. We aim to bring together researchers from
both the theoretical and applied communities who do not
usually get the chance to interact in the framework of a
medium-scale event.

INVITED TALKS:
Distinguished guests will give one-hour long invited talks.
Confirmed invited speakers include:
       John Dennis (Rice University)
       Michael Todd (Cornell University)
       Lieven Vandenberghe (UCLA)
       David Williamson (IBM Almaden)

CONTRIBUTED TALKS:
Contributions are solicited for presentation at the conference.
Each accepted paper will be alloted a 25 minute talk.
Presentation of recent results is encouraged. Authors wishing
to speak at the conference should submit the abstract on which
the talk will be based, in ASCII or LaTex source, to
           terlaky@mcmaster.ca
            by April 30, 2001.
Please use "MOPTA" in the email subject line.
All decisions on acceptance will be made after the closing day of April
30, 2001. A preliminary program will be available before the end of May.

ORGANIZING COMMITTEE
The Organizing Committee
Tamas Terlaky, terlaky@mcmaster.ca (Chair)
Stavros Kolliopoulos (CAS, McMaster University)
Tom Luo (ECE, McMaster University)
Henry Wolkowicz (Comb. Opt. University of Waterloo)
*********************************************************
Prof. Tamas  Terlaky
Department of Computing and Software, Office: JHE/214
McMaster University
Hamilton, Ontario, Canada, L8S 4L7
Phone: +1-905 525-9140 ext. 27780, FAX: +1-905 524-0340
Email: terlaky@cas.mcmaster.ca
www: http://www.cas.mcmaster.ca/~terlaky
********************************************************
A new journal OPTIMIZATION AND ENGINEERING is established
The first issue is on the WEB! Please look at the home page:
http://ssor.twi.tudelft.nl/~terlaky/OPTE/opte.html
http://www.cas.mcmaster.ca/~terlaky/OPTE/opte.html
http://fmad-www.larc.nasa.gov/mdob/users/natalia/opte
********************************************************