New modeling and solution approaches for combinatorial optimization, with application to exam timetabling and batch scheduling in chemical manufacturing.

摘要

This thesis considers modeling schemes, problem decomposition and modular methodologies in the integer programming area. We design novel approaches and apply them together with mathematical programming techniques to two large hard combinatorial optimization problems.; In the first place, we study a real-world university exam timetabling problem at USMA (West Point). The timetabling problem, i.e., to minimize the number of makeup exams, was formulated as an MILP, but it was unsolvable due to the extremely large number of binary variables. We propose a new variable redefinition and bilinearization strategy, which introduces new indices and a group of new variables that replace part of the original ones. With the new variables and constraints, the original problem can be decomposed into sub-problems which can be solved iteratively until no further solution improvement. Computational results for the USMA application demonstrate the effectiveness of the novel bilinearization approach for the scheduling problem.; Secondly, we consider a capacitated batch sizing and scheduling problem in process industries. Discrete-time and continuous-time MILP formulations have been built and utilized for minimizing makespan. Yet, since good feasible solutions and tight lower-bounds are very difficult to get when problem size gets large, we explore a multi-step modular approach which hybridizes discrete-time and continuous-time models in a specific order, and the results of one model are fed into the next in the chain. We also propose to introduce, as a simplifying tool for any problem, related problems with simpler data structures, whose solution is much easier, and whose solution, upon inspection, can be exploited and in some way used as input information for solving the harder problem. This tool turns out to be very helpful to decompose the original problem, and becomes the link for different modules on consecutive stages. Additionally, we propose an easy LP model which provides the basis for a strong lower-bound on the makespan. Good solutions have been obtained at relatively cheap computational cost for the Westenberger and Kallrath Benchmark problems, as well as for the newer problems with or without cleaning requirement by Blöer and Güther.