[APDIO] Palestra Prof. Filipe Alvelos, INESC Porto, 3ª feira - 17 de Maio, 13h

[aviana <aviana@inescporto.pt>]

Bom dia,

Na próxima 3ª feira, 17 de Maio, pelas 13h terá lugar no Auditório do INESC Porto uma sessão tutorial sobre o método de Geração de Colunas.
A sessão estará a cargo do Prof. Filipe Alvelos (Universidade do Minho).

A entrada é livre mas, por questões logísticas, agradecemos aos
potenciais interessados em estar presentes que o comuniquem a Marta
Oliveira (mio@inescporto.pt) até ao dia 16 de Maio.


Cumprimentos,


Ana Viana




* Title: Column generation based approaches for combinatorial optimization problems
  * Type:  Invited talk / Tutorial
  * Author: Filipe Pereira e Alvelos (Universidade do Minho)
  * Date: Tuesday, May 17th, 2011, 13h00  (INESC Porto, auditório)
  * Keywords: Column generation; Combinatorial optimization
  * Abstract: 
In this talk, we discuss the use of column generation (CG) in exact
and approximate methods for solving integer programming and
combinatorial optimization problems.

CG is a decomposition method driven by linear programming where the
subproblems can be tackled by any optimization algorithm. The
combination of CG and branch-and-bound (branch-and-price) results in
an exact method for integer programming / combinatorial optimization,
whose main issues are discussed and illustrated with problems arising
in (i) telecommunications networks, (ii) industries where it is
crucial to minimize the waste of cutting operations, and (iii) forest
management.

Next, approximate methods based on CG are discussed. In particular, a
framework for combining column generation and metaheuristics,
"SearchCol: Metaheuristic search by column generation", is
addressed. In each iteration of a SearchCol algorithm, CG provides the
optimal solution (primal and dual) to a metaheuristic which returns a
(incumbent) solution used for defining a (perturbed) CG problem for
the next iteration.  In the last part of the talk, a C++ framework for
integer programming and combinatorial optimization for implementing
column generation based approaches for general and specific problems
is briefly described.