Combining Node and Variable Selection Heuristics for Faster MIP Solutions
Public Deposited- Resource Type
- Creator
- Abstract
The Node selection (NS) and variable and direction selection (VDS) heuristics significantly affect the time to find the MIP integer-optimal solution when using branch and bound method. In this thesis, various variable and direction selection methods are tested coupled with the node selection heuristic by Wojtaszek and Chinneck[2010]. Rules are developed to select VDS / NS configuration depending on MIP characteristics. Empirical results show a new VDS / NS configuration outperforms the state of the art as well as the VDS / NS configuration found by Wojtaszek and Chinneck. The hypothesis that a feasibility - oriented VDS coupled with a good NS heuristic will provide the fastest MIP solution time is disproved. A new hybrid VDS/NS selection heuristic is developed and shown to provide better results than any individual VDS/NS configuration or the state of the art default configuration.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2020 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2020
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
lu-combiningnodeandvariableselectionheuristics.pdf | 2023-05-05 | Public | Download |