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