Optimisation Problems And Techniques Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Nowadays optimisation problems are likely to arise in various domains such as Network Routing, Timetabling, Production Planning etc. The essay discusses approaches used to solve such problems by various optimisation techniques. The essay is structured in such a way that it first takes a brief look of what exactly optimisation and optimisation problems are. The next section describes optimisation techniques i.e., approximation algorithms, heuristics, meta-heuristics, biologically inspired methods, and exact optimisation. The third section details the problem of each domain and lists the strengths and weaknesses of optimistaion techniques, which can be used to solve the problem. The essay concludes by identifying approaches that are best suited to solve specific problems defined by different domains.

2: Overview of Optimisation and Optimisation Problems.

Optimisation in Mathematics and Computer Science refers to choosing the best possible solution/element from the set of available solutions/alternatives. In other words, it means solving problems in which one seeks to maximise or minimise a real function by systematically choosing the real or integer values of variables from within an allowed set.

Many problems both practical and theoretical importance concern themselves with a choice of a "best "configuration or a set of parameters to achieve some goal. Over the past few decades a hierarchy of such problems have emerged, some of them are Non-linear programs, Convex or Integer programs etc. Optimisation problems seem to divide into two general categories: those with continuous variables and those with discrete variables which are called as combinatorial problems. In continuous problems we look for a set of real numbers or an even function while, in combinatorial problems we look for an object from a set such as a Integer set, graph or permutation. Thus we define optimisation problem as:

"An instance of an optimisation problem is a pair of (F, c) where F is any set, the domain of feasible points; c is the cost function, a mapping c: F->R1.

The problem is to find an f Є F, for which c(f) ≤ c(y) for all y Є F. Such a point f is called the globally optimal solution to a given instance or when no confusion can arise; simply an optimal solution."

[Combinatorial optimization: algorithms and complexity By Christos H. Papadimitriou, Kenneth Stieglitz]

3. Approaches used for Optimisation.

3.1 Approximation algorithms.

Approximation algorithms are used to find approximate solutions to optimisation problems rather than finding the exact solution. Some problems are enormously difficult than the cost of running an algorithm to find a exact solution is very high or the time complexity grows exponentially with the input size that it is almost impossible to find a solution in finite time for such problems. Such problems are often referred to NP-Hard. Hence approximation algorithms are used to find the near optimal solution for such problems in polynomial time.

Consider a problem P, A is algorithm and I is the instance.

A (i): cost of solution found by A on I, OPT (i): optimal cost {OPT (i) >0 assumed}

Approximation Factor, ρi = A(i) / OPT(i).

We tend to keep the approximation factor as small as possible.

There are various Approximation algorithms which find a near optimal solution for various classes of NP-complete problems such as 2-Approximation Vertex Cover, Polynomial Time Approximation Scheme, 2-Approximation for TSP special case, Log n Approximation for Set Cover etc.

3.2 Heuristics and Meta-heuristics

In general, Heuristics are based on previously acquired knowledge, experience and common sense. Heuristic as optimization paradigm is also based on similar concept. A heuristic optimization technique uses previously gathered data to yield a feasible solution for an optimization problem or an optimal solution.

It's used in scenarios where either an optimal solution can't be found out using other method or it's just not feasible to use any other method.

The implementation of heuristic algorithm is very simple. It starts with finding, generally, all the possible solution of an optimization problem and creating a database of solutions. The second step would be to start searching from a solution, comparing it with others to find a feasible solution.

It keeps improving a solution by changing neighbourhood or local searches. It allows for movements that will improve the solution by either maximizing or minimizing it. Due to this, it tends to get trapped in local optima, failing to find global optima.

Meta-heuristic approaches use improved search techniques to find solution. Exact and approximate solutions can be found using this. Its search techniques are based on local search, greedy search and other nature inspired algorithms. Unlike heuristics, this approach is suitable for non-polynomial time (NP) optimization problems.

Some of the algorithms to implement meta-heuristic optimization are described here.

Greedy Algorithm

This algorithm starts with finding local optimal solution with intention of finding global optimum solution over iterations.

The process starts with a candidate set. A selection function is used to select next candidate to be added to the set. A feasibility function determines whether the selected candidate should be added or not. If added, an objective function assigns value to the new partial solution. A solution function determines whether a desired solution is obtained?

A greedy algorithm reduces a problem to sub-problems. Each stage is a sub-problem for it. It finds a solution for current stage without considering its previous decision.

Simulated annealing, Random permutation and Iterative repair are few of algorithms that can be categorized under greedy algorithms.

Local Search

Local search is used for finding solution to computationally hard problems. It gives better result when the number of iterations performed is large.

The process starts with an initial solution. For better result, some algorithm should be used to determine the best initial solution. The algorithm searches for better neighbouring solution within the confines of search space. If a better solution is found, the search starts around the new solution. Iterating these steps would result in an acceptable solution for the problem. Iteration can be optionally exited after a fixed number of cycles are performed after finding last solution.

Tabu Search, Simulated Annealing and Reactive Search are some of the search algorithms that belong to family of local search.

Biologically Inspired Methods

Biologically inspired algorithms are based on activities that take place in environment around us. This is discussed in detail in next section.

3.3 Biologically Inspired Methods

These methods study nature and make computer model to simulate their behaviour towards a certain problem. Algorithms under family of evolutionary algorithms and swarm intelligence are most commonly used in field of optimization.

Evolutionary Algorithm

Evolutionary algorithm is a population based meta-heuristic technique.

In this approach, the first generation of solutions (candidates) are generated randomly. The fitness function is applied to them and their offspring. Fitness functions help to determine the solutions that sustains under given constraints. The higher the fitness of a candidate is, the better its chance to be selected for reproduction. The chosen candidates reproduce to by copying their genes. Mutation (random change in genetic identity of the candidate) and crossover (combination of parental genes) takes place. These new born compete the previous generations for being selected into reproduction pool on policy of "survival of the fittest". This step is iterated until a candidate (solution) with desired genetic quality is obtained or the constraint(s); if any; is/ are met.

Genetic algorithm and evolution strategy belong to this family of algorithms.

Swarm Intelligence

Swarm intelligence can be used to model natural as well as artificial behaviour of a collection of entities. Ant colony, bird flock, bee swarm, fish school are most commonly used natural swarms to model algorithms. Behaviour of a species towards a certain problem is studied and a computer model is developed to simulate it.

A decentralized group of self-operated bots are used. Each of them finds their own solution for the problem. They may cooperatively interact with their random neighbour during their solution finding process. Their convergence provides the final optimal solution for the problem.

3.4 Exact Algorithms

Exact algorithms are used to find an optimal solution to a given problem and mostly used to solve a wide variety of NP-Hard problems such as Weighted Set Cover etc, and we aim to find fast exponential-time solutions. Exact algorithms are also applied to solve a wide range of NP-complete problems (assumed P≠NP) using super polynomial time algorithms. There are some problems which have better and faster exact algorithms than others.

Although the exact algorithms seem to find an optimal solution for various combinatorial optimisation problems, the run-time often increases dramatically with instance size and only small instances can be practically solved. Hence sometimes heuristics methods are used instead of exact algorithms where time complexity is a factor under consideration instead of optimality of a solution.

Among the exact methods are Branch and Bound, Dynamic Programming, Lagrangian relaxation-based methods, and Linear and Integer Programming.

4. Strengths and Weakness of these approaches for:

4.1 Network Routing

Network routing is process of selecting a route to send traffic through it. The optimization problem lies here in selecting the shortest route from origin to destination. Passing through intermediate nodes or stops may be the additional constraint to it. More often than not, the environment in a network keeps changing- like breakdown of wire, cellular antenna or an obstruction on road. This adds another layer of complexity to the problem.

Most researched upon networks are data network, communication network and transportation network. Each of these problems has something common among them, as they belong to same domain. We will discuss about suitable optimization approaches to solve problems of this domain and weaknesses of others.

Classical heuristics are not suitable for this kind of optimization problems. But it can be used in scenarios when meta-heuristics fails to deliver any solution or are just not feasible. Getting a solution will always be better than not getting it at all.

Meta-heuristic approaches, mainly biologically inspired, are most suitable for these problems. A lot of research has been done on solving these problems using "Ant Colony Optimization" and "Genetic Algorithm". The ever-changing situations in network routing are the main motivation behind preference of these techniques.

Approaches like "Tabu Search" and "Simulated Annealing" are also suitable but are less adaptive to changing environment.

More often than none, the solutions found are approximate. The time is the main constraint here. Sometimes, it's better to find an approximate solution in lesser time than spending a considerable amount of time to find marginally better exact solution.

Exact solution is easy to find in elementary routing problems, like one dimensional routing. It's also a feasible option when the network is static in nature. Here, it can be found just once and used forever.

4.2 Production Planning

Production planning plays a very important role in the production process of an enterprise. Hence optimisation techniques are used to find solution to the problems that occur during the production phase. Any enterprise has to keep up with the demand of the products by its consumers, produce those products with the available resources without increasing manpower or capacities and earn profits. The optimisation techniques aim to find the optimal amount of products to produce, the optimal time required to produce the product and to maximise the profit in doing so.

A lot of research has been done on the problems of production planning and these have been grouped under the area of Job Shop Scheduling Problems (JSSP). Typically the production planning problems are considered to be combinatorial problems classified as of type NP-hard ordering. The problems in JSSP can be of Sequencing or Scheduling type (broadly speaking). Sequencing requires determining processing order of productions on one or more machines; while Scheduling requires determining the schedule to start and end various production activities synchronously. More specific problems can be Capacity Planning, Inventory Production planning, Production Mix, Facility layout etc. Optimisation techniques are used to find the best possible/optimal sequence or schedule for the above mentioned problems. Since the production processes are time constrained and the problems are NP-hard, it is sometimes not feasible to find exact solutions to the problems and instead a near optimal solution is preferred, although there are exact algorithms to solve these problems. Let's have a look on various optimisation approaches suitable to solve these problems.

Exact Algorithms: These algorithms such as Branch and Bound can be used to solve the production problems but are mostly used for problems with small instances. Since the time complexity increases in these problems with instances and also a lot of computational effort is required sometimes near-optimal solutions are preferred.

Heuristics: These methods might be used for specific problems but the quality of solutions is not guaranteed.

Meta-heuristics: These methods are used to get feasible solutions in short period of time. Neighbourhood search based techniques such as Tabu search, Iterated Local Search are mostly used, since these have small computational times even for larger instances.

Biologically Inspired Methods such as Genetic Algorithms and Ant Colony Optimisation approach are used in the areas where real world scenarios have to be modelled. These algorithms are fast, effective and easy to understand and implement over a wide variety of problems.

Approximation Algorithms are used when it is expensive to find an exact solution or there is no other solution available.

4.3 Timetabling

Timetabling problems have been researched for many decades in the field of Operational Research and Artificial Intelligence. The problems under the broad umbrella of Timetabling are Nurse roistering, Sports timetabling, Transportation timetabling, University timetabling (exam and courses) etc. A lot of research papers have been written on the university timetabling problems as they arise in every educational institute (in general) from time to time.

The timetabling problems are considered to be combinatorial problems which are NP-complete. In general in every timetabling problem the goal is to assign entities (such as tasks, events etc) to a limited number of resources constrained over a specific time to meet the predefined system requirements. So we define the university timetabling problem as, a set of events (i.e., exams or courses) which need to be assigned to a certain number of time periods with predefined constraints. The constraints can be: Hard, which have to be satisfied under any circumstances; Soft, which need to be satisfied as much as possible.

In earlier times of research, the timetabling problems were solved using Graph Heuristics or Integer Programming. These techniques were not suitable to solve too simple or too complex or large problems. As the research progressed over the years, Constraint based techniques were used to address timetabling problems. In the recent years Meta-heuristics techniques have been very popular in solving a wide variety of timetabling problems such as Tabu Search, Simulated Annealing etc (discussed in details in later this section). New approaches and methodologies have also been evolved recently such as Case-based reasoning on educational timetabling and nurse roistering, Fuzzy methodology on exam timetabling and Hyper-Heuristics on timetabling problems.

Now let's have a look on various approaches that can be used to solve timetabling problems.

Exact Algorithms: These algorithms are not suitable for timetabling problems since they are constrained over time. Also it is computationally expensive to find a solution for large timetabling problems using exact algorithms.

Heuristics and Meta-Heuristics: Heuristics methods are not so preferred although there has been a lot of research lately on Hyper-Heuristics approaches.

Meta-Heuristics, on the other hand are most popular techniques to solve timetabling problems. Tabu Search, Simulated Annealing and Evolutionary Algorithms such as Genetic Algorithms and Ant Colony Optimisation techniques are used to solve a wide variety of problems. These are used because these algorithms guarantee to find a feasible solution in a short time span even if the problem is large or has many predefined constraints. Algorithms are fast, effective and real world situations can be effectively analysed using them.

Approximate Algorithms are not considered much, although we have come across few papers in which Constraint Programming is applied to solve Hard constraints and Simulated Annealing is used to solve Soft constraints to generate an approximate solution to a timetabling problem.

[Approximate Solution to an Exam Timetabling Problem By Adam White, Dept of Computing Science, University of Alberta, Combining Constraint Programming and Simulated Annealing on University Exam Timetabling By Tuan-Anh Duong and Kim-Hoa Lam, International Conference for frenchspeaking and Vietnamese computer scientists - 2004]

5. Conclusion

In this fast paced field of technology which is advancing so rapidly, it is inevitable to have several problems. Optimisation techniques have been evolved to tackle some of these problems and to produce solutions which are fast, effective and practical. We have seen various approaches these optimisation techniques use such as Heuristics, Meta-heuristics, Exact and Approximation algorithms and Biologically inspired methods.

We have also discussed the problems arising in the field of Network Routing, Production Planning, and Timetabling, and various approaches that can be used to solve these problems. It will be correct to say that, to solve the problems of Network Routing, biologically inspired techniques are best suited. For the problems of Production Planning evolutionary algorithms such as Genetic Algorithms are the best choice. For the problems of Timetabling, Meta-Heuristics approaches such as Tabu Search, Simulated Annealing and evolutionary algorithms such as Genetic Algorithms and Ant Colony Optimisation techniques are widely used.