Binary Optimization: Applications To Regional Planning
This dissertation is based on three related essays applying binary optimization, with a focus on discovering the best selection of nodes, parcels, and villages that are subject to a budget constraint. The applications are special cases of a mathematical problem called the knapsack problem. The first essay discusses the clustered knapsack problem with an underlying graph structure. Three different models are formulated in addition to the basic knapsack problem, and instance family groups of cluster types are constructed. A series of experiments solving the instances to find the optimal solutions are performed. The second essay focuses on the study of rehabilitation and reconstruction of housing in Banda Aceh, Indonesia, which was destroyed by the tsunami and earthquake in 2004. Problems arose due to lack of planning, although millions of dollars were set aside for the reconstruction effort. New houses in the villages were badly constructed with minimal or no infrastructure support where they were located far from the closest rebuilt hospital, schools and other infrastructures. As such, one way to model this problem is to focus on individual villages to rebuild, building up their infrastructure so that everyone from that village and nearby villages can have access to the village community. The clustered knapsack models are applied to the City of Banda Aceh. Finally, the third essay evaluates watershed protection in the Skaneateles Lake, which is the primary water supply for the city of Syracuse, NY. The high quality of the water makes it possible to utilize the lake's water without filtration. The City of Syracuse was granted a filtration waiver by signing a Memorandum of Agreement, subject to several very strict conditions which include continuous monitoring of key water quality parameters, a back-up disinfection system, and a rigorous watershed protection program to reduce pathogen, chemical, nutrient and sediment loading into the lake. Part of the watershed management program involves the establishment of a riparian buffer at important areas within the watershed. We approach the riparian buffer problem using clustered knapsack models which will be applied to a selection of parcels in the Town of Skaneateles.
Binary Optimization; knapsack problem; Aceh; tsunami; Clustered Knapsack; Skaneateles Lake; riparian buffer
Conrad, Jon M
Azis, Iwan Jaya; Gomes, Carla P
Ph.D. of Regional Science
Doctor of Philosophy
dissertation or thesis