For the final project of Efficient Algorithms and Intractable Problems (CS 170), we were asked to solve the not-betweeness problem: given elements `a _{i}`, where

I later found out that this was a variant of betweenness. In this problem, constraints state that an element is between two other elements. Under a different name (Total Ordering Problem), OpatrnÃ½ proved this was NP-complete.

As a result of an early mistake, I ended up creating several solutions (because I believed all of them were suboptimal until I caught my mistake). In retrospect, I really enjoyed the experience because I had the opportunity to explore a lot of different algorithms through the process. The team that I led for this project also finished in the top 8% of groups, with full marks on the project.

At first, I used a genetic algorithm to find the optimal solution. Since my solution was permutation based, I used the swap mutation and the OX1 crossover operator. To select parents, I used tournament selection. Because my fitness function was literally the opposite of what it should've been, this algorithm did not perform very well.

My second solution attempt used a reduction to SAT, and more specifically, 3SAT. To do this, I made boolean variables which represented `a _{i} < a_{j}`. More specifically, if

Because SAT is a well known solver, I assumed a Python SAT solver existed. Thankfully, it did in the form of pycosat. However, it takes clauses in conjunctive normal form (CNF). To convert my clauses into CNF, I recognized that the boolean expression I built was effectively xnor. xor can be represented as (

After getting a set of variables back from the SAT solver, I had to reconstruct this into an ordering. Because each variable represents an ordering between two elements, we can effectively draw a directed acyclic graph (DAG) with this information. More specifically, let us use each

It turns out that the DAG that's created can have circular dependencies. More specifically, there are instances where the solution pycosat returns has a loop which looks like

It was (late) at this stage that I discovered my fitness function was incorrect. In simulated annearling, a huge determining factor in getting the correct solution in a reasonable amount of time is the neighbor-generating function. If a bad function is used, then it's likely that a solution will be stuck in local optima, or just not be able to traverse to the correct solution at all. Because the solutions to not-betweeness are permutation-based, I used neigbor selection algorithms similar to those used for the travelling salesman problem, another permutation-based question. It turned out that random swap (the mutation function from the genetic algorithm) was effective. However, the most effective neighbor-generating function was actually a random slide, in which one element is shifted to another location while all other elements are kept in order.