Operations Research, Systems Engineering and Industrial Engineering Commons^™

Exploiting Symmetry In Linear And Integer Linear Programming, Ethan Jedidiah Deakins

Doctoral Dissertations

This thesis explores two algorithmic approaches for exploiting symmetries in linear and integer linear programs. The first is orbital crossover, a novel method of crossover designed to exploit symmetry in linear programs. Symmetry has long been considered a curse in combinatorial optimization problems, but significant progress has been made. Up until recently, symmetry exploitation in linear programs was not worth the upfront cost of symmetry detection. However, recent results involving a generalization of symmetries, equitable partitions, has made the upfront cost much more manageable.

The motivation for orbital crossover is that many highly symmetric integer linear programs exist, and …

An Optimization Framework For Integrating Variable Capacity And Pavement Thickness Requirements In Highway Cost Allocation, Saurav Kumar Dubey

Doctoral Dissertations

The objective of Highway Cost Allocation (HCA) is to distribute or allocate in a fair and rational manner the cost of a transportation facility (either a highway or bridge) among all vehicle classes using it. The purpose of this dissertation is to study and enhance a model, known as the least-core model, to include both pavement thickness and traffic capacity requirements for all coalitions formed with a given group of vehicle classes. Considering vehicle classes as players and groups of vehicle classes as coalitions, it is possible to quantify the thickness and width of pavement needed to accommodate the vehicle …