Full text
| |
| Author(s): |
Andrei de Almeida Sampaio Braga
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2011-02-09 |
| Examining board members: |
Cid Carvalho de Souza;
Antonio Carlos Moretti;
Flávio Keidi Miyazawa
|
| Advisor: | Cid Carvalho de Souza |
| Abstract | |
The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm (AU) | |
| FAPESP's process: | 08/03285-8 - Lagrangian relaxations and cutting planes in solving set partitioning problems |
| Grantee: | Andrei de Almeida Sampaio Braga |
| Support Opportunities: | Scholarships in Brazil - Master |