This week the goal was to focus on trying to implement a method for resolving a tabletop rearrangement from "High-Quality Tabletop Rearrangement with Overhand Grasps." This work began with me reading through more of the paper in an attempt to understand what was happening, but was relatively quickly sidetracked by my quest to understand and implement Johnson's algorithm for finding all the cycles in the graph (which I thought was necessary for the original algorithm). This involved quite a bit of both reading through the paper published about the algorithm, as well as more struggles with Python.

At the start of the week, I finished my code. However, upon finally implementing Johnson's accursed cycle finding algorithm, I found that my new task was to pursue an understanding of the minimum simultaneous problem through the lens of integer programming. However, the first step of this was actually understanding how to consider things through such a perspective. Of course I realized this not through logic, but rather simply plunging myself into the first paper recommended by Professor Yu. There might be people who can just hit the ground running. I am not one of them.

Thus, armed with a friend's recommendations, I set out to learn more about integer programming. A couple of days, a few lecture notes, and a video lecture later, I felt comfortable enough with the concept to attempt to return to "The orienteering problem: A survey," and I am happy to report it no longer felt as though I was reading hieroglyphics. Instead I was able to properly investigate the approach it took for removing cycles. This involved, among other things, looking into the paper it cited, "Integer programming formulations and travelling salesman problems," to understand what inspired the method.

I began this week continuing my investigation into adapting the approach of "The orienteering problem: A survey." Uninspired by what I was currently looking at, I began to look for other sources. However, I could not see how to adapt the approach for paths to an entire subgraph. Thus, I began to seek alternative routes. Among these looking at another LP solution to TSP, though frankly that one failed to convince me that it worked. Eventually I decided to pursue my own approach inspired by the fact that a graph without cycles should have a topological ordering.

With another meeting came another task. I came to the realization after this meeting that I could use Gurobi's example sudoku.py as an example of how to assign a group of variables to essentially hold a permutation of 1 to n. Alas, integer programming was no longer the name of the game. It was just programming. Luckily, Johnson's cycle finding algorithm was finally able to make up for some of the misery it's paper caused, as I utilized its ability to find all the cycles, and thus all the items in cycles. Regardless, after spending a couple of days on my pseudocode, I was then able to put it together in Python and get it working.

This week was primarily about presentations and papers. After modifying my code slightly, I began work on my presentation. This included many more hours of manipulating pictures of graphs than was perhaps reasonable, but I'd like to believe that it paid off in aesthetics. After that, the focus was on the paper. While I thought that since the algorithm was programmed that would be the simplest part to write up, I came to the realization that abridging code into pseudocode is actually far more annoying than the other way around. Anyhow, with everything done and submitted, I'd like to give thanks to DIMACS, in particular Lazaros Gallos and Parker Hund, for organizing this program. As well as NSF HDR TRIPODS award CCF-1934924 for funding this project.