Web Page for:

SCHEDULE, ABSTRACTS, TALKS, and also
PHOTOS from the talks

Novel Approaches to Hard Discrete Optimization


Thursday-Saturday April 26-28, 2001

all talks to be held in Davis Center, DC-1302 (capacity 120)
Accomodation at Conference Centre, Ron Eydt Village, REV University of Waterloo
Wed. reception, all breakfasts and lunches to be held in Davis Center, DC-1301 (capacity 200, badge is your ticket)
Banquet: Friday evening from 7PM, Laurel Room in South Campus Hall, SCH, (badge is your ticket)
A Photo Album is available.


Days:
  1. Wednesday, registration and reception
  2. Thursday, sessions: R1, R2, R3, R4,
  3. Friday, sessions: F1, F2, F3, F4,
  4. Saturday, sessions: S1, S2, S3, S4,
  5. Sunday, post conference events:

    Wednesday, April 25, 2001

    6:00--10:00PM      Registration and Reception 
                       in DC 1301
    

    Thursday, April 26, 2001

    PLENARY Session R.1 Chairman: William Cunningham (Chair of C & O Dept., photo)
    10:20-10:45 Coffee Break

    Session R.2 Chairman: Kurt Anstreicher
    • 10:45--11:10 Kurt Anstreicher, (The University of Iowa)
        title: Solving Quadratic Assignment Problems Using Convex Quadratic Programming Relaxations (with N.W. Brixius, J.-P. Goux, J. Linderoth)
        ( talk photo) We describe a new approach to the Quadratic Assignment Problem (QAP) based
on the use of convex quadratic programming (QP) relaxations. These
relaxations are closely related to, but offer a number of advantages over,
the well-known projected eigenvalue (PB) bound for QAP. The QP bounds are
implemented in a complete branch-and-bound algorithm that solves problem
instances to optimality. The branch-and-bound algorithm has been
implemented using the Master-Worker (MW) distributed processing system,
allowing for the use of a large number of processors over an extended
period. The MW implementation has for the first time solved to optimality
several large benchmark QAPs, including the nug30 and tho30 problems. The
computations associated with these problems are among the largest ever
performed in solving discrete optimizations problems to optimality. Solving Quadratic Assignment Problems Using
Convex Quadratic Programming Relaxations
    • 11:15--11:40 Jonathan Eckstein, (Rutgers University),
        title: PICO: a massively parallel branch-and-bound toolbox
        ( talk photo) PICO is a general-purpose, object-oriented toolbox for expressing
branch-and-bound algorithms and executing them in parallel computing
environments.  The initial target architecture is the 'Janus'
supercomputer consisting of 4,536 nodes, each with two Pentium-II
processors, although it is designed to be portable and adaptable.
PICO is implemented in C++, using the MPI message passing interface,
and is intended to be scalable to thousands of processors.  Its key
innovations include:

(1) A novel object-oriented approach to describing branch-and-bound
algorithms, permitting many different variants of the method, for
numerous applications, to use the same underlying search 'engine'.

(2) An architecture whereby applications can first be developed
sequentially using PICO's 'serial layer', and then quickly converted
to parallel execution.

(3) A 'stride scheduler' that handles multiple asychronous parallel on
each processing node, and provides a framework for smoothly 'blending'
branch and bound with other, heuristic search methods in a parallel
environment.

We will examine a sample application of PICO to general mixed-integer
programming problems, with preliminary computational results on up to
128 processors. PICO: a massively parallel branch-and-bound toolbox
    • 10:45--12:10 Catherine Roucairol, (University of Versailles,France),
        title: Revisiting lower bounds based on linear formulations in the exact solution of the QAP (with Van-Dat Cung, Thierry Mautor, Peter Hahn, Monique Guignard-Spielberg)
        ( talk photo)  We revisit a large class of lower bounds for QAP based on a 0-1 linear formulation of the problem.  The aim of our work is to better understand and improve, where possible, the dual procedure, a method proposed by Hahn that affords easily calculated and tight lower bounds for the QAP.  First, we recall some results about the 0-1 linearization method proposed by Adams and Sherali in 1986.  Their formulation is theoretically superior to alternative published linear formulations of QAP relative to the strength of the continuous relaxation.) Second, we give an alternative presentation of the dual procedure method.  The dual procedure can be viewed as Lagrangean decomposition on the 0-1 linear formulation of QAP.  To solve the Lagrangean dual, n-square linear assignment problems of size n-1 plus one of size n are successively solved.  The multipliers are obtained not with a subgradient algorithm, but are iteratively adjusted.  The method is similar to that of Adams and Sherali, but the adjustment of multipliers is done more effectively.  Finally, we propose some improvements to the dual procedure.  We will show that, even if the recently proposed quadratic bound of Anstreicher is theoretically tighter, the dual procedure branch-and-bound requires far fewer node evaluations.  As parallelization and massive computing power seem to be the only way to go for solving larger problems (n>30), we will discuss this point. Revisiting lower bounds based on linear
formulations in the exact solution of the QAP(talk in PowerPoint Diaporama format (.pps))
    12:10-2:00 Lunch

    PLENARY Session R.3 Chairman: Panos Pardalos
    • 2:00--2:50 Resende, Mauricio (Information Sciences Research, AT&T Labs Research)
        title: GRASP with path relinking for the three-index assignment problem
        (with R.M. Aiex, P.M. Pardalos, and G. Toraldo) ( talk photo)
        This talk describes variants of GRASP 
(greedy randomized adaptive
search procedure) with path relinking for the three index assignment
problem (AP3).  GRASP is a multi-start metaheuristic for combinatorial
optimization.  It usually consists of a construction procedure based
on a greedy randomized algorithm and local search.  Path relinking is
an intensification strategy that explores trajectories that connect
high quality solutions.  Several variants of the heuristic are proposed
and tested.  Computational results show clearly that this GRASP for AP3
benefits from path relinking and that the variants considered in this
paper compare well with previously proposed heuristics for this problem.
GRASP with path relinking was able to improve the solution quality
of heuristics propsed by Balas and Saltzman (1991), Burkard, Rudolf,
and Woeginger (1996), and Crama and Spieksma (1992) on all instances
proposed in those papers.  We show that the random variable -time to
target solution,- for all proposed GRASP with path relinking variants,
fits a two-parameter exponential distribution.  To illustrate the
consequence of this, one of the variants of GRASP with path relinking
is shown to benefit from parallelization.
( This is joint work with R.M. Aiex, P.M. Pardalos, and G. Toraldo.) GRASP with path relinking for the three-index assignment problem
    • 3:00--3:50 Francisco Barahona (IBM)
        title: Branch and Cut based on the Volume Algorithm
        ( talk photo) We present a Branch-and-Cut algorithm where
the Volume Algorithm
is applied to the linear programming relaxations arising at each node of
the search tree. This means we use fast approximate solutions to these
linear programs instead of exact but slower solutions given by the
traditionally used simplex method. We present computational results
with the Max-Cut and Steiner Tree problems. We show evidence that
one can solve these problems much faster with the Volume Algorithm
based Branch and Cut code than with a dual simplex based one.
(This is joint work with Laszlo Ladanyi.)
    3:50-4:45 Coffee Break

    Session R.4 Chairman: Miguel Anjos


    Friday, April 27, 2001 ( photos)

    7:30--8:30        Breakfast
    
    PLENARY Session F.1 Chairman: Tony Vannelli
    10:20-10:45 Coffee Break

    Session F.2 Chairman: Yin Zhang
    • 10:45--11:10 Sam Burer, (Georgia Tech)
        title: Maximum Stable Set Formulations and Heuristics Based on Continuous Optimization, (with Monteiro and Zhang) ( talk photo) 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. Maximum Stable Set Formulations and Heuristics Based on Continuous Optimization
    • 11:15--11:40 Yin Zhang (Rice University)
        title: Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs (With R. Monteiro and Burer)
        ( talk photo) Semidefinite relaxation for certain discrete optimization problems
involves replacing a vector-valued variable by a matrix-valued one,
producing a convex program while increasing the number of variables by
an order of magnitude.  As useful as it is in theory, this approach
encounters difficulty in practice as problem size increases. In this
paper, we propose a rank-two relaxation approach and construct
continuous optimization heuristics applicable to some binary quadratic
programs, including primarily the Max-Cut problem but also others such
as theJ. Abello,  Max-Bisection problem.  A computer code based on our rank-two
relaxation heuristics is compared with two state-of-the-art
semidefinite programming codes.  We will report some rather intriguing
computational results on a large set of test problems and discuss
their ramifications. Rank-Two Relaxation Heuristics for Max-Cut and
Other Binary Quadratic Programs
    • 10:45--12:10 Sergiy Butenko (University of Florida, butenko@ufl.edu)
        title: Finding Independent Sets in a Graph Using Continuous Multivariable Polynomial Formulations
        (with J. Abello, Panos Pardalos, and M.G.C. Resende)
        ( talk photo) Two continuous formulations of the maximum
independent set problem on a
graph G=(V,E) are considered.  Both cases involve the maximization of
an N-variable polynomial over the N-dimensional unit hypercube, where N
is
the number of nodes in G. Two (polynomial) objective functions F(X) and
H(X) are considered.  Given any solution X in the hypercube, we propose
polynomial-time algorithms, based on these formulations, for finding
maximal independent sets with cardinality greater than or equal to F(X)
and H(X), respectively. A relation between two approaches is studied.
Results of computational experiments for some
of the DIMACS clique benchmark graphs are presented.  Finally, a more
general statement for dominating sets is proved.
    12:10-2:00 Lunch

    PLENARY Session F.3 Chairman: Henry Wolkowicz
    3:50-4:45 Coffee Break

    Session F.4 Chairman: Franz Rendl
    Special Session on: Bundle Methods and Lagrangian Duality
    (
    talk photo1 (the Austrians)), ( talk photo1a (more Austrians)), ( talk photo2) We consider the problem of maximizing a concave function $c:\R^{n} \to \R$
 subject to finitely many constraints. In particular, given
 $c:\R^{n} \to \R$, $A \in \R^{m \times n}$, $b \in \R^{m}$ and a convex
 set $X$ we deal with
 \begin{eqnarray}
   {\rm {\bf (P)}} \qquad  & \max & \!\!\!\!  c(x) \nonumber  \\ 
   & \mbox{s.t.} &\!\!\!\! x \in X \nonumber   \\ 
   &&\!\!\!\!  Ax \leq b. \nonumber
 \end{eqnarray}
 The number of constraints $m$ could be very large, hence solving {\bf (P)}
 directly is too difficult. The goal is selecting
 important inequalities of $Ax \leq b$ to get a good approximation of the original
 problem. We present a method which leads to such an approximation in reasonable time.
We use this method to solve combinatorial optimization problems which  
fit into this framework such as Max-Cut and QAP. For these two problems numerical results will be presented. Special Session on: Bundle Methods and
Lagrangian Duality and also Special Session on: Bundle Methods and
Lagrangian Duality
    • 4:45--5:45
      Gerald Gruber (Universitaet Klagenfurt)
        title I: Solving hard optimization problems with linear inequality constraints using bundle methods, ( talk photo)
      Ilse Fischer (Universitaet Klagenfurt)
        title II: Solving hard optimization problems with linear inequality constraints using bundle methods, ( talk photo)
      Renata Sotirov (Universitaet Klagenfurt)
        title III: Solving QAP using bundle methods

    6:00PM -- on            pre-Banquet goodbye party for Adrian Lewis (grad house)
     photo1  photo2  photo3  photo4  photo5  photo6  photo7
    7:00PM -- on            Banquet at Laurel Room in South Campus Hall
     Banquet PICS
    

    Saturday, April 28, 2001

    7:30--8:30        Breakfast
    
    PLENARY Session S.1 Chairman: Francisco Barahona
    10:20-11:15 Coffee Break

    Session S.2 Chairman: Kees Roos
    • 11:15--11:40 Kartik Krishnan ( Dept. Math. Sc. Rensselaer Polytechnic Institute)
        title: A Linear Programming Approach to Semidefinite Problems (With John Mitchell)
        A semidefinite programming problem can be regarded as a convex nonsmooth optimization problem, 
so it can be represented as a semi-infinite linear programming problem. 
Thus, in principle, it can be solved using a cutting plane approach; 
we describe such a method. 
The cutting plane method uses an interior point algorithm to solve the linear programming relaxations approximately, 
because this resulted in the generation of better constraints than a simplex cutting plane method.
Further, the bundle method of Helmberg and Rendl can be used to generate a set of linear constraints. 
Typically, these alone are not sufficient to give a good linear programming relaxation. 
Nonetheless, if they are used in conjunction with some families of problem specific constraints, 
tight LP relaxations can be obtained. A Linear Programming Approach to Semidefinite
Problems
    • 11:45--12:10 Kees Roos (TU Delft/University of Leiden)
        title: Maximization of a quadratic form over the intersection of ellipsoids with common center (with Arkadi Nemirovski and Tamas Terlaky)
        We demonstrate that if $A_1,...,A_m$ are 
symmetric positive semidefinite
$n\times n$ matrices with positive definite sum and $A$ is an arbitrary symmetric
$n\times n$ matrix, then the relative accuracy, in terms of the optimal value, of
the semidefinite relaxation
$$
\max_X \{\Tr(AX)\mid\, \Tr(A_iX)\le1, i=1,...,m; X\succeq0\} 
$$
of the optimization program
$$
x^TAx\to\max\mid x^TA_ix \le 1, i=1,...,m 
$$
is not worse than $1-{1\over{2\ln(2m^2)}}$. It is shown that this bound is sharp
in order, as far as the dependence on $m$ is concerned. Maximization of a quadratic form over the
intersection of ellipsoids with common center
    12:10-2:00 Lunch

    Session S.3 Chairman: Jean-Louis Goffin
    4:00-4:25 Coffee Break

    Session S.4 Chairman: William Cook


    Post-Workshop Events




    Photo Album
    Back to Workshop Home Page
    , by Henry Wolkowicz