Another Galapagos Tutorial

September 17, 2013

I’ve been thinking about Grasshopper 2.0 for a while now and there are a lot of facets to the project where I’d like to see improvement. One of the things I’m looking into is incorporating 3rd party code libraries that would provide advanced statistical and algorithmic functionality. One of the libraries I’ve been browsing is the Microsoft Solver Foundation whose main purpose is to solve optimization problems.

Looking for examples on how to use MSF I came across this blog post which poses a hypothetical (but not unrealistic) problem which can be cracked using an algorithmic solver. The post itself has some inconsistencies in the numbers it uses to describe the problem, so I’ll outline it briefly here as well:

  • You own a trading company and you’re looking to import some cheap-ass furniture from China and sell it to gullible Europeans for cut-throat prices. So the goal here is profit maximization.
  • We hire individual containers from a shipping company, and these containers have limits on how much weight you can put in. We’ll use a 500 kilogram limit in this tutorial. We are not concerned with volume limitations.
  • There are three types of furniture we can import; chairs, tables and bookcases (the original article uses cupboards instead of bookcases, but I wanted three items that start with different letters). Each has its own specific purchasing cost, profit margin and weight.
  • There is one additional constraint concerning purchasing cost; your company can only afford to spend 5000 Euros per container.

That’s it, simple enough. A profit function with three variables (amount of chairs, tables and bookcases respectively) and two hard constraints limiting the weight and purchasing costs.

Because of the weight and purchasing constraints this problem becomes non-trivial and an algorithmic approach would be good to have, if only to check your intuitions in case you’re doing the purchasing by hand.

This is a three-variable problem which means the phase space of all possible states is three-dimensional and the fitness landcape is a four-dimensional surface (if you don’t know what a fitness function/landscape is, please see this blog post or buy the Architectural Design publication with my article). I cannot draw a four-dimensional surface on a two-dimensional screen so instead I decided to just make sh*t up and hope it gets the point across regardless of being utter humbug:

Fitness Function with Constraints

Fitness Function with Constraints

Here you see a two-dimensional phase-space (let’s ignore bookcases for the time being and assume we only have to pick chairs and tables) with the resulting three-dimensional fitness landscape. From left to right we go from zero chairs to some arbitrary upper limit. From front to back we go from zero tables to some arbitrary upper limit. Every two-dimensional point is some combination (i.e. state) of chairs and tables. For every combination we can compute the profit that combination would generate, and this has been represented by the height of the landscape. The higher the surface, the more money we’re going to make. Find the highest point on the landscape and you know how many chairs and tables hit the sweet spot.

So far so good. But what about our constraints? Some combinations of chairs and tables are impossible either because they weigh too much or because they cost too much. So our landscape shouldn’t in fact exist at all when this is the case. This is known as a hard constraint and unfortunately in Galapagos it is impossible to add a hard constraint (at least for now).

Luckily we can mimic this effect with penalty clauses. We’re looking to maximize our profit, so what we’ll do is subtract a large amount of money if any of these constraints are overstepped. As long as we subtract enough, the solver will automatically avoid those areas. Enough theorizing, lets hook up some wires!

Let’s start with the simple stuff. We know we’ll need three sliders for the amounts of chairs, tables and bookcases. The lowest possible value of each is zero, we can set the highest possible value at whatever value is clearly beyond our budget.

Problem Variables

Problem Variables

Next up, we need to compute the purchasing cost, sales income and weight for the entire shipment. I’m using the same numbers as in the original article, to wit:

  • Chairs cost 20€, sell for 60€ and weigh 4 kg.
  • Tables cost 150€, sell for 250€ and weigh 8 kg.
  • Bookcases cost 260€, sell for 400€ and weigh 10 kg.

The cost is simply the number of chairs times the price of a chair, added to the number of tables times the price of a table, added to the number of bookcases times the price of a bookcase. We’ll use Grasshopper Expressions for this bit as it’s more economical in terms of screen-space and visual complexity:

Individual Fitness Functions

Individual Fitness Functions

The profit we’ll make is simply the income from sales minus the purchasing cost:

Profit (income - expenditure)

Profit (income – expenditure)

Now we get to the bit about penalty clauses. Basically, if our purchasing costs exceed 5000€ or if the shipment weight exceeds 500 kg this represents an impossible shipment and we need to smack the solver over the head with a rolled up newspaper for daring to venture into forbidden territory. Let’s subtract 100,000€ from the profit calculation if this is the case (you have to pick the severity of your penalty carefully to make sure it’s not too weak or too strong, this unfortunately means you need a firm grasp on the problem at hand). Another possible type of penalty clause could be to either return zero or one and then multiply the profit by this number. Benefit in this case is that no matter how high the profit was before, it will always be zero if it happens to break a constraint.

We’ll again use Grasshopper Expressions to define these penalties, mostly because it’s easiest to write conditional statements this way.

Penalty Clause, Santa's unpopular younger brother

Penalty Clause, Santa’s unpopular younger brother.

Ok, that was actually the hardest bit, we just need to combine our profit with the penalty values and hook up a Galapagos Object to the result. I’ve used negative penalties which means I can add all three values together in a single [Addition] component (zoom in on the left hand side to add the third addition input).

Complete Algorithm

Complete Algorithm

All that is left is to start Galapagos and make sure the solver is aware that it should Maximize the target value (bigger profit good, lower profit bad). We’ll be using the Evolutionary Solver in this example and I’ve also changed the default population size from 50 to 25. It will work with pretty much any population size but when we’re only dealing with three integer variables the number of unique genomes is quite limited so we don’t need a large population to retain a diverse gene-pool. I’m afraid there’s no hard and fast rule as to what population is best for any given problem, 50 is a sensible default, for low-dimensional problems with reasonably continuous fitness landscapes a lower number will be fine.

Galapagos Settings

Galapagos Settings

When you run the solution you may not get the same answer as Flo did. As it turns out, this problem has more than one possible answer. The maximum profit achievable by the functions and the constraints can be reached with several different chair, table and bookcase amounts. Galapagos will present you with one of these solutions.

Galapagos Solver Run

Galapagos Solver Run

Thus endeth the lesson for today. If you feel you understand this problem and want to try your hand at something a bit more complex, I have some suggestions:

  • Make the cost calculation more realistic. I.e. chairs cost 20€, but if you buy more than 15, they only cost 18€. If you buy more than 40, the price drops to 15€, etc.
  • Make the cost constraint more realistic. Instead of having a fixed amount you can spend per container, make it depend on the profit you’ll make. So instead of a hard-coded value of 5000€, make it 90% of the profit you stand to make.
  • Make the algorithm more flexible. Instead of three sliders with hard-coded weights and costs for each type of object, use a Gene Pool to define an easily adjustable number of commodities and use Text Panels to define purchase, sales and weights for each one.

5 Responses to “Another Galapagos Tutorial”

  1. Jonathon Says:

    There is of course a more difficult constraint in that shipping containers have absolute geometric size as well as weight limits.

    Unless in an Ikea flat pack wet dream each is absolutely modular and in the same size box which happens to be a factor of each of the containers dimensions, you may hit packing limits for some combinations prior to weight limits.

    • David Rutten Says:

      Absolutely, that is however a rather difficult constraint to enforce because the number of variables for that problem isn’t just the amount of each type of commodity you’re shipping, but also the position and orientation of each item in the container. So taking the solution for this particular problem (to wit, 94 chairs, 3 tables and 10 bookcases) you’ll have to add 6 variables (X,Y,Z position and X,Y,Z rotation) for each one of those 94+3+10=107 items, leaving you with a 3+(107*6)=645 dimensional phase-space rather than a 3 dimensional one.

      Worse actually, the number of items is a variable so you’d have to deal with a variable-dimensional space. That gets hairy pretty quick.

      If you assume that the actual packing properties don’t matter, then all you need is a way to tell you whether the boxes you’ve picked fit into a container, and then hope that the people doing the packing are good at their job.

      Another way to incorporate this would be to add up the volume of all your items and see if it’s less than the volume of the container, allowing perhaps for 5% empty space because the boxes probably won’t fit very snugly. That is actually a hard-constraint that could relatively easily be added.

  2. 陆大侠 Says:

    Good turorial!!!!!!But,in summing the value process,it seems to be wrong by using “add” component,”multiply”component is right,i guess…..

  3. Lida Says:

    Hello, I am trying to do this example by adding aslo the volume of a container (66.5 m3). but the result I am getting are not really convincing, the volume of the container which i got is 21 m3, any idea how to optimize it to get per example more space filled in the container? thank you

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: