The Simplex algorithm for solving linear programs---one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century---is an important topic in many algorithms courses. While the algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library of example visualizations, and our tool allows instructors to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing algorithm visualization literature: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions.

We consider the integrality gap of the subtour linear program (LP) relaxation of the traveling salesman problem (TSP) restricted to circulant instances. De Klerk and Dobre [ Discrete Appl. Math., 159 (2011), pp. 1815--1826] conjectured that the value of the optimal solution to the subtour LP in these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma [ The Symmetric Circulant Traveling Salesman Problem, Research Memorandum 429, Institute of Economic Research, University of Groningen, 1991]. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few nontrivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas [ Math. Programming, 60 (1993), pp. 145--166] in a distinctly nonmetric set of instances.