| |
|
Description: |
In this presentation, we discuss the application of column generation based algorithms to three multicommodity flow problems (MFP). In this type of problems, it is desired to route a set of commodities through a capacitated network at a minimum cost.
In the linear MFP, each unit of each commodity is divisible. We present an extended model with variables associated with paths and circuits and a column generation algorithm for planar instances.
We propose a branch-and-price algorithm for the integer MFP, where each unit of each commodity is indivisible; the flow of a commodity can be split between different paths, but the flow on each of those paths must be integer.
In the binary MFP, all the flow of each commodity must be routed along a single path. We discuss two branch-and-price algorithms based different decompositions.
We report on computational results for the three problems.
We discuss some of the issues involved when using column generation in Linear and Integer Programming, namely when applied to models resulting from Dantzig-Wolfe decomposition / Lagrangean Relaxation. We also describe the software ADDing (???Automatic Dantzig-wolfe Decomposition for INteger column Generation???), which is a C++ implementation of a generic branch-and-price algorithm.
We conclude the presentation with some future research topics.
Area(s):
|
|
Date: |
|
| Start Time: |
14.30 |
|
Speaker: |
Filipe Alvelos (Departamento de Produção e Sistemas, Universidade do Minho)
|
|
Place: |
Room 5.5
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
