Bruce Cox

Chancellor Johnstone, Bruce Cox

Decision-making under uncertainty is hugely important for any decisions sensitive to perturbations in observed data. One method of incorporating uncertainty into making optimal decisions is through robust optimization, which minimizes the worst-case scenario over some uncertainty set. We connect conformal prediction regions to robust optimization, providing finite sample valid and conservative ellipsoidal uncertainty sets, aptly named conformal uncertainty sets. In pursuit of this connection we explicitly define Mahalanobis distance as a potential conformity score in full conformal prediction. We also compare the coverage and optimization performance of conformal uncertainty sets, specifically generated with Mahalanobis distance, to traditional ellipsoidal uncertainty sets on a collection of simulated robust optimization examples.

Petar D. Jackovich, Bruce A. Cox, Raymond R. Hill

This paper further defines the class of fragment constructive heuristics used to compute feasible solutions for the Traveling Salesman Problem into arc-greedy and node-greedy subclasses. Since these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel methodology, the Greedy Tracker, and compares it to both known methodologies. Computational results are generated across multiple symmetric and asymmetric instances. The results demonstrate the Greedy Tracker is the fastest method for preventing subtours for instances below 400 nodes. A distinction between fragment constructive heuristics and the subtour elimination methodology used to ensure the feasibility of resulting solutions enables the introduction of a new node-greedy fragment heuristic called Ordered Greedy.