University of Twente Student Theses
Recognition and Exploitation of Single-Machine Scheduling Subproblems in Mixed Integer Programs
Wijfjes, R.L.H. (2022) Recognition and Exploitation of Single-Machine Scheduling Subproblems in Mixed Integer Programs.
PDF
1MB |
Abstract: | To speed up the branch-and-bound algorithm that is used to solve mixed integer programs, modern solvers exploit general and problem specific cutting planes. As it is unknown whether the application of the class of scheduling cutting planes is beneficial, we investigate the employment of the subclass of single machine scheduling cutting planes that are valid for the formulation using big-M constraints with natural date variables. To be able to identify single machine scheduling subproblems within mixed integer programs, a new exponential time recognition algorithm, performing well in practice, is developed and presented here. Experiments to investigate the exploitation of single machine scheduling subproblems indicate that in a small number of cases the use of scheduling cutting planes indeed reduce the solving time and in a few more cases there is potential to decrease the solving time by integrating the cutting planes into the branch-and-cut algorithm. |
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/89500 |
Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Repository Staff Only: item control page