Loading [MathJax]/jax/output/CommonHTML/jax.js

Wednesday, August 28, 2024

Circle Packing and HTML reporting

Little example. Here, we try to pack n circles with a given radius ri into a larger disc with an unknown radius R. The goal is to minimize R. The underlying model is simple: 

Packing of Circles
minRc(pi,cpj,c)2(ri+rj)2i<jcp2i,c(Rri)2iR0c{x,y}

Monday, August 12, 2024

Revised Simplex LP Solver written in GAMS

I am teaching some GAMS classes, and a question arose: "How does the Simplex method work?" It's not easy to answer in a few sentences, but I want to touch upon the concept of a basis anyway. Once you have a good intuition of what a basis is, a simple Simplex method is not so far-fetched. I find the tableau presentation somewhat confusing and far removed from what actual Simplex solvers do. I strongly prefer the Revised Simplex Method in matrix notation. 

Minor rant: I just don't understand the appeal of the tableau method. It looks to me like an invention for torturing undergrad students. Most of all, it is not very structure-revealing; it does not help you understand the underlying concepts. But about 100% of the LP textbooks insist we should learn that first.

As a gimmick, I implemented a simplified version in the GAMS language. This reminds me that someone spent the effort writing a Basic interpreter in TeX [1]. This is probably just as useful.