Seminar on
Applied Mathematics
PROGRAM
Utorak, 30.03.2004. u 14:15, sala 2 SANU:
Leo Liberti, DEI, Politecnico di Milano, Italy
METAHEURISTICS APPLIED TO THE MINFCB PROBLEM:
NUMERICAL EXPERIENCES WITH VNS AND TABU SEARCH
Abstract:
A cycle basis of a simple biconnected graph G is fundamental if,
given a spanning tree of G, each cycle in the basis has a unique
co-tree edge. Finding the fundamental cycle basis (FCB) of minimum
cost is an NP-hard problem. We propose a local search based on an
edge-swapping move, and insert said local search in various
metaheuristic frameworks. In particular, we perform an in-depth
computational analysis of the performances of VNS and Tabu Search,
based on the aforementioned edge-swapping move.
Takodje pozivamo sve zainteresovane da prisustvuju jos jednom
predavanju ovog autora koje ce biti odrzano na zajednickom
sastanku Odeljenja za matematiku MI SANU i Opsteg matematickog
seminara na Matematickom fakultetu:
Petak, 26.03.2004. u 14h, RL ili sala 718, Matematicki fakultet :
Leo Liberti, DEI, Politecnico di Milano, Italy
DETERMINISTIC GLOBAL OPTIMIZATION OF CONTINUOUS NONCONVEX
PROGRAMMING PROBLEMS
Abstract:
Many real-life problems are nonconvex, and therefore present many
complicating features, including multiple local minima. One of the
most widely used deterministic techniques for the global solution
of continuous nonconvex problems is spatial Branch-and-Bound. We
describe a spatial B&B algorithm where the convex relaxation at each
node is built with the help of symbolic computation, and discuss a
family of tightening cuts that significantly accelerate the
convergence of the algorithm on a wide class of bilinear nonconvex
problems.
RUKOVODIOCI SEMINARA
Vera Kovacevic-Vujcic
Milan Drazic