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 Simplex 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 explicitly connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library with example visualizations, and our tool allows an instructor 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 literature on algorithm visualizations: 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.
翻译:解决线性程序之一的简单化算法 — — 科学与工程的计算系统十大最有影响力的20世纪最强的算法 — — 在许多算法课程中,这是一个重要话题。虽然简单化算法依赖直观几何想法,但算法的计算参与机制可以混淆几何理解。在本文中,我们提出Gilp,这是一个容易使用的简单化算法可视化工具,旨在明确将算法的机械步骤与其几何判读联系起来。我们提供了一个庞大的图书馆,提供了实例直观化,我们的工具允许教员迅速为学生制作定制的互动式 HTML 文档,以进行算法实验(不要求学生安装任何东西 ) 。这个工具也可以用于Jupyter笔记的交互式任务,并已被纳入即将出版的数据科学和决策互动教科书。在这个文件中,我们首先描述该工具如何适应关于算法可视化的现有文献:它的设计如何促进学生的公开参与和教师的采用,以及它如何大幅度扩展现有的可视化工具。 我们然后描述其直径的发展和使用直径性 HTM工具与直径直径直径直径的链接。