Embeddings for Disjunctive Programs with Applications to Political Districting and Rectangle Packing

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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial and Systems Engineering

Department dc:contributor.department

Industrial and Systems Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2024

Author dc:creator

• Fravel, William James

Chair dc:contributor.committeechair

• Hildebrand, Robert

Committee members dc:contributor.committeemember

• Xie, Weijun
• Bansal, Manish
• Sarin, Subhash C.

• Disjunctive Program
• Political Districting
• Rectangle Packing
• Piecewise-Linear Approximation
• Compact Formulation
• Ideal Formulation
• Encoding
• Embedding

Statement dc:rights

• Creative Commons Attribution 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:41667

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/121582