University of Twente Student Theses
Odd-Cycle Separation for Set Cover
Smit, K.W. de (2021) Odd-Cycle Separation for Set Cover.
|
PDF
3MB |
| Abstract: | To investigate a potential decrease of computation time of mixed-integer linear programs, we implement a separation algorithm which is then added to the solution process. The separation algorithm uses odd-cycle inequalities for set cover constraints. To find the odd-cycle inequalities for the set cover constraints in a mixed-integer program, the constraints of the set cover type first have to be detected. In the detection, we check all the constraints of the problem. With an implemented plug-in the constraints are checked by reformulating the constraints using the complemented version of variables. After that, the violated odd-cycle inequalities for the set cover constraints are computed using Dijkstra's algorithm and the corresponding cutting planes are added to the problem. The impact of the so-called set cover separator is tested by solving test instances. From the computational results, we could conclude that the potential of the separation of the cuts is not directly visible in all the test instances. However, it is concluded that the separation of the cuts has the potential to decrease computation times in some optimization problems. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/88508 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page