Constrained Knapsack with Python-MIP

This will be another quick post that’s a follow-up to this previous one. That problem works in a linear program by luck, since the ‘capacity’ of the knapsack (the number of jobs that need to be done) is an integer. For recent versions of SciPy’s linear solver, you have to use revised simplex, and it’s not very straightforward.

I recently learned about Python-MIP, and it is easier to write the problem in that framework, and it’s made for integer linear problems. I’ll show you how to write the problem in that below!

Cellular Islands

I’ve started playing with some simple generative art, and you can see two examples at this thread and this other thread on the Python Sub-Reddit. It’s fun to do, and it can make some cool-looking images. I’m still very much in the ‘replicate examples’ stage of learning as I gather knowledge about different kinds of tools and methods that can be used to create images.

Today I’d like to share some things I learned how to do in Python that might help you out as well. We’re going to use Cellular Automata to make islands and continents.

Using Google OR-Tools for Social Golfers

The ‘Social Golfers’ problem asks how to group golfers in a tournament such that no golfer plays in a group with someone they’ve played with before. The number of golfers, group size, and number of rounds can all be varied.

I learned about this problem from an r/Python thread, particularly the user named ‘mzl’. Inspired by Raymond Hettinger’s talk about problem solving in python, I thought I’d work through how to use constraint programming in Google’s OR-Tools to solve this problem.

Loot Boxes, Sparse Markov, and Decimal Networks

Once again we are back with Markov Chains inspired by a reddit thread! We’ll answer the question: “When’s the best time to switch loot box opening strategies?”

In this post we’ll go over:

1. Setting up a large, sparse Markov Chain
2. The perils of analyzing it with python’s built-in floating point capabilities
3. Comparing simulation to Markov Chains
4. Using NetworkX and decimal.Decimal to run a Markov Chain with very very very small probabilities

Let’s get to it!

A Quick Knapsack Example

This is a quick example of how to start working on a knapsack problem, inspired by a reddit thread.

Estimating the Cost of Education

I saw a post circulating Facebook that sardonically addressed some ‘real’ comments from Facebook about teacher salaries. That post, “Are you sick of highly-paid teachers?“, comes to the conclusion:

$1.42 per hour per student — a very inexpensive baby-sitter and they even EDUCATE your kids!

This doesn’t seem realistic at first glance, nor does it account for all the other factors that go into employing a person. Let’s be a bit more rigorous and understand the problem from the numbers side.

Falling Through the Earth (and Mars)

Recently, on Reddit (of course), someone posted a video talking about how long it would take to fall straight through the center of the earth to the other side. One of the nice parts of the video is that it shows you what the time would be when we account for the actual, non-uniform density of the earth. The video just showed an Excel sheet, though.

I recommend you watch the linked video so you have a good visual of the problem. Once you’ve done that, come on back! In this post I’m going to show you how to solve the problem using Python and a numerical integrator from SciPy.

Powerball Nears Best EV (Updated)

This is a quick post that is the exact same as the Mega Millions post I did. I break down the Powerball odds, use some sales data, and look at the EV over various jackpots.

The quick takeaway, as the Powerball is up to $450 million for Wednesday, is that either this drawing (or the next if no one wins) is as near to the possible expected value for this lottery. The other takeaway? Don’t buy lottery tickets!

UPDATE: Going back I found an error in my code. I’ll update it at some point, but for now, take it with a grain of salt (except the historical data part, that part was fine).

Mega Millions, Multiple Winners, and Expectations

The Mega Millions lottery is a popular number-picking lottery game in the US. It exists in 45 states (including D.C.), and is played by millions of people every week. Lotteries are well known for having negative expected values, meaning that players lose (on average) more than they win. This should be expected, given that lotteries (and gambling in general) are profit-seeking enterprises.

The potentially large jackpots of Mega Millions (the jackpot is pari-mutuel) can push the game into a region of positive EV, though. This is counter-balanced by the fact that duplicate tickets will result in splitting the winnings equally among the winners, driving down the available EV. This post explores what kind of impact that has on the game.

Non-Uniform Coupon Collector’s Problem

The Coupon Collector’s Problem is a neat little problem in probability, and I first heard about it recently on the statistics subreddit. You, like me, might be familiar with it if you’ve ever tried to solve the expected number of boxes of cereal to buy to get all the toys. Not that I have that problem right now, but it shows up on probability quizzes and the like.

The problem’s solution hinges on two things. One, there is replacement (sampling from a seemingly infinite population of items that are in some proportion). Two, all items are equally likely. What happens when they aren’t equally likely? We turn back to Absorbing Markov Chains (AMC), because apparently that has to be 50% of what I talk about on here!