SCIENTIFIC PROGRAMS AND ACTIVITIES
April 16, 2024

Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems

SCHEDULE --
(You can also see the abstracts for the talks.)

May 15- Friday 17, 1996

to be held at The Fields Institute, Toronto, Ontario, Canada

Supported jointly by Fields Institute and CRM

 

Tuesday, May 14, 1996
6:00--8:00PM Registration and Reception
2nd Floor Fields Institute
Wednesday, May 15, 1996
8:15--8:20 Opening Remarks

8:20--8:30 Welcome from the Director of the Fields Institute,
John Chadam
Session W.1 Chairman: P. Pardalos
  • 8:30-- Monique Laurent
    A connection between positive semidefinite and Euclidean distance matrix completion problems
  • 9:00-- Charles Johnson
    Recent progress on non-positive definite matrix completion problems
  • 9:30-- Stefan Karisch (speaker) and F. Rendl
    Semidefinite Programming and Graph Equipartition
  • 10:00-- Kees Roos (speaker), Tamas Terlaky, Etienne de Klerk
    Initialization in semidefinite programming via a self-dual embbedding

10:30-10:50-- Break

Session W.2 Chairman: J. Cheriyan
  • 10:50 -- C. Helmberg (speaker), F. Rendl, R. Weismantel
    Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming
  • 11:20 -- Philip Klein and Hsueh-I Lu (speaker)
    Fast approximation algorithms for some semidefinite relaxations arising from combinatorial optimization problems (principally, MAX CUT and COLORING)
  • 11:50 -- Lieven Vandenberghe (speaker), Stephen Boyd, Shao-Po Wu
    Determinant Maximization with linear matrix inequality constraints

12:20-1:50-- Lunch

Session W.3 Chairman: H. Wolkowicz
  • 1:50 -- F. Rendl (speaker) and C. Helmberg
    Large Scale SDP using eigenvalues
  • 2:20 -- Zhi-Quan Luo (speaker) Jos F. Sturm and Shuzhong Zhang
    Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming

2:50-3:20 -- Break

Session W.4 Chairman: J. Cheriyan
  • 3:20 -- Gabor Pataki
    Cone-LP's and Semidefinite Programs: Geometry and a Simplex-type Method
  • 3:50 -- J.P. Warners, T. Terlaky(speaker), C. Roos, B. Jansen
    Potential reduction algorithms for structured combinatorial optimization problems
  • 4:20 -- Lorant Porkolab (speaker) and Leonid Khachiyan
    Bounds on Feasible Solutions of Semidefinite Programs

6:20 -- Conference Reception, at the Fields Institute

Thursday, May 16, 1996
Session R.1 Chairman: L. Tuncel
  • 8:30-- Mauricio G.C. Resende (speaker) and Panos Pardalos
    Using linear programming to help solve quadratic assignment problems
  • 9:00-- Michael J. Todd (speaker), Kim Chuan Toh, Reha H. Tutuncu,
    On the Nesterov-Todd direction in semidefinite programming
  • 9:30-- John E. Mitchell
    Using an Interior Point Algorithm in a Cutting Plane Method for Solving Integer Programming Problems
  • 10:00-- Qing Zhao (speaker), Stefan E. Karisch, Franz Rendl, Henry Wolkowicz
    Semidefinite Programming Relaxations for the Quadratic Assignment Problem

10:30-10:50-- Break

Session R.2 Chairman: T. Vannelli
  • 10:50 -- Leonid Faybusovich
    Infinite-dimensional semidefinite programming: self-concordant barriers and path-following algorithms for Semidefinite Programming
  • 11:20 -- Chih-Jen Lin and Romesh Saigal (speaker)
    An infeasible start predictor corrector method for semidefinite linear programming
  • 11:50 -- LE THI Hoai An and PHAM DINH Tao (speaker)
    D.c. (difference of convex functions) Optimization: Theory, Algorithms & Aplications

12:20-1:50-- Lunch

Session R.3 Chairman: H. Wolkowicz
  • 1:50 -- A. Shapiro
    SECOND ORDER OPTIMALITY CONDITIONS AND STABILITY ANALYSIS OF SEMI-DEFINITE PROGRAMS
  • 2:20 -- Jos F. Sturm and Shuzhong Zhang (speaker)
    Symmetric primal-dual path following algorithms for SDP

2:50-3:20 -- Break

Session R.4 Chairman: P. Pardalos
  • 3:20 -- Boris Mirkin
    Approximation Clustering: A Mine of Semidefinite Programming Problems
  • 3:50 -- Jonas MOCKUS, Audris MOCKUS, Linas MOCKUS (speaker)
    BAYESIAN APPROACH TO COMBINATORIAL OPTIMIZATION
  • 4:20 -- Arjan Berkelaar (speaker) and Shuzhong Zhang
    Convergence Issues and Path-following Algorithms for Semidefinite Programming
  • 5:10 -- Dimitris Bertsimas
    Bounds and policies for dynamic optimization via semidefinite and infinite linear programming
Friday, May 17, 1996
Session F.1 Chairman: H. Wolkowicz
  • 8:30-- Kees Roos, Tamas Terlaky, Etienne de Klerk (speaker)
    Method of approximate centers for semidefinite programming
  • 9:00-- Zhi-Quan Luo Jos F. Sturm (speaker) and Shuzhong Zhang
    Duality and self-duality for semidefinite and conic convex programming
  • 9:30-- . Goldfarb and K. Scheinberg (speaker)
    Interior Point Trajectories in Semidefinite Programming
  • 10:00-- Ding-zhu Du
    On Floorplan Design and Optimization

10:30-10:50-- Break

Session F.2 Chairman: P. Pardalos
  • 10:50 -- Yinyu Ye
    On the complexity of approximating a KKT point of quadratic programming
  • 11:20 -- Manuel A. Nunez (speaker) and Robert M. Freund
    Condition Measures and Properties of the Central Trajectory of a Semidefinite Program
  • 11:50 -- LE THI Hoai An (speaker) and PHAM DINH Tao
    An efficient adapted DCA and Branch-and-Bound algorithm for globally solving large-scale 0-1 quadratic programming problems

12:20-1:50-- Lunch

Session F.3 Chairman: T. Vannelli
1:50 -- Jun Gu
Optimization Algorithms for Satisfiability (SAT) Problem 2:20 -- M. R. Emamy-K.
How efficient can we maximize threshold pseudo-Boolean functions?
2:50-3:20 -- Break
Session F.4 Chairman: L. Tuncel
3:20 -- M. Ramana
Recognition of Polyhedral Semidefinite Programs
3:50 -- Renato Monteiro
Primal-Dual Path Following Algorithms for Semidefinite Programming
4:20 -- Yin Zhang
Some Thoughts on Primal-Dual Interior-Point Methods for Semidefinite Programming
5:10 -- Laura Palagi (speaker) and Stefano Lucidi
Trust region Problems: Theoretic Results and New Algorithmic Developments