A Closer Look at the Held-Karp Relaxation
After talking with my GSoC mentors about what we all believe to be the most difficult part of the Asadpour algorithm, the Held-Karp relaxation, we came to several conclusions: The Asadpour paper recommends using the ellipsoid method so that their algorithm runs in polynomial time. We do not need a polynomial time, just an algorithm with reasonable execution time. An example of this would be the ellipsoid algorithm versus the simplex algorithm.
Pyplot vs Object Oriented Interface
Generating the data points To get acquainted with the basics of plotting with matplotlib, let’s try plotting how much distance an object under free-fall travels with respect to time and also, its velocity at each time step. If, you have ever studied physics, you can tell that is a classic case of Newton’s equations of motion, where $$ v = a \times t $$ $$ S = 0.5 \times a \times t^{2} $$
Emoji Mosaic Art
A while back, I came across this cool repository to create emoji-art from images. I wanted to use it to transform my mundane Facebook profile picture to something more snazzy. The only trouble? It was written in Rust. So instead of going through the process of installing Rust, I decided to take the easy route and spin up some code to do the same in Python using matplotlib. Because that’s what anyone sane would do, right?
NetworkX Function Stubs
Now that my porposal was accepted by NetworkX for the 2021 Google Summer of Code (GSoC), I can get more into the technical details of how I plan to implement the Asadpour algorithm within NetworkX. In this post I am going to outline my thought process for the control scheme of my implementation and create function stubs according to my GSoC proposal. Most of the work for this project will happen in netowrkx.
Held-Karp Seperation Oracle
Continuing the theme of my last post, we know that the Held-Karp relaxation in the Asadpour Asymmetric Traveling Salesman Problem cannot be practically written into the standard matrix form of a linear program. Thus, we need a different method to solve the relaxation, which is where the ellipsoid method comes into play. The ellipsoid method can be used to solve semi-infinite linear programs, which is what the Held-Karp relaxation is.
Draw all graphs of N nodes
The other day I was homeschooling my kids, and they asked me: “Daddy, can you draw us all possible non-isomorphic graphs of 3 nodes”? Or maybe I asked them that? Either way, we happily drew all possible graphs of 3 nodes, but already for 4 nodes it got hard, and for 5 nodes - plain impossible! So I thought: let me try to write a brute-force program to do it! I spent a few hours sketching some smart dynamic programming solution to generate these graphs, and went nowhere, as apparently the problem is quite hard.
Sidharth Bansal joined as GSoC'20 intern
When I, Sidharth Bansal, heard I got selected in Google Summer of Code(GSOC) 2020 with Matplotlib under Numfocus, I was jumping and dancing. In this post, I talk about my past experiences, how I got selected for GSOC with Matplotlib, and my project details. I am grateful to the community :) About me: I am currently pursuing a Bachelor’s in Technology in Software Engineering at Delhi Technological University, Delhi, India. I started my journey of open source with Public Lab, an open-source organization as a full-stack Ruby on Rails web developer.
Held-Karp Relaxation
In linear programming, we sometimes need to take what would be a integer program and ‘relax’ it, or unbound the values of the variables so that they are continuous. One particular application of this process is Held-Karp relaxation used the first part of the Asadpour algorithm for the Asymmetric Traveling Salesman Problem, where we find the lower bound of the approximation. Normally the relaxation is written as follows. \[ \begin{array}{c l l} \text{min} & \sum_{a} c(a)x_a \\\ \text{s.
Matplotlib Cyberpunk Style
1 - The Basis Let’s make up some numbers, put them in a Pandas dataframe and plot them: import pandas as pd import matplotlib.pyplot as plt df = pd.DataFrame({'A': [1, 3, 9, 5, 2, 1, 1], 'B': [4, 5, 5, 7, 9, 8, 6]}) df.plot(marker='o') plt.show() 2 - The Darkness Not bad, but somewhat ordinary. Let’s customize it by using Seaborn’s dark style, as well as changing background and font colors:
Elliott Sales de Andrade hired as Matplotlib Software Research Engineering Fellow
As has been discussed in detail in Nadia Eghbal’s Roads and Bridges, the CZI EOSS program announcement, and in the NumFocus sustainability program goals, much of the critical software that science and industry are built on is maintained by a primarily volunteer community. While this has worked, it is not sustainable in the long term for the health of many projects or their contributors. We are happy to announce that we have hired Elliott Sales de Andrade (QuLogic) as the Matplotlib Software Research Engineering Fellow supported by the Chan Zuckerberg Initiative Essential Open Source Software for Science effective March 1, 2020!