In my previous post Learning Mathematics I mentioned how I wished I was told some practical uses of advanced mathematical entities such as polynomials and matrices. In this section I am going to talk about truth tables. Actually, I am not going to explain what they are because there is a lot of material for that. I am going to talk about what they can be used for in a real-life use case.
Say you have 2 benches and each can seat 3 students. Call these 6 students as s1, s2, s3, s4, s5 and s6 (obviously in real life they have their own unique names and identities). Let’s say all the odd numbered students are girls and even numbered students are boys. If the goal is to just find out how many ways to seat these students, we just need the knowledge of permutations and combinations (the answer is 6!).
However, what if there are constraints on the seating? Say we have the following constraints.
- No two girls should sit next to each other
- Student s1 doesn’t want to sit next to s4
- Student s2 doesn’t want to sit in the middle
You can think of a few more constraints if you wish. Now, how many ways are there to seat the students? This is going to get more complicated. With more number of students and more constraints it’s going to get very ugly. These constraints can be expressed as Boolean functions. First, we need to be able to distinguish between student s1 sitting on the first seat with student s2 sitting. Which means, we also need to label the seats. Let’s call them c1 through c6. If we now thing of each of these 12 variables (s1 to s6 and c1 to c6) as Boolean operations, then ith student sitting on jth seat can be considered as (si and cj). For example, (s1 and c4) indicates that s1 is sitting on c4. If you want to say s2 or s5 can sit on seat c3, it can be written as (c3 and (s2 or s5)). Each one is an individual constraint by itself. Now, the solution is the assignment of True/False to each of these 12 variables such that all the individual constraints listed in the problem are satisfied.
There are actually 3 types of results one might be interested in such problems expressed as constraints. They are
1) Just counting how many ways it’s possible to do
2) What good is just being able to say there are 12,197,407 ways of seating the students for this year’s winter classes without knowing how exactly they can sit? So, we may also be interested in one or all ways of actually assigning the variables values that satisfies the constraints
3) Now, let’s say there is a cost for seating a student in a seat and the cost depends on both the student and the seat. So, C(si,cj) is the cost and what if our goal is to find not just any seating but the one that minimizes the cost? So, we are all of a sudden looking at combinatorial optimization problems.
There are different techniques to solve the problems. Dynamic Programming is one of the most common techniques for solving combinatorial problems where a problem can be decomposed into several sub-problems and the same sub problem repeats several times and it has the same outcome no matter how we reached to that sub-problem.
Dynamic Programming is usually much faster than other straight-forward techniques. However, there are times even dynamic programming is slower, especially if we are trying to enumerate all the solutions to find the optimal one. Also, if the sub-problem space is very large, we can also run into memory problems.
I recently ran into a similar problem. The problem asked for assigning numbers to a set of cells in the grid with some constraints and find the optimal assignment. Say the optimal value is X. Anyone who got found an assignment that gives at least X-3 is considered to have done a good job but the closer one can get to X, the better. My initial dynamic programming based solution gave X-3 in less than 2 minutes and X-2 in about 5 hours. So, I knew there is no way I could get to X with my existing algorithm.
I also knew that there are these things called BDDs but didn’t exactly know what they are and how to solve a problem using them (but I knew they can solve the above type of problems). So, I finally took some time to learn about BDDs and solve the problem. Based on my knowledge of the problem, I have added 4 more additional constraints that I know would help speed up for the optimal structure. With that, the answer for X was found in less than 13 seconds!
Lessons learned for me are
- BDDs are damn fast
- It’s also easy to express individual constraints with Boolean variables than actually coding the same for dynamic programming
- Especially so if we need to refer back to the previous states of the DP
- If the variables are numeric, it’s a bit challenging but not impossible to use BDDs although the number of variables will explore (looks like there are ADDs (Algebraic DDs)and FDDs (Finite Domain DDs) that makes it less challenging
- It’s difficult to debug the logic since at present using BDDs with existing libraries is like writing assembly language (that is, we have to think in terms of the underlying building blocks of the library rather than at a higher level closer to the problem).
I used BuDDy BDD library to solve the problem. It’s written in C++ and very fast compared to another Python library I first tried to use. My current experience with BDDs is a) I can start thinking in BDDs to solve constraint problems b) I know how to use atleast one BDD library. Admittedly, what I still don’t know is all the theory behind BDDs and how they actually work fast. As time permits, I will spend time exploring some of that.
There is very limited information on the internet about using BDDs and solving specific problems. Most of them just hash out the theory behind BDDs which to a normal student can be easily daunting. But getting a feel for a problem, how it can be represented as BDD and using a specific library to solve the problem like I did can come a long way to clear things up or at least create the desire to explore the concepts deeper (I mean, wouldn’t you be curious if you managed to solve a problem in 15 seconds runtime which couldn’t be solved in 5 hrs and still not close to the optimal solution?).
What we need in teaching math or any advanced concept for that matter is to first create the desire to learn something with concrete examples and benefits.