UC Davis

This dissertation discusses several problems motivated by the simplex method, one of the most influential algorithms in optimization.

First, every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. We introduce the notions of $f$-arborescence and $f$-monotone path on$P$, as well as a natural graph structure on the vertex set of $f$-monotone paths on the resulting directed graphs. These combinatorial objects are proxies for pivot rules and simplex method pivot steps. We bound the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets. We also sample the distribution of lengths of monotone paths over different classes of random polytopes.

Second, inspired by the simplex and the criss-cross methods, we present an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements. For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights an old conjecture that states a linear bound for the diameter is possible. On the positive side, we show the conjecture is true for oriented matroids of low rank and low corank, and, verified with computers, for all oriented matroids with up to nine elements. On the negative side, our computer search showed two natural strengthenings of the main conjecture are false.

Finally, we discuss a data-driven, empirically-based framework to make algorithmic decisions or recommendations without expert knowledge. We improve the performance of the simplex method by selecting different pivot rules for different linear programs. We train machine learning methods to select the optimal pivot rule for given data without expert opinion. We use two types of techniques, neural networks and boosted decision trees. Our selection framework recommends various pivot rules that improve overall total performance over just using a default fixed pivot rule. Here our recommendation system is best when using gradient boosted trees. Our data analysis also shows that the number of iterations by steepest-edge is no more than four percent from the optimal selection.

The thesis is structured as follows: In Chapter 1 we introduce the readers to the basic notions in Sections 1.1 and 1.2, and summarize our main results in Sections 1.3, 1.4 and 1.5. Section 2.1 through Section 2.4 prove our stated bounds on number of arborescences, monotone paths, and the diameter of flip graphs; Section 2.5 demonstrates the distributions related to length of monotone paths, and we conclude Chapter 2 with some open problems in Section 2.6. Chapter 3 proves the diameter conjecture in low rank and corank oriented matroids and shows the constructions of counterexamples. In Chapter 4 we show how we generate the training data and the comparison between different machine learning models to select pivot rules. In Appendix, we present the pseudocode for converting oriented matroids in different representations and for computing different features on directed polytope graphs.