Maximizing the Path Through a Triangle

A coworker recently introduced me to Project Euler, a website featuring mathematical problems intended to be solved with computer programs. The beginning problems are a warm-up and most can be solved by brute-force algorithms. The problems become more complicated as one progresses, requiring a more focused approach. While many of the initial problems involve finding numbers that satisfy specific mathematical properties (prime numbers, Fibonacci numbers, perfect squares, etc.), later problems can utilize probability, game theory, and Operations Research.

The problem that prompted me to check out the site is to maximize the path through a triangle comprised of numbers, starting at the top and moving down the rows of the triangle through adjacent numbers. The site gives a triangle with a base of four numbers as an example (below). The first problem triangle (Problem 18) has a base of only fifteen numbers and can quickly be solved by brute force if desired. However, a later problem returns to this challenge with a triangle with a base of one hundred numbers (Problem 67) – far too large to just iterate through all possible solutions.

Finding the maximum path through the triangle

Fortunately this problem is easily solved with a basic MIP model. Let the index ij represent the number in position j in row i. Define cij as the value of the number in position ij and xij as a binary variable where 1 indicates number ij is contained in the optimal path through the triangle and 0 indicates it is not contained in the path. The objective is to maximize the sum of the numbers in the path. We only need two sets of constraints to solve this problem. First, only one number in each row can be in the path (moves to the left or right are not allowed). Second, we need to model the requirement that the path must be comprised of adjacent numbers (i.e. if the number in position j in row i is chosen for the path, numbers in row i+1 not adjacent to j cannot be chosen). This yields the following MIP:

max ∑ijcij .
s.t.
(1) ∑j xij = 1   ν i
(2) ∑j’  x(i+1)j’  ≤ 1 – xij where (i+1)j’ is not adjacent to ij   ν ij

In constraint (2), if xij equals 1, the variables for all numbers in the next row that are not adjacent to xij must all be 0. Otherwise at most one of these variables can be 1 (although they can also all be 0).

This problem solves very quickly with Cplex for the triangles on the website (in seconds for the triangle with a base of fifteen numbers and in around a minute for the triangle with a base of one hundred numbers). However, as the triangle grows in size and the run time increases, a MIP approach may not be feasible. I randomly generated a triangle with a base of 200 numbers and after 3-4 hours of solving with Cplex, the best solution still had an optimality gap of 11%. At this point it may be time to bring in the heuristics…

Advertisements
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

3 Responses to Maximizing the Path Through a Triangle

  1. Or solve it exactly using dynamic programming pretty darn quickly (linear in the number of entries). v(i,j) = c(i,j) + max_{j’: (j’,i+1) adjacent to (j,i)} v(i+1,j’) and v(i_max,j) = c(i_max,j) for the bottom row.

    IP seems overkill and that’s a little too quick to jump to heuristics. Unless I have my DP wrong!

  2. Yori says:

    Less efficient that Michael Trick’s method but nice to mention: you can use a shortest path algorithm. Define a network like this: http://i.imgur.com/qB2W2.png . Finding a shortest path from s to t in this network is equivalent to finding a *minimum* path through the triangle. The trick is that this (acyclic) network is special: every path from s to t has exactly the same length (namely, 5 edges). Therefore, you may multiply all edge costs by -1 and run a shortest path algorithm on the resulting network to find a longest path in the original network. This longest path corresponds to a maximum path through the triangle.

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