Print Email Facebook Twitter Decision diagrams for decomposed mixed integer linear programs Title Decision diagrams for decomposed mixed integer linear programs Author van der Linden, Koos (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Software Technology) Contributor de Weerdt, M.M. (mentor) Spaan, M.T.J. (graduation committee) van Iersel, L.J.J. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science Date 2017-08-30 Abstract A recent development in the field of discrete optimization is the combined use of (binary) decision diagrams (DD) and branch and bound for optimization. This method has been shown to outperform integer linear programming on several classic problems. The performance of DDs in integer optimization raises the question if this method can be extended to solve mixed integer problems (MIP), because of the prevalence of MIP modelling. This thesis is an effort to answer that question. Currently DD-based optimization does not allow for continuous variables. We propose a method that uses Benders Decomposition to divide MIP problems into a discrete master problem and a continuous subproblem. DD-based optimization is used to solve the master problem. The subproblem can be solved by linear programming. The results presented in this thesis show that our method can be used for MIP problems whose integer variables play a dominant role, and are hard to solve by MIP solvers. An advantage of our method is that it provides feasible solutions as early as the first iteration. Subject Decision diagramsMixed integer programmingBenders decompositionAlgorithmics To reference this document use: http://resolver.tudelft.nl/uuid:57e43a69-e380-4917-9598-097710379b9f Part of collection Student theses Document type master thesis Rights © 2017 Koos van der Linden Files PDF jgmvanderlinden_final.pdf 787.12 KB Close viewer /islandora/object/uuid:57e43a69-e380-4917-9598-097710379b9f/datastream/OBJ/view