Preprocessing and postprocessing in linear optimization

ii This thesis gives an overall survey of preprocessing and postprocessing techniques in linear optimization (LO) and its implementations in the software package McMaster Interior Point Method (McIPM). We ¯rst review the basic concepts and theorems in LO. Then we present all the techniques used in preprocessing and the corresponding operations in postprocessing. Further, we discuss the implementation issues in our software development. Finally we test a series of problems from the Netlib test set and compare our results with state of the art software, such as LIPSOL and CPLEX. iii iv Acknowledgements I gratefully give my thanks to my supervisor, Dr. Tam¶as Terlaky, an expert in optimization area. It is him who lead me to the wonderful optimization world. I bene¯t a lot from his invaluable instruction. Without his guidance, discussion and encouragement, I would not ¯nish this thesis. I also thank the members of the defense committee: Dr. Antoine Deza and Dr. Jiming Peng for their careful review and insightful comments on my work. I appreciate all the kind help from the members of the advanced optimization laboratory, especially thank Xiaohang Zhu who provided great help in the process of my thesis writing and implementation. Finally my special thanks goes to my husband Changhai Jia, my father Xiaorong Huang and my mother Xiuyun Zhao, for their endless love, encouragement and sup-port. v v