Branch-and-price and multicommodity flows

Abstract

In this Thesis, we address column generation based methods for linear and integer programming and apply them to three multicommodity flow problems. For (mixed) integer programming problems, the approach taken consists in reformulating an original model, using the Dantzig-Wolfe decomposition principle, and then combining column generation with branch-and-bound (branch-and-price) in order to obtain optimal solutions. The main issue when developing a branch-and-price algorithm is the branching scheme. The approach explored in this work is to branch on the variables of the original model, keeping the structure of the subproblems of the column generation method unchanged. The incorporation of cuts (branch-and-price-and-cut), again without changing the structure of the subproblem, is also explored. Based on that general methodology, we developed a set of C++ classes (ADDing - Automatic Dantzig-Wolfe Decomposition for INteger column Generation), which implements abranch-and-price algorithm. Its main distinctive feature is that it can be used as a “black-box”: all the user is required to do is to provide the original model. ADDing can also be customised to meet a specific problem, if the user is willing to provide a subproblem solver and/or specific branching schemes. We developed column generation based algorithms for three multicommodity flow problems. 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 problem, each unit of each commodity is divisible. By using a model with variables associated with paths and circuits, we obtained significant improvements on the solution times over the standard column generation approach, for instances defined in planar networks (in several instances the relative improvement was greater than 60%). In the integer problem, 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 general, the proposed branch-and-price algorithm was more efficient than Cplex 6.6 in the sets of instances where each commodity is defined by an origin-destination pair; for some of the other sets of instances, Cplex 6.6 gave better time results. In the binary problem, all the flow of each commodity must be routed along a single path. We developed a branch-and-price algorithm based on a knapsack decomposition and modified (by using a different branching scheme) a previously described branch-and-price-and-cut algorithm based on a path decomposition. The outcome of the computational tests was surprising, given that it is usually assumed that specific methods are more efficient than general ones. For the instances tested, a state-of-the-art general-purpose (Cplex 8.1) gave, in general, much better results than both decomposition approaches.

Nesta Tese, abordam-se métodos de geração de colunas para programação linear e inteira. A sua aplicação é feita em três problemas de fluxo multicomodidade. Para problemas de programação inteira (mista), a abordagem seguida é a de reformular um modelo original, utilizando o princípio de decomposição de Dantzig-Wolfe, e combinar geração de colunas com o método de partição e avaliação (partição e geração de colunas) para a obtenção de soluções óptimas. A questão essencial no desenvolvimento de um algoritmo deste tipo é a estratégia de partição. A abordagem seguida neste trabalho é a de realizar a partição nas variáveis do modelo original, mantendo a estrutura do subproblema do método de geração de colunas. A incorporação de cortes, ainda sem alteração da estrutura do subproblema, é também explorada. Com base nesta metodologia geral, foi desenvolvido um conjunto de classes em C++ (ADDing - Automatic Dantzig-Wolfe Decomposition for INteger column Generation), que implementa um algorithmo de partição e geração de colunas. A sua característica fundamental é apenas ser requerido ao utilizador a definição de um modelo original. Num modo mais avançado, o utilizador pode implementar algoritmos para resolver o subproblema e/ou esquemas de partição. Foram desenvolvidos algoritmos baseados em geração de colunas para três problemas de fluxo multicomodidade. Neste tipo de problemas, pretende-se encaminhar um conjunto de comodidades através de uma rede capacitada, minimizando o custo. No problema linear, cada unidade de cada comodidade é divisível. Utilizando um modelo com variáveis associadas a caminhos e a circuitos, obtiveram-se melhorias significativas nos tempos de resolução em relação ao método de geração de colunas usual, para instâncias definidas em redes planares (em várias instâncias a melhoria relativa foi superior a 60%). No problema inteiro, cada unidade de cada comodidade é indivisível; o fluxo de uma comodidade pode ser dividido por diferentes caminhos, mas o fluxo em cada um deles tem de ser inteiro. Em geral, o algoritmo de partição e geração de colunas foi mais eficiente do que o software Cplex 6.6 nos conjuntos de instâncias em que cada comodidade é definida por um par origem-destino; para alguns dos outros conjuntos de instâncias, o software Cplex 6.6 obteve melhores resultados. No problema binário, todo o fluxo de cada comodidade apenas pode utilizar um caminho. Foi desenvolvido um algoritmo de partição e geração de colunas baseado numa decomposição de mochila e modificado (através de um esquema de partição diferente) um algoritmo de partição e geração de colunas com cortes, previamente descrito, baseado numa decomposição por caminhos. Os resultados dos testes computacionais foram surpreendentes, dado que é usualmente assumido que métodos específicos são mais eficientes do que métodos gerais. Para as instâncias testadas, o software Cplex 8.1 obteve, em geral, resultados muito melhores do que as duas decomposições.