When the Product Owner enters the office, I feel goosebumps and my pulse rate accelerates. You can tell by her eyes that she's about to ask for a brand cool new feature for our clients.
Yes, Bring it on! Always love new exciting challenges. In just a hundred of a second few parallel threads spawn in my body. My left hand Ctrl+L my laptop (protection against relentless trolls), my right hand grabs colour markers, my feet jump towards the whiteboard and wait for PO's input.
Jokes aside, software developers usually understand the problem at hand and figure out the solution head-on. If the problem is complex, we may not be able to implement the best solution and settle for a partial, not-that-bad solution.
Mathematical Programming is a powerful methodology that software developers can add on their toolbelt to solve complex problems. The main highlight is that you don't have to come up with a solution, the computer will find one for you. Not just one, but the best solution.
That looks amazing, isn't it?
(With love to Product Owners. You do an amazing job.)
Here begins our journey
In this series of articles you will learn Mathematical Programming. Eventually you will gain enough knowlege to reason about problem-solving, understand code and contribute fearlessly.
Let's start our journey with our first baby step by introducing the framework. This framework is just a guide to organize and communicate all the information that is needed to solve any problem in a clear, concise and standard manner.
Without further ado, please welcome The Framework!
The Framework with an example
Abby is the owner of a very successful small-sized hardware store in a farily big city. As the company grows, last-mile deliveries to end customers are becoming less efficient. Abby thinks the number of orders that the delivery van serve daily is far from ideal, mainly due to inefficient route planning.
If her team doesn't figure out a solution by the end of the year, they won't be able to deliver all packets on big events such as Christmas.
Write a document
Let's organize the previous statement into a proper document. The document gathers all the information that is needed to communicate the previous statement in a clear, concise and organized way. It's just a questionnaire with five simple questions.
What is the goal?
What data is at my disposal to reach this goal?
What actions can I take to achieve this goal?
Are there any requirements?
Are there any forbidden actions?
What is the goal?
Find the sequence of locations that minimize the kilometers that the delivery van runs to deliver all packages. (The green right-hand side solution)
What data is at my disposal to achieve this goal?
A list of locations of clients where packets must be delivered.
The distance in kilometers for each pair of locations.
What actions can I take to achieve this goal?
- For each pair of locations, should the van travel from one to the other? Yes or no.
For example,
Should the van travel from Amy's location to Max's location? Yes or no.
Should the van travel from Ryan's location to Susan's location? Yer or no.
etc.
Are there any requirements?
The delivery van always leaves from the hardware store, and must return to it.
The delivery van has to serve all packets. In other words, it must visit all locations.
Are there any forbidden actions?
Let's make up one forbidden action for the sake of this example.
- Amy wants to return a couple of big packets from previous order. It will be easier for the van driver if those packets are loaded when the van is at least half empty. Thus, Amy must be visited either in 4th, 5th or 6th place (never in 1st, 2nd nor 3rd).
Hand the document to a teammate
All the knowledge needed to solve the problem is clearly stated in the document. It can be assigned to any teammate to find the best solution.
Some teammates will realise that this problem can be already solved with a classic Dijkstra algorithm. Other teammates, like us, will think:
Hey, this document is so well writen that a computer must also be able to understand it, and solve it better than me.
Mr. Computer, could you please read this document and find the solution for me?
This is exactly what Mathematical Programming is about. You hand a document with a description of a problem, a goal, data, a set of actions, a set of rules (requirements and forbidden actions), and ask the computer to find a solution for you.
Solvers
The software that understands documents in this format is called a Solver. A Solver is a black box that recieves a document as an input and solves the problem, i.e. computes the best compliant solution.
Just to give you an idea, here's a list of Solver names depending on the complexity of the problem. Don't expect to understand them yet :)
So, in a nutshell, the job of a mathematical programmer consists in translating a document with human words into a document a Solver can understand, let the Solver do the hard work for you and report back the solution
There are plenty of such libraries to translate documents and interact with solvers in almost all programming languages. Examples are Pyomo, PySCIPOpt, AMPL, GAMS, CPLEX OPL, etc.
Why is it called Mathematical Programming?
Solvers only understand documents with mathematic equations. Consequently, we'll need to write a document with mathematics on it. But trust me, it will be easier than you think.
Solvers are brilliant pieces of engineering. They combine advanced mathematics (linear algebra, calculus, heuristics and more) and computer science (absolute wirzardry going on here) to squeeze every cycle of your CPU and RAM.
Can't wait to see an example!
In the next article we'll install a solver and play our very first thrilling problem.
Attributions
Images desined with Miro.