University of Twente Student Theses

Login

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.

[img] 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