26 Feb 2024
An old math problem I had not seen since my university days resurfaced the other
day, the Maximum Flow problem. It came up in the context of analyzing
some industrial process. For illustration purposes, let’s say we are producing
sausages, following these steps: we grind some meat, add some seasoning, then
stuff and tie the sausage casings, and split them into delicious sausage links.
We could represent this process as a graph, like so:
``` mermaid
graph TD;
grind_meat --> season_meat;
season_meat --> stuff_casing;
stuff_casing --> cut_links;
Now the question is, how many sausages per minute could we produce?
Assuming each operation is performed by a separate person, this is not very
complicated. We are going to be as slow as the slowest link. So if for instance
we could
- grind meat for 20 sausages / minute,
- season meat for 15 sausages per minute,
- stuff 5 sausages per minute, and
- cut 20 sausages per minute,
we would end up running at 5 sausages / minute at best, the bottleneck being
stuffing.
Now we might be able to get a better throughput with some parallelization. For
instance, we could organize production like so:
``` mermaid
graph TD;
grind_meat --> season_meat_1;
grind_meat --> season_meat_2;
season_meat_1 --> stuff_casing1;
season_meat_1 --> stuff_casing2;
season_meat_2 --> stuff_casing2;
season_meat_2 --> stuff_casing3;
stuff_casing1 --> cut_links_1;
stuff_casing2 --> cut_links_1;
stuff_casing3 --> cut_links_1;
This is still not overly complicated, but it is beginning to be hairy, and you
can imagine how with a few more processes added, the question “how much work
can I process through this network” will soon become impractical to handle by
hand.
This is essentially what the Maximum Flow problem is about. Given a directed
graph, with capacity limitations, how much throughput (flow) can we achieve?
In the rest of this post, I’ll go through one way you could answer that
question, using Linear Programming.
More...
23 Nov 2023
In my previous post, I went over the recent changes I made to my
F# Nelder-Mead solver, Quipu. In this post, I want to explore how I could
go about handling constraints in Quipu.
First, what do I mean by constraints? In its basic form, the solver takes a
function, and attempts to find the set of inputs that minimizes that function.
Lifting the example from the previous post, you may want to know what values of
$(x,y)$ produce the smallest value for $f(x,y)=(x-10)^2+(y+5)^2$. The solution
happens to be $(10,-5)$, and Quipu solves that without issues:
#r "nuget: Quipu, 0.2.0"
open Quipu.NelderMead
let f (x, y) = (x - 10.0) ** 2.0 + (y + 5.0) ** 2.0
NelderMead.minimize f
|> NelderMead.solve
val it: Solution = Optimal (2.467079917e-07, [|9.999611886; -4.999690039|])
However, in many situations, not every value will do. There might be
restrictions on what values are valid, such as “x must be positive”, or “y must
be less than 2”. These are known as constraints, and typically result in
an inequality constraint, in our case something like $g(x,y) \leq 0$. How could
we go about handling such constraints in our solver?
More...
11 Nov 2023
Back in April ‘23, I needed a simple solver for function minimization, and
published a basic F# Nelder-Mead solver implementation on NuGet. I
won’t go over the algorithm itself, if you are curious I wrote a post breaking
down how the Nelder-Mead algorithm works a while back.
In a nutshell, the algorithm takes a function, and finds the set of inputs that
produces the smallest output for that function. The algorithm is not foolproof,
but it is very useful, and has the benefit of being fairly simple.
After dog-fooding my library for a bit, I found some rough spots, and decided
it was time to make improvements. As a result, the API has changed a bit -
hopefully for the better! In this post, I’ll go over some of these changes.
Basic usage
Imagine that you are interested in the following function:
$ f(x,y)=(x-10)^2+(y+5)^2 $
Specifically, you would want to know what values of $(x,y)$ produce the
smallest value for $f$.
This is how you would go about it with Quipu in an F# script:
#r "nuget: Quipu, 0.2.0"
open Quipu.NelderMead
let f (x, y) = (x - 10.0) ** 2.0 + (y + 5.0) ** 2.0
NelderMead.minimize f
|> NelderMead.solve
This produces the following output:
val it: Solution = Optimal (2.467079917e-07, [|9.999611886; -4.999690039|])
The solver has found an Optimal solution, for $x=9.999,y=-4.999$, which yields
$f(x,y)=2.467 \times 10^{-7}$, very close to the correct answer, $f(10,-5)=0$.
More...
29 Oct 2023
In September, I had the great pleasure of attending the
Data Science in F# conference in Berlin. I gave a talk and a workshop on
Linear Programming, and figured I would make the corresponding material
available, in case anybody is interested:
More...
28 Jun 2023
This is a follow-up to my recent post trying to implement the classic
Conway Game of Life in an MVU style with Avalonia.FuncUI. While I managed
to get a version going pretty easily, the performance was not great. The
visualization ran OK until around 100 x 100 cells, but started to degrade
severely beyond that.
After a bit of work, I am pleased to present an updated version, which runs
through a 200 x 200 cells visualization pretty smoothly:
As a side note, I wanted to point out that the size change is significative.
Increasing the grid size from 100 to 200 means that for every frame, the
number of elements we need to refresh grows from 10,000 to 40,000.
In this post, I will go over what changed between the two versions.
You can find the full code here on GitHub
More...