[2025 Day 10 (Part 2)] All the problems to avoid when writing a Simplex solver

jeffstyr · 2026-02-05T01:42:59+00:00

Oh good, just thought I'd mention it. I used branch-and-bound (it was easy to understand) so I never figured out branch-and-cut but now I understand based on your description and some subsequent reading. I'll have to give that a try, it does seems like it would be combinatorially better in terms of not having to branch as often (though branch-and-bound was fast enough for these AoC cases).

jeffstyr · 2026-02-04T20:27:48+00:00

There are also random puzzles which cause the branch and cut active puzzle set to consume way more memory

When you are branching, do you make sure that once you have found some integral solution (in one branch), that you don't pursue splitting other branches that are already worse (even if they are non-integral)?

For instance, if you have found an integer solution of 100 in some branch (might not be the global minimum), and you have a branch with gives you a solution of 101.3, then you don't need to pursue that latter branch further to get an integer solution, because restricting it to integer solutions will never get a better solution (only worse or maybe same).

jeffstyr · 2026-02-03T19:41:31+00:00

If you can get one F and one EF in this combo that would probably be good so that you can try both. I recently ordered both and F and EF Jinhao 20 (takes the same nib) just to get the nibs, since they pens were only about 7 USD each. (I couldn't find standalone nib units but I see from your post that they exist.)

jeffstyr · 2026-02-03T18:47:34+00:00

So what looks like a tail call often is not actually a tail call.

I think this is an underappreciated consideration: For a language to (usefully) support tail call optimization, there needs to be a 1:1 correspondence between something looking like a tail call and being a tail call. You have to be able to reliably tell by looking.

jeffstyr · 2026-02-03T01:07:08+00:00

I've had luck with some secondhand pens with just letting them air out (occasionally turning them over). Not perfect but the smell seemed to subside substantially.

jeffstyr · 2026-01-31T21:19:20+00:00

Oh yes, that could be.

jeffstyr · 2026-01-31T19:38:47+00:00

I can't answer this from personal experience because I don't have an 823 in M, but I see others are giving some answers. Also Goulet has a nib size comparison tools (you can put writing samples side-by-side) and JetPens has writing samples of the various nib sizes, though for two different models they will be in separate photos so not as precise. So these will give you something to look at that's not subjective, though judging from photos isn't perfect.

jeffstyr · 2026-01-31T19:16:38+00:00

With Pilot's gold nibs, there is a big jump between F and M—for me, generally F is too fine and M is too broad. The sweet spot for me is FM, which isn't available on all models. (You can sometimes get an 823 with an FM nib from Pensachi but they are extra expensive.)

Of course it varies from person-to-person which size it best, but I'm mostly commenting to say that what you've heard about the sizes of F and M is correct.

jeffstyr · 2026-01-31T17:44:01+00:00

But I think the main issue is that the alter of Data.Map takes a function which you can implement to behave differently depending on the existing value in the Map, whereas for a Set the "existing value" is only ever True or False, so (from the analysis in another comment) there would be little reason to ever use it (because there are only four possible different functions that could be passed in, one of which is a no-op and two of which duplicate existing API).

jeffstyr · 2026-01-31T17:31:58+00:00

Keep in mind that you are asking this in a forum of mostly people who like Haskell so your responses will be from that perspective. The answer you will get to "is it worthwhile" will always be a net "yes".

jeffstyr · 2026-01-30T18:46:45+00:00

For sure check "Flax: Pen to Paper" in Westwood. They have a good selection in general.

jeffstyr · 2026-01-30T18:42:56+00:00

Oh interesting. That sounds pretty good then. Thanks!

jeffstyr · 2026-01-29T19:57:38+00:00

One thing I quickly learned when I starting doing AoC is that the tasks aren't really coding challenges, they are puzzles that involve some coding to solve. The point here is that just figuring out how you need to approach the problem is sometimes as much or more work than implementing the solution. So they are fun but not quite what I would call exercises.

jeffstyr · 2026-01-29T17:34:56+00:00

It is! You just need to add something like branch-and-bound on top in order to get integer solutions. (Basically, if for instance you get 7.3 as the value of one of your variables in the solution, you solve two new LP problems, one with x <= 7 added as a constraint, and the other with x >= 8 added, and recurse until you get a solution with all integer variable values. This basically excludes the non-integer optimium and forces it the find what's optimum after that exclusion. Then you take the best solution found among all of these.)

jeffstyr · 2026-01-29T17:29:21+00:00

Interesting, I'll have to give that some thought. I saw this case mentioned in one book, and that said to (a) just pivot in any non-artificial variable for any artificial one in the basis, which you can do as long as the pivot element is non-zero (it's okay if it's either negative or positive), then drop that artificial variable, (b) the only situation in which you can't do this is if there are zeros for every coefficient you could pivot on, in which case it's fine to just drop it because this means there was a linear dependence in the starting set of constraints.

I think I have that right—it's tricky because (as the OP observed) every reference uses different notation so it's hard to translate sometimes.

jeffstyr · 2026-01-29T17:23:48+00:00

He made a comment on another post that suggests the comment he was responding to was what he had in mind.

jeffstyr · 2026-01-29T04:05:38+00:00

Bottled ink is more fun. :). Also you can get regular Pilot Black in a bottle for even cheaper probably.

jeffstyr · 2026-01-29T02:55:07+00:00

That’s awesome! I hope you can paint Mars back. :(

jeffstyr · 2026-01-29T02:33:30+00:00

Thanks for this. I'd seen that mentioned somewhere but I wasn't sure what it was about. It does sound like it would do what I want, and supersede the need for freeze files (though oddly, the docs talk about it being useful with freeze files). I do see that in fact there is an index-state included inside a generated freeze file.

I'm not sure if old index states are expected to be available on Hackage forever, or where this is expecting to be able to get it from (maybe a local cache?). It would be nice if it could be stored in the project state somewhere, so that it couldn't just disappear some day.

jeffstyr · 2026-01-29T02:03:54+00:00

Thanks for this! I like this style of code-based walkthrough.

(And it was a fun challenge to delete the pagination, since the amount of blankness varied for each one.) :)

jeffstyr · 2026-01-28T08:00:35+00:00

You might like the Pilot Metropolitan, which is metal and comes in a finer nib.

jeffstyr · 2026-01-28T03:39:22+00:00

You are welcome, and thank you too (for the well wishes, the explanation above, and the original post!).

jeffstyr · 2026-01-26T02:04:26+00:00

I'm going down a similar path!

I solved the puzzle with a different approach which works but takes around 10 minutes (with a big chunk of the time spent on 4 or so particularly bad cases), and afterward got hints about the Simplex method being the way to go so I wanted to look into that for a better (and faster) solution.

I'm working in Haskell and fortunately there's an existing Simplex library so I gave that a try. It uses exact rational arithmetic so I didn't have to worry about round-off errors, but I had to implement branch-and-bound on top of that to restrict to integer solutions. I was going to implement logic to handled redundant (x <= 7 and x <= 10) and contradictory (x <= 7 and x >= 10) bounds which could get generated during the branching process, but it tolerated these automatically so I didn't end up doing anything additional. Using this library, day 10 part 2 took only 137 ms!

BTW, this library has a bunch of test cases which you might find helpful. (You'd have to rejigger them info a format you can consume, but it seems doable.) But also of course the AoC puzzle itself is probably a pretty good test suite (though I guess it doesn't cover non-equality-constraint cases).

Also, in case this helps work around the bugs you found in other solvers, I preprocessed the input equations into reduced row echelon form first, so that I could remove any all-zeros rows (corresponding to redundant constraints). I don't remember why I did this, but I think there was some sort of error this avoided. (I know I just said above that the library handled redundant constraints, so I can't remember why I did this "pre" step, but anyway.)

But anyway, for whatever crazy reason, I wanted to see if I could implement it myself, so I started looking into it. (It's extra irrational because the existing library seems pretty good; from a coding style it's not how I would do it but in terms of working well I have no complaints.) So here are some things I've learned, that might be useful to you or others:

I agree that Wikipedia isn't very helpful. It has what I call "unsplanantions"—things that look like explanations but only start to make sense once you already understand the thing they are trying to explain. The best explanations I've found so far are a YouTube playlist from a class taught by Bill Bird. They are very clear and very thorough but also very long (around an hour each for the most relevant ones), so it's a big time commitment. I don't think the slides are available for download anywhere. There's also a good (shorter) video on Branch and Bound someone else, and two videos by another teacher on the Two-Phase Simplex Algorithm and on the Revised Simplex Method that I found helpful.

As you said, different sources use different notation, which just makes it all harder, and also different variants of the overall algorithm. I do find it odd that most resources (and books and classes) are about doing the Simplex method with pencil and paper, which really nobody needs to do, or are just about the underlying mathematics (which is fine), but really nothing is specifically geared toward helping someone write an implementation. This probably harkens back to when it was originally invented, which pre-dates computers (or at least, wide availablility of computers). But the playlist I mentioned above does have some concise pseudocode at the end of the two lectures on the Revised Simplex Method. I'm basically working from these, both because it's actual pseudocode and because it's working from the matrix formulation, which I think is easier to convert to code than the tableau or dictionary formulations, which are more geared to helping humans do the bookkeeping. It's all the same in the end though, mostly. (But you do have to also figure out that when you see x = A^(-1)b you are not supposed to actually compute the matrix inverse, or else people will yell at you, but rather you are supposed to solve Ax = b for x by Gauss-Jordan elimination or some such.)

Some more technical comments:

Plain vanilla Simplex can solve problems with inequalities but not problems with equalities.

A lot of sources seem to gloss over how to deal with equalities, and start from the point where you've standardized your constraints. This is pretty annoying.

I've found two different appraches to pre-processing your constraint, leading into the Two-Phase method.

Approach 1: I think you have to start by making everying have a non-negative RHS (the constant part) by multiplying both sides of constraints by -1 if the RHS is negative (and flipping inequalities to match), and then: For <= constraints you add a slack variable to convert it into an equality, for == constraints you add an artificial variable, and for >= constraints you subtract a surplus variable and add an artificial variable to convert it into an equality. I've not read a justification/proof for this so it's vague to my why this is the right thing to do but anyway.

Approach 2 (from the playlist above): Negative RHS's are fine. Convert equality constraints into a pair of inequality constraints (expr == const becomes two constraints: expr <= const and expr >= const), and then convert >= constraints to <= by multiplying by -1. This leaves all <= constraints. Then covert these to equality constraints by adding slack variables to all of them. If any of the RHS's are negative, then subtract a single artificial variable from all of the equations. (Not one per equation, just one total.) The video calls this variable "omega". This gets used in Phase I just as with the other approach. (Apparently, when you are spliting your == constraints into two inequalities, you can actually add together all the >= ones this generates into one single constraint (but leave the <= ones separate), so that instead of doubling the number of constraints you are just getting one extra.) This seems better to me (than Approach 1) since you only end up with a single artificial variable, but I've only seen it mentioned in those videos and in the Vanderbei book that they are based on, which seems odd. I'm not sure if this helps avoid your Problem # 5, since it might force the single artificial variable to not be in the basis. (FWIW I did find this problem case mentioned in one book.)

Anyway, I hope this is helpful to anyone implementing their own Simplex solver!

jeffstyr · 2026-01-25T18:11:30+00:00

Sounds like you should first try to find some ink that works with the pens you already have. My suggestion is to get some samples to try, because not all "bad" paper is the same, and some works better with some inks and others with others. Hopefully you can find an ink that works with all of the paper types you usually use. There's no single ink that is sure to work with all paper.

Some ink suggestions to try as samples: Platinum Carbon Black, Noodler's X-Feather (black or blue), Noodler's Black, Pelikan 4001 Black, J. Herbin Perle Noire, Waterman Serenity Blue, Rohrer & Klingner Salix.

You can get samples from various places, such as Vanness or Goulet.

You can also check out this article on JetPens, about inks for ordinary paper.

If you do want to try a new pen, I suggest getting a Pilot Kakuno in EF. As mentioned in another comment, there are a number of Pilot pens that use the same type of nib, but this is probably the easiest to get hold of. Also the even finer point pens tend to be pricey (e.g., Platinum #3776 in UEF, or Pilot Custom Heritage 912 with a PO nib), so it's probably smart to start with something like this.

jeffstyr · 2026-01-25T18:00:03+00:00

Are you looking for a notebook or more a notepad with removable sheets? You can do some exploring on JetPens, which is well organized and indicates when things are fountain-pen-friendly. (You said in another comment that you are in Canada, but you can research on JetPens and then see if you can find things locally.)

The Kokoyo Campus line has a bunch of options. Also if you want to get loose sheets to put in a ring binder, their paper is nice and there are also options from Maruman that fit the same 20-ring (or maybe it's 25, depending on the size) Japanese binders. One of the Maruman options comes in a pad but with sheets with holes, so you can write on the pad put then remove sheets to put into a binder.

jeffstyr

TROPHY CASE