Fravel III, William James2024-11-092024-11-092024-11-08vt_gsexam:41667https://hdl.handle.net/10919/121582This 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.ETDenCreative Commons Attribution 4.0 InternationalDisjunctive ProgramPolitical DistrictingRectangle PackingPiecewise-Linear ApproximationCompact FormulationIdeal FormulationEncodingEmbeddingDissertation