Relax, But With Constraints

We often wonder if we end up relaxing for too long or wonder when to relax so that getting back to work will not be affected much. Often we wish to relax because we are working on a bigger problem than what we can store in our bag.  But when it comes to us computer science people, the context of this word is changed, i.e. we use it on the problems we work on rather on ourselves as a means of rest.

There are different types of relaxation and the simplest one is called Constrained Relaxation. The main idea behind this type of relaxation is to remove certain constraints that’s set in the problem we’re solving. By removing certain constrains we end up solving an easier version of the same problem. Once after we make some progress or even find a good place to start, we can bring back the same constraint we initially let go.

Let’s take the example of the famous travelling salesman problem. We can relax a certain constraint from this problem by letting the salesman revisit the place again and letting him retrace his steps without any cost. This can be solved by finding the minimum spanning tree, which is also computationally easier” or something,

What we have to to note is that the minimum spanning tree doesn’t give us the exact answer to our problem, it manages to solve a subproblem per se. And definitely this solution would never talk longer to find than the real/actual solution. So we could very well assume this to be our lower bound on the reality.

What’s surprising is that for the travelling salesman problem, it turns out that the minimum spanning tree is actually one of the best starting points to begin with. The basic message behind constrained relaxation is the same when we associate this to life. The idea is to make the intractable tractable and make process in a world subject to your rules which can then port back to the real world. Start by solving an easier version or a reduced version of the same problem if you can’t solve the original. And who knows, maybe this solution would be the actual starting point to solve the bigger problem. Although we are not guaranteed to get a solution or a shortcut to solve the bigger problem, this is definitely not a bad start. In most of the cases we only struggle how to get started and once we do, there’s sometimes no stopping.

Enjoyed the read ?

Subscribe to my FREE newsletter and get super interesting articles delivered straight to your inbox.

Have something to share ?

Feel free to drop a mail to thebotsite@protonmail.me