This dissertations represents a composite of three papers which have been submitted for publication:
The first chapter deals with a non-convex knapsack which is inspired by a simplified political districting problem. We present and derive a constant time solution to the problem via a reduced-dimensional reformulation, the Karash-Kuhn-Tucker optimality conditions, and gradient descent.
The second chapter covers a more complete form of the political districting problem. We attempt to overcome the non-convex objective function and combinatorially massive solution space through a variety of linearization techniques and cutting planes. Our focus on dual bounds is novel in the space.
The final chapter develops a framework for identifying ideal mixed binary linear programs and applies it to several rectangle packing formulations. These include both existing and novel formulations for the underlying disjunctive program. Additionally, we investigate the poor performance of branch-and-cut on the example problems. / Doctor of Philosophy / This dissertation is made up of three papers dealing with two problems: Political Districting (the process of partitioning land into voting districts for United States Congressional Representatives) and Rectangle Packing (the process of fitting rectangular objects onto a floorspace in some efficient or optimal manner). Both problems receive thorough descriptions in their respective chapters. Rather than generating real, usable solutions, our focus for the districting problem is on producing upper bounds against which the myriad existing solutions can be compared. This is useful in evaluating whether or not said solutions fairly represent the voting populous of a state.
The first chapter deals with the difficulty of political districting by reducing the space of solutions; rather than assigning discrete tracts of land to districts, we assign individual voters. We present two fast methods for solving this reduced problem and achieving viable upper bounds. The second chapter covers a more complete form of the political districting problem as we attempt to overcome the difficulty associated with the objective function rather than the solution space. We propose a variety of techniques for efficiently approximating said function within exiting optimization frameworks and perform a number of experiments to demonstrate their effectiveness.
The final chapter shifts focus to the rectangle packing problem described above. This problem is most naturally given as a Disjunctive Program (an optimization problem which requires `or' statements to properly describe). The approximation schemes given in Chapter 2 can also be accurately described as disjunctive programs, so some of the same techniques apply. There exist several good methods for formulating this problem, but we seek to establish a theoretical aspect of these methods. We say that a model is Ideal if any integer requirements can be safely ignored without destroying the solution; Chapter 3 develops a framework for identifying ideal formulations and uses it to prove and correct the idealness of existing methods.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/121582 |
| Date | 08 November 2024 |
| Creators | Fravel III, William James |
| Contributors | Industrial and Systems Engineering, Hildebrand, Robert, Xie, Weijun, Bansal, Manish, Sarin, Subhash C. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Dissertation |
| Format | ETD, application/pdf |
| Rights | Creative Commons Attribution 4.0 International, http://creativecommons.org/licenses/by/4.0/ |
Page generated in 0.0109 seconds