Building a Mathematical Optimiser (in Zig): Introduction

Why a Mathematical Optimiser?

At my current workplace, we use a commercial solver to solve complex mathematical optimizations. I had the itch to understand how this actually works under the hood. I found the resources online on how to actually code something like this are lacking. They are either too textbooky or too abstract and missing key steps.

Why Zig?

I've been half learning Zig for the better part of a year now. However I haven't actually built anything substantial with it. So this will also be a learning curve for me.

Zig appeals to me due to its very explicit nature. I want to have full control over the code and memory management, which leads into the next part of this series.

Code Performance

Again over the past year I have been doing Casey Muratori's course on Performance-Aware Programming. Whilst implementing an optimizer, we will be attempting to implement my learnings from that course, and will have dedicated blogs on analyzing the assembly code generated by the compiler.

This project allows me to scratch my itch of maths, Zig and code optimisation.

What's Next?

In this blog series, I'll be covering the following topics:

• Simplex Method - The foundational algorithm for linear programming
• Dual Simplex - An alternative approach to solving linear programs
• Branch and Bound - Techniques for solving integer programming problems
• Testing and Verification - Validating our implementation against known problems and solutions
• Cutting Plane - Methods to strengthen linear programming relaxations
• Optimization Passes - Diving into proper performance analysis and assembly inspection
• Python Bindings - Making the optimizer accessible from Python
• .mps Parser - Supporting the standard mathematical programming format